Problem 11013
(American Mathematical Monthly, Vol.110, May 2003) Proposed by D. Callan (USA).
A Dyck n-path is a lattice path of n upsteps (1, 1) and n downsteps (1, −1) that starts at the origin and never falls below the x-axis. Show that the number of Dyck (2n)-paths that avoid {(4k, 0) : 1 ≤ k ≤ n − 1} is twice the number of Dyck (2n − 1)-paths.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
It is well known that the total number of Dyck n-paths is equal to the catalan number Cn= 1
n+ 1
2n n
. Let An be the number of Dyck (2n)-paths that avoid the set
Pn = {(4k, 0) : 1 ≤ k ≤ n − 1} , then we have to prove that
An= 2C2n−1 for all n ≥ 1.
By the inclusion-exclusion principle,
An =
∞
X
j=0
(−1)j· Nj,n
where Nj,nis the number of Dyck n-paths which hit the set Pn at least j ≥ 0 times. Note that this sum is finite actually, because Nj,n= 0 for j ≥ n.
Since a Dyck n-paths which hit the points (4k1,0), · · · , (4kj,0) ∈ Pn with 0 = k0< k1<· · · < kj<
kj+1= n can be obtained by concatening j + 1 Dyck paths respectively of lengths 4si= 4(ki− ki−1) for i = 1, · · · , j + 1, then the total number of such paths is
j+1
Y
i=1
C2si.
Varying the j points in Pn, we get the following formula for Nj,n
Nj,n= X
s1+ · · · + sj+1= n s1≥ 1, · · · , sj+1≥ 1
j+1
Y
i=1
C2si
! .
Let C(x) be the generating function of the catalan numbers and define the functions
G(x) = 1
2(C(x) + C(−x)) − 1 =
∞
X
n=1
C2nx2n,
F(x) = x
2(C(x) − C(−x)) =
∞
X
n=1
C2n−1x2n.
By the convolution property and the formula for Nj,n, we have that
∞
X
n=1
Nj,nx2n= Gj+1(x)
and
∞
X
n=1
Anx2n =
∞
X
n=1
∞
X
j=0
(−1)j· Nj,n
x2n
=
∞
X
j=0
(−1)j·
∞
X
n=1
Nj,nx2n
!
=
∞
X
j=0
(−1)j· Gj+1(x)
= G(x)
1 + G(x).
Therefore, in order to prove An= 2C2n−1 for all n ≥ 1, it suffices to show that
∞
X
n=1
Anx2n = G(x)
1 + G(x) = 2F (x) =
∞
X
n=1
2C2n−1x2n.
This is equivalent to
4F (x) (1 + G(x)) − 2G(x) =xC2(x) − C(x) + 1 + (−x)C2(−x) − C(−x) + 1 = 0, which certainly holds because the generating function C(x) satisfies the equation
xC2− C(x) + 1 = 0.
