Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal

Question

I am in the process of understanding the Catalan problem of how many ways one can reach from (0,0) to (5,5) without trespassing the diagonal.

RUU-RRRRUUU is one way where diagonal trespasses. Now, the complement is taken of the right side. RUU-UUUURRR

I have attached the image (courtesy Discrete and Combinatorial Mathematics by Ralph P. Grimaldi).

Is complementing done with the sole purpose of shifting the parts marked in green (by me) in diagrams c and e to the left of the diagonal?

Also, what is the reason complementing shifts all subsequent steps to the left if so?

Answer 1

Now that i have seen the source, the used counting strategy is easy to explain in the given special situation of paths from $(0,0)$ to $(5,5)$. To recall, we are counting such paths with ten steps of length one using the vectors $R=(1,0)$ and $U=(0,1)$, so that the path is always using lattice points below or on the diagonal line through $(0,0)$, $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, $(5,5)$. Each such path is determined by the places where we insert the $R$'s among the $10$ places where we can do this. The condition of never going strictly upwards beyond the diagonal means, that we always use after each step more $R$'s then $U$'s. We will also identify a path with the "word" $w$ with letters $R,U$ that appear in the order we use them in the path.

And here is the counting strategy.

• Without any restriction, there are $\binom{10}5$ possibilities to chose the places of the five $R$'s among the ten places.
• But we need to count with the diagonal restriction. Instead of counting such "good" paths, respecting the condition, we will count the "bad" paths, where we at least once touch at least one of the points $(0,1)$, $(1,2)$, $(2,3)$, $(3,4)$, $(4,5)$.
• For each such "bad" path break the word $w$ corresponging to it in two subwords, $w_1$ and $w_2$. The first subword $w_1$ is taken till we strictly go upwards beyond the diagonal for the first time, the second word $w_2$ is the remained subword, so that $w=w_1w_2$.
• Now consider the "opposite" word $w_2^*$, obtained by exchanging letters $R\leftrightarrow U$ in $w_2$. And we build the word $w'=w_1w_2^*$.
• Which is the (letter) composition of $w'$? Well, $w_1$ has one more $U$. So $w_2$ has one more $R$. So $w_2^*$ has one more $U$. So $w'=w_1w_2^*$ has two more $U$'s. So $w'$ has six $U$ and four $R$ letters in its composition. How many words of this shape are there? Of course $\binom{10}4=\binom {10}6$.
• To have a full argument, we still need to show that the map $w\to w'$ from bad "$5U+5R$" paths to (all) "$6U+4R$" paths is a bijection. So we need to construct the inverse. This is easily done. Start with a word $v$ of the shape "$6U+4R$". Then there is a first place till where we use strictly more $U$'s than $R$'s, break the string $v$ after this place, so write it like $v=v_1v_2$ with $v_1$ containing $U$'s one more than $R$'s. The same is then true for $v_2$, then build the opposite $v_2^*$ by exchanging $U\leftrightarrow R$, then consider $v'=v_1v_2^*$. It turns out that the map $v\to v'$ is well defined, and the path $v'$ is a "$5U+5R$" bad path.

The above describes the strategy of counting. We obtain finally $$ \binom{10}5-\binom{10}4= \frac{10!}{5!5!}-\frac{10!}{6!4!}= \frac{10!}{5!5!}\left(1-\frac56\right)= \frac{10!}{5!5!}\cdot \frac16= \frac 1{5+1}\frac{10!}{5!5!} $$ "good" paths, this is the Catalan number for $n=5$.

---

Examples:

• Start with $w=RUUURRRUUR$ from the picture, part (c). Write $w=w_1w_2$ with $w_1=RUU$, $w_2=URRRUUR$. (The sub path $RUU$ is the first one going beyond the diagonal.) We build $w'=w_1w_2^*=(RUU)(URRRUUR)^*=(RUU)(RUUURRU)=RUURUUURRU$, which is one of the many words counted in $\binom{10}4=\binom {10}6$. If we start with this result as $v$, so $v=RUURUUURRU$, then while building $v'$ we split it "at the same place", and obtain $v'=(RUURUUURRU)'=(RUU)(RUUURRU)^*=(RUU)(URRRUUR)=w$.

• Start with $w=UURURRRURU$ from the picture, part (e). Write $w=w_1w_2$ with $w_1=U$, $w_2=URURRRURU$. (The sub path $U$ is the first one going beyond the diagonal.) We build $w'=w_1w_2^*=(U)(URURRRURU)^*=(U)(RURUUURUR)=URURUUURUR$, which is one of the many words counted in $\binom{10}4=\binom {10}6$. If we start with this result as $v$, so $v=URURUUURUR$, then while building $v'$ we split it "at the same place", and obtain $v'=(URURUUURUR)'=(U)(RURUUURUR)^*=(U)(URURRRURU)=w$.

• Start with $w=RUURRRRUUU$ from the OP. Then $$ w'=(RUU)(RRRRUUU)^*=(RUU)(UUUURRR)\ . $$

This "(subpath) complement building" is done since the counting strategy is using it. Once found, the strategy is working! There is no "movement of the green part from the pictures" really relevant, instead, this "breaking and second-part-reflecting" procedure is replacing a(ny) "bad" path from $(0,0)$ to $(5,5)$ by a(ny) path from $(0,0)$ to $(4,6)$, and such paths are easily counted. So better paint the end point $(4,6)$ with an other color to mark the idea!