Two Bijections for Dyck Path Parameters
DAVID CALLAN
Department of Statistics
University of WisconsinMadison
1210 W. Dayton St
Madison, WI 537061693
July 19 2004
The Motzkin number (\htmladdnormallinkA001006http://www.research.att.com:80/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001006) counts Motzkin paths: lattice paths of upsteps , flatsteps and downsteps such that (i) the path contains steps, (ii) the number of s = number of s, and (iii) the path never dips below the horizontal line joining its initial and terminal points (ground level) [1]. A Dyck path is a Motzkin path with no flatsteps, counted by the Catalan number . A free Dyck path is one that contains no consecutive and so on. A descent in a path is a maximal sequence of contiguous downsteps. A short descent is one consisting of a single downstep. A terminal descent is one that ends the path. Thus a Dyck path is free iff it contains no short nonterminal descents. Each upstep in a Dyck (or Motzkin) path has a matching downstep: the first one encountered directly East of the upstep.
The first result is easy, and also appears in [2].
Theorem 1.
The number of free Dyck paths is .
Proof.
Given a free Dyck path, change each to , then change each remaining to . This is a bijection to Motzkin paths. For example with
The next bijection gives the distributions both of the parameter “number of s” (\htmladdnormallinkA091869http://www.research.att.com:80/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A091869) [3] and the parameter “number of s” (\htmladdnormallinkA091894http://www.research.att.com:80/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A091894) on Dyck paths.
Theorem 2.
i The number of Dyck paths containing exactly s is
Donaghey distribution.
ii The number of Dyck paths containing exactly s is
Touchard distribution.
Proof.
A bicolored Motzkin path is a Motzkin path of length in which each flatstep is given one of two colors, say green and black, denoted by wavy and flat overlines respectively. There is an obvious bijection to Dyck paths: replace each by , by , by , by and then prepend a and append a .
Here is a less obvious bijection that takes s to s and s to s. Since it is easy to count bicolored Motzkin paths either by s or by s, we get the stated distributions.
Given a bicolored Motzkin path, first append a downstep as a convenience. Now every flatstep has an associated downstep: the first whose initial point is on the ray obtained by extending eastward. Then

Leave s intact

Replace by

Replace by

Replace by and insert a immediately before its associated downstep (thus the new and inserted will be a matching pair and the result is the same no matter in what order the s are processed).
Finally, delete the appended (it remains undisturbed). An example with is illustrated.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . biclored Motzkin path (with appended ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (in red) inserted before each green s become s 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . remaining s labeled along with associated s 1 2 3 1 2 3 
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . change s to s and insert matching s (changed and inserted steps in red) 
The map is invertible: s are recaptured as s followed by a , s are recaptured as s, s are recaptured as s whose matching is in the interior of a descent of length and the original s are recaptured as s such that both the itself and its matching are followed by a . ∎
This map restricted to Motzkin paths (no green s) is a bijection from Motzkin paths to free Dyck paths. Further, note that a Motzkin path contains no flatsteps at ground level iff the corresponding free Dyck path ends with . So, by deleting this , Motzkin paths with no flatsteps at ground level (\htmladdnormallinkA005043http://www.research.att.com:80/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum= A005043) correspond to Dyck paths with no short descents.
References
 [1] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999.
 [2] Sergi Elizalde and Toufik Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials, \htmladdnormallinkpreprinthttp://wwwmath.mit.edu/ sergi/.
 [3] Emeric Deutsch and Louis W.Shapiro, A bijection between ordered trees and 2Motzkin paths and its many consequences, Discrete Math. 256 (2002), 655670.