MathDB

A Dyck

n

-path is a lattice path of

n

upsteps

(1, 1)

and

n

downsteps

(1, -1)

that starts at the origin

O

and never dips below the

x

-axis. A return is a maximal sequence of contiguous downsteps that terminates on the

x

-axis. For example, the Dyck

5

-path illustrated has two returns, of length

3

and

1

respectively. Show that there is a one-to-one correspondence between the Dyck

n

-paths with no return of even length and the Dyck

(n - 1)

paths.
\begin{picture}(165,70) \put(-5,0){O} \put(0,10){\line(1,0){150}} \put(0,10){\line(1,1){30}} \put(30,40){\line(1,-1){15}} \put(45,25){\line(1,1){30}} \put(75,55){\line(1,-1){45}} \put(120,10){\line(1,1){15}} \put(135,25){\line(1,-1){15}} \put(0,10){\circle{1}}\put(0,10){\circle{2}}\put(0,10){\circle{3}}\put(0,10){\circle{4}} \put(15,25){\circle{1}}\put(15,25){\circle{2}}\put(15,25){\circle{3}}\put(15,25){\circle{4}} \put(30,40){\circle{1}}\put(30,40){\circle{2}}\put(30,40){\circle{3}}\put(30,40){\circle{4}} \put(45,25){\circle{1}}\put(45,25){\circle{2}}\put(45,25){\circle{3}}\put(45,25){\circle{4}} \put(60,40){\circle{1}}\put(60,40){\circle{2}}\put(60,40){\circle{3}}\put(60,40){\circle{4}} \put(75,55){\circle{1}}\put(75,55){\circle{2}}\put(75,55){\circle{3}}\put(75,55){\circle{4}} \put(90,40){\circle{1}}\put(90,40){\circle{2}}\put(90,40){\circle{3}}\put(90,40){\circle{4}} \put(105,25){\circle{1}}\put(105,25){\circle{2}}\put(105,25){\circle{3}}\put(105,25){\circle{4}} \put(120,10){\circle{1}}\put(120,10){\circle{2}}\put(120,10){\circle{3}}\put(120,10){\circle{4}} \put(135,25){\circle{1}}\put(135,25){\circle{2}}\put(135,25){\circle{3}}\put(135,25){\circle{4}} \put(150,10){\circle{1}}\put(150,10){\circle{2}}\put(150,10){\circle{3}}\put(150,10){\circle{4}} \end{picture}

Problem Statement