Proof clarification: Catalan numbers and lattice paths

536 Views Asked by At

I'm reading a proof of the fact that the number of monotonic lattice paths from (0,0) to (n,n) not crossing over the diagonal y=x is given by the Catalan numbers. The proof uses the reflection technique (about y = x+1) that a number of other proofs seem to employ as well. That is, you find a bijection between the "bad" paths (ones crossing y = x) and the lattice paths from (0,0) to (n-1,n+1). However, I don't understand this part in the attached image about showing it is indeed a bijection. How does this establish that the reflection transformation described is one-to-one and onto? (In the text below, $\mathcal{B}$ denotes the set of paths crossing the diagonal, and the lattice paths are described as binary strings in V and H, H denoting horizontal movements and V denoting vertical. The position $i$ refers to the $i$-th character in such a string.) enter image description here