Find a bijection between the $(n-1)$ paths and the $n$-paths which have no downramps of even length.

Question

So here is the Question :-

A Dyck $n$-path is a lattice path of n upsteps $(x,y)$ $\rightarrow$ $(x + 1,y + 1)$ and $n$ downsteps $(x,y) \rightarrow (x + 1,y-1)$ that starts at the origin and never dips below the $x$-axis. A downramp of length $m$ is an upstep followed by $m$ downsteps ending on the $x$ axis. Find a bijection between the $(n-1)$ paths and the $n$-paths which have no downramps of even length.

I know the definition of Dyck-path , it is a staircase walk from $(0,0)$ to $(n,n)$ that strictly lies below the diagonal joining $(0,0)$ and $(n,n)$ , and got the definition of a downramp . But I am not sure how to show a bijection , can anyone help ?

Answer 1

Let $A$ be the set of all $(n-1)$ paths and $B$ the set of all $n$-paths without even-length downramps. Define $u$: $A$ $\rightarrow$ $B$ as follows:- if the path has no even-lengthed downramps, then add an upstep followed by a downstep at the start of the path. Otherwise just add an upstep at the start and a downstep after the last even-lengthed downramp. The new path is an $n$-path and has no downramps until what was the last even-lengthed downramp, but is now odd. Hence all its downramps are odd and it belongs to set $B$.

Now define L: $B$ $\rightarrow$ $A$ as follows:- remove an upstep from the start and remove a downstep from the first downramp. The result is $A$. A little thought shows that ud and du are both identity maps. Hence u and d are both bijections.

Answer 2

The answer provided by Maths-Lover is actually incorrect. The injection $u: A \to B$ is fine, however its inverse is incorrect. Consider the inverse $L$ acting on the two Dyck paths represented by the binary strings $p_1 = 11101000$ and $p_2 = 10111000$ (where $1$ is an up-step and $0$ is a down-step). Notice how $L(p_1) = L(p_2) = 111000$ -- which means that $L$ is not injective and cannot be an inverse.

The correct inverse would be the function $I: B \to A$ which acts on a path in $p \in B$ as follows. If $p$ begins with a $10$, then $I(p)$ is the path with the first $10$ removed. Otherwise, $I$ removes the first $1$ and the first $0$ from the first block of $0$s of odd length at least $3$.