7. [6] Rachel has two indistinguishable tokens, and places them on the first and second square of a $1 \times 6$ grid of squares, She can move the pieces in two ways:
- If a token has free square in front of it, then she can move this token one square to the right
- If the square immediately to the right of a token is occupied by the other token, then she can "leapfrog" the first token; she moves the first token two squares to the right, over the other token, so that it is on the square immediately to the right of the other token.
If a token reaches the 6th square, then it cannot move forward any more, and Rachel must move the other one until it reaches the 5 th square. How many different sequences of moves for the tokens can Rachel make so that the two tokens end up on the 5 th square and the 6 th square?
Answer: 42
We put a marker on $(i, j)$ when a token is on $i$ th and $j$ th square and $i>j$. When the token in front/behind moves one step forward to a blank square, move the marker rightward/upward one unit correspondingly. When a "leapfrog" happens, the marker moves from $(x-1, x)$ to $(x, x+1)$. We can translate this movement into: 1 . move the marker upward to $(x, x) ; 2$. move the marker rightward to $(x, x+1)$. Thus, we set up a lattice path way from $(2,1)$ to $(6,5)$ staying under $y=x$. This is a bijection since every intersection of the path way and $y=x$ indicates a "leapfrog". According to the definition of Catalan Number, the answer is the number of such lattice path ways, which is $C_{5}=42$.