Putnam 2003, Problem A-5

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.

Solution:
### First solution:  
We represent a Dyck \( n \)-path by a sequence \( a_1 \cdots a_{2n} \), where each \( a_i \) is either \( (1,1) \) or \( (1,-1) \).  

Given an \( (n - 1) \)-path \( P = a_1 \cdots a_{2n-2} \), we distinguish two cases. If \( P \) has no returns of even-length, then let \( f(P) \) denote the \( n \)-path \( (1,1)(1,-1)P \). Otherwise, let \( a_i a_{i+1} \cdots a_j \) denote the rightmost even-length return in \( P \), and let \( f(P) = (1,1)a_1 a_2 \cdots a_j (1,-1)a_{j+1} \cdots a_{2n-2} \). Then \( f \) clearly maps the set of Dyck \( (n - 1) \)-paths to the set of Dyck \( n \)-paths having no even return.  

We claim that \( f \) is bijective; to see this, we simply construct the inverse mapping. Given an \( n \)-path \( P \), let \( R = a_1 a_2 \cdots a_j \) denote the leftmost return in \( P \), and let \( g(P) \) denote the path obtained by removing \( a_1 \) and \( a_j \) from \( P \). Then evidently \( f \circ g \) and \( g \circ f \) are identity maps, proving the claim.  


### Second solution: (by Dan Bernstein)  
Let \( C_n \) be the number of Dyck paths of length \( n \), let \( O_n \) be the number of Dyck paths whose final return has odd length, and let \( X_n \) be the number of Dyck paths with no return of even length.  

We first exhibit a recursion for \( O_n \); note that \( O_0 = 0 \). Given a Dyck \( n \)-path whose final return has odd length, split it just after its next-to-last return. For some \( k \) (possibly zero), this yields a Dyck \( k \)-path, an upstep, a Dyck \( (n - k - 1) \)-path whose odd return has even length, and a downstep. Thus for \( n \geq 1 \),  
\[
O_n = \sum_{k=0}^{n-1} C_k (C_{n-k-1} - O_{n-k-1}).
\]  

We next exhibit a similar recursion for \( X_n \); note that \( X_0 = 1 \). Given a Dyck \( n \)-path with no even return, splitting as above yields for some \( k \) a Dyck \( k \)-path with no even return, an upstep, a Dyck \( (n - k - 1) \)-path whose final return has even length, then a downstep. Thus for \( n \geq 1 \),  
\[
X_n = \sum_{k=0}^{n-1} X_k (C_{n-k-1} - O_{n-k-1}).
\]  

To conclude, we verify that \( X_n = C_{n-1} \) for \( n \geq 1 \), by induction on \( n \). This is clear for \( n = 1 \) since \( X_1 = C_0 = 1 \). Given \( X_k = C_{k-1} \) for \( k < n \), we have  
\[
X_n = \sum_{k=0}^{n-1} X_k (C_{n-k-1} - O_{n-k-1}) = C_{n-1} - O_{n-1} + \sum_{k=1}^{n-1} C_{k-1} (C_{n-k-1} - O_{n-k-1}) = C_{n-1} - O_{n-1} + O_{n-1} = C_{n-1},
\]  
as desired.  

**Note:** Since the problem only asked about the existence of a one-to-one correspondence, we believe that any proof, bijective or not, that the two sets have the same cardinality is an acceptable solution. (Indeed, it would be highly unusual to insist on using or not using a specific proof technique!) The second solution above can also be phrased in terms of generating functions. Also, the \( C_n \) are well-known to equal the Catalan numbers \( \frac{1}{n+1} \binom{2n}{n} \); the problem at hand is part of a famous exercise in Richard Stanley’s *Enumerative Combinatorics*, Volume 1 giving 66 combinatorial interpretations of the Catalan numbers.