Séminaire Lotharingien de Combinatoire 53 (2006), Article B53e

SOME BIJECTIONS AND IDENTITIES FOR THE CATALAN AND FINE NUMBERS

DAVID CALLAN

Department of Statistics, University of Wisconsin-Madison 1300 University Avenue, Madison, WI 53706-1532

                       E-mail: callan@stat.wisc.edu

Abstract. We establish combinatorial interpretations of several identities for the Catalan and Fine numbers. Analytic proofs are outlined and we also give combinatorial proofs utilizing some new bijections of independent interest. We show that C_{n} = \frac{1}{n+1} ∑_{k} \binom{n+1}{2k+1}\binom{n+k}{k} counts ordered trees on n edges by number of interior vertices adjacent to a leaf and C_{n} = \frac{2}{n+1} ∑_{k} \binom{n+1}{k+2}\binom{n−2}{k} counts Dyck n-paths by number of long interior inclines. We also give an analogue for the Fine numbers of Touchard’s Catalan number identity.

1. Introduction

The purpose of this paper is to establish combinatorial interpretations of several identities for the Catalan numbers and one for the Fine numbers. The identities are relatively easy to prove by analytic methods but our main object is to give bijective proofs. The common thread is a generalization, from ordinary lattice paths to “marked” paths, of a well known bijective method for counting Dyck paths. Before reviewing terminology and introducing marked paths, let us list the main results:

C_{n} = \frac{2}{n + 1} ∑_{k=0}^{n−2} \binom{n + 1}{k + 2}\binom{n − 2}{k}

counts Dyck n-paths by number of long interior inclines,

C_{n} = \frac{1}{n + 1} ∑_{k} \binom{n + 1}{2k + 1}\binom{n + k}{k}

counts ordered trees on n edges by number of interior vertices adjacent to a leaf, and

F_{n} = \frac{1}{n + 1} ∑_{k≥0} \binom{n − 2 − k}{k}2^{n−2−2k}\binom{n + 1}{k + 1}

counts Fine n-paths by number of long noninitial ascents.

2. Terminology and Notation

A balanced n-path is a sequence of n Us and n Ds, represented as a path of upsteps (1, 1) and downsteps (1, −1) from (0, 0) to (2n, 0). An ascent in a balanced path is a maximal sequence of (consecutive) upsteps and analogously for a descent. An incline is an ascent or descent. An incline is short if it consists of just one step, otherwise it is long. An ascent consisting of j upsteps contains j − 1 vertices of the path in its interior. We will need the notion of a path with marked vertices. Two types of vertex are relevant. An IA vertex is one incident with two upsteps, that is, a vertex in the interior of an ascent (IA for interior ascent). A DF vertex is one that is not incident with a downstep (DF for downstep free). Every IA vertex is also DF but the initial and terminal vertices of a balanced path, while never IA, may or may not be DF. A k-IAmarked (resp. k-DFmarked) balanced path is one in which k of the IA (resp. DF) vertices have been marked.

A Dyck path is a balanced path that never drops below the x-axis (ground level). The size of a Dyck path, sometimes called its semilength, is the number of upsteps; thus a Dyck n-path has size n. The empty Dyck path is denoted ϵ. A nonempty Dyck path always has an initial ascent and a terminal descent; all other inclines are interior. A peak is an occurrence of UD and similarly a valley is a DU. A DXD is an occurrence of DUD or DDD. A peak vertex is a vertex preceded by a U and followed by a D. A hill is a peak at level 1. Every U in a Dyck path has a matching D: the downstep terminating the shortest Dyck subpath beginning at U. We also need the notion of an associated D with each U: the downstep terminating the longest Dyck subpath beginning at U.

The marked Dyck path illustrated has size 6, 4 peaks, 3 valleys, 2 UUs, 2 DDs, 2 long interior inclines, 3 DXDs and 1 hill. It has one marked vertex that is both IA and DF.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; U_{1}; U_{2}; associated; D for U_{2}; ↙; matching; D for U_{1}; ↑; •; •; •; •; •; •; •; •; •; •; •; •; •]

a marked Dyck path

3. The \frac{1}{n+1} Factor

It is classic that the parameter X on balanced n-paths defined by X = “number of upsteps above ground level” is uniformly distributed over {0, 1, 2, …, n} and hence divides the \binom{2n}{n} balanced n-paths into n + 1 equal-size classes, one of which consists of the Dyck n-paths (the one with X = n). Indeed, for 1 ≤ i ≤ n, a bijection from balanced n-paths with X = 0 (inverted Dyck paths) to those with X = i is as follows. Number the upsteps from right to left and top to bottom, starting with the last upstep. Then remove the first downstep D encountered directly west of upstep i to obtain two subpaths P and Q, and reassemble as Q D P. (See [1] for a more leisurely account.)

This bijection does not disturb the lengths of ascents. So we can conclude that the number of Dyck n-paths with k odd-length ascents is \frac{1}{n+1} times the number of balanced n-paths with k odd-length ascents. We will use this fact in §8 below. More importantly, the bijection can equally well be applied to k-IAmarked balanced n-paths: the interior vertices of ascents are never disturbed. It again produces n + 1 equal-size classes one of which consists of the k-IAmarked Dyck n-paths. One consequence [2] is that the total number of IAmarked Dyck n-paths (with no restriction on the number of marks) is the little Schröder number s_{n} and, since DFmarked Dyck paths also allow a mark on the initial vertex, the number of DFmarked Dyck n-paths is the big Schröder number r_{n} = 2s_{n} (n ≥ 1). In fact, there is a simple bijection from DFmarked Dyck paths to a well known manifestation of the big Schröder numbers — Schröder paths. A Schröder path is a path of upsteps (1, 1), double-flatsteps (2, 0), and downsteps (1, −1) that starts at the origin, never drops below the x-axis, and terminates on the x-axis. The terminal point necessarily has even x-coordinate, say 2n; then we call it a Schröder n-path and we say its size is n. The number of Schröder n-paths is r_{n}. Here is a bijection from DFmarked Dyck paths to Schröder paths that preserves size and sends marks to doubleflatsteps. Given a DFmarked Dyck path, locate the upsteps starting at a marked vertex along with their matching downsteps. Then delete these upsteps (and their marks) and replace each matching downstep by a double-flatstep. An example with 3 marks and size 8 is illustrated.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; DFmarked Dyck path; Schröder path; ⟶; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....]

Note that a mark on the initial vertex of the Dyck path corresponds to the first doubleflatstep at ground level in the Schröder path. Thus,for n ≥ 1, there are just as many Schröder n-paths with a double-flatstep at ground level as without. Hence, the number of Schröder n-paths with no double-flatsteps at ground level is r_{n}/2, the small Schröder number. See [3] for other connections between the large and small Schröder numbers.

4. The DUtoDXD Bijection

We define a bijection on Dyck n-paths with the following properties.

(1) It sends # DUs (valleys) to # DXDs. Since # valleys has the Narayana distribution [4], so does # DXDs. Many other statistics having the Narayana distribution on Dyck paths are given in [4].

(2) It sends the paths with a terminal descent of even length to the hill-free paths, thereby giving a bijection between two manifestations of the Fine numbers [5, p. 263].

(3) It sends the nonempty paths all of whose descents to ground level have odd length to the paths that start UD, thereby giving a bijective proof for item j in [6, Ex. 6.19].

The bijection ϕ can be defined recursively as follows. First, ϕ(ϵ) = ϵ and we consider nonempty paths P by the parity of the length of the terminal descent.

(i) terminal descent has even length. Here P has the form (uniquely)

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P; =; P_{1}; P_{2}; …; P_{ℓ−1}; P_{ℓ}; Q]

with ℓ ≥ 1, P_{1}, …, P_{ℓ} arbitrary Dyck paths, and Q a Dyck path (possibly empty) whose terminal descent has even length. Then

[figure: ^{.....}; ^{.....}; …; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ϕP; =; ϕP_{1}; ϕP_{2}; ϕP_{ℓ}; ϕQ]

(ii) terminal descent has odd length. Here P has the form

[figure: …; •; •; •; •; •; •; •; •; •; •; •; P; =; P_{1}; P_{2}; P_{ℓ}; P_{0}]

with ℓ ≥ 1, P_{0}, P_{1}, …, P_{ℓ} Dyck paths (possibly empty) whose terminal descent has even length. Then

[figure: …; •; •; •; •; •; •; •; •; •; ϕP; =; ϕP_{0}; ϕP_{1}; ϕP_{2}; ϕP_{ℓ}]

Note that all UDs terminating the path are preserved; in particular, ϕ preserves the property “ends DD”. Clearly, ϕ sends Dyck paths whose terminal descent has odd length to paths containing at least one hill and, by induction, it sends paths whose terminal descent has even length to hill-free paths. These facts allow the process to be reversed and yield a similar recursive definition of the inverse ψ. Again there are two cases:

(i) P is nonempty hill-free. Here P has the form

[figure: ^{.....}; ^{.....}; …; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P; =; P_{1}; P_{2}; P_{ℓ}; Q]

with ℓ ≥ 1, P_{1}, P_{2}, …, P_{ℓ} arbitrary Dyck paths and Q (possibly empty) a hill-free Dyck path. Then

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; ψP; =; ψP_{1}; (∗); …; ψP_{ℓ−1}; ψP_{ℓ}; ψQ]

(ii) P contains hills. Here P has the form

[figure: …; •; •; •; •; •; •; •; •; •; P; =; P_{0}; P_{1}; P_{2}; P_{ℓ}]

with ℓ ≥ 1, P_{0}, P_{1}, …, P_{ℓ} hill-free Dyck paths (possibly empty). Then

[figure: …; •; •; •; •; •; •; •; •; •; •; •; ψP; =; ψP_{0}; (∗∗); ψP_{1}; ψP_{2}; ψP_{ℓ}]

To show (by induction) that ϕ sends # DUs to # DXDs, let μ(P) denote the number of DUs in P and ν(P) the number of DXDs. Then in case (i) — terminal descent has even length — we find

μ(P) = ℓ − 1 + μ(P_{1}) + … + μ(P_{ℓ−1}) + μ(P_{ℓ}) + μ(Q) + [P_{ℓ} ≠ ϵ].

Here [A] is the Iverson notation: [A] = 1 if A is true and = 0 if A is false. The term [P_{ℓ} ≠ ϵ] is present because the U following P_{ℓ} is part of a DU precisely when P_{ℓ} is nonempty. We also have

ν(ϕP) = ℓ − 1 + ν(ϕP_{1}) + … + ν(ϕP_{ℓ−1}) + ν(ϕP_{ℓ}) + ν(ϕQ) + [ϕP_{ℓ} ≠ ϵ].

Here we have used the fact that ϕQ does not start UD because it is hill-free and the initial term ℓ − 1 records the ℓ − 1 DDDs contained in the first descent to ground level of ϕP. So induction yields μ(P) = ν(ϕP) in case (i) and a similar argument works for case (ii). Because of this key property, we will subsequently refer to ϕ as the DUtoDXD bijection and to its inverse as DXDtoDU.

Next, we show that DXDtoDU sends the paths that start UD to the paths all of whose descents to ground level have odd length. A path P that starts UD necessarily has P_{0} = ϵ in the form (ii) above for hill-containing paths and ψP, as defined, has all descents to ground level of odd length because ψ sends hill-free paths to paths whose terminal descent has even length. Similarly, ψ sends all other paths to images that contain at least one even-length descent to ground level.

A recursively defined bijection is often easier to work with but it is also of some interest to have an explicit description. Here is a cut-and-paste description of DXDtoDU. Given a Dyck path, first color red the last D of each DDD. Then color blue the middle U of each DUU unless its matching downstep is immediately followed by a red D.

[figure: ^{.....}; _{.....}; •; •; •; •; •; •; •; •; •; •; •; •; •; blue U; ↓; red D; ↓; not blue; (its matching D is; followed by a red D); ↑]

Process the blue Us one at a time as follows (the resulting path is independent of the order of processing). Delete the Dyck subpath starting at a blue U and terminating at its matching D, and reinsert at the rightmost peak vertex preceding it just before deletion. Then process the red Ds in the resulting path as follows (simultaneously, if you like). For each red D locate the matching upstep U of its predecessor step (the predecessor is necessarily a downstep); then delete the red D and reinsert just before the corresponding U. An example is illustrated below with red steps labeled 1,2,… and blue steps labeled a, b, . . ..

Let θ denote this cut-and-paste map. To show that θ coincides with DXDtoDU, it suffices to show that θ satisfies the defining properties (∗) and (∗∗) of DXDtoDU. In applying θ, a noninitial upstep is colored blue iff it does not start a hill. For each red downstep, the matching upstep of its predecessor remains so after processing a blue step. Also, processing a red downstep D only affects the longest Dyck subpath terminating at D. Using these facts, one may verify that θ satisfies (∗) and (∗∗) (and the initial condition θ(ϵ) = ϵ), and hence θ = DXDtoDU. To invert the cut-and-paste map θ we must first recover the red Ds and blue Us in the image path. This is a little more involved. A valley D is one whose successor step is a U. The associated Dyck path of an upstep in a Dyck path is the longest Dyck subpath starting at the upstep. The red Ds are recovered as the valley Ds for which the associated Dyck path of the successor upstep contains at least one descent of even length to (its own) ground level. Then the blue Us are recovered as the Us whose associated Dyck path (i) is immediately preceded by an upstep (i.e. U is the second step of a double-rise), (ii) has terminal descent of even length, and (iii) is NOT immediately followed by a red D. Once the colored steps have been determined, the reverse cut-and-paste procedure is clear.

[figure: ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; 1; 2; 3; 1; 2; 3; 1; 2; 3; a; b; c; a; b; c; a; b; c; Dyck path P; DXDtoDU(P); process ↓ blues; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; process ↓ reds; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

An example of DXDtoDU

The properties of DUtoDXD that were proved above by induction from the recursive definition can also be seen directly from the explicit description.

5. Review of Known Bijections

In this section, we review some well known bijections involving Dyck paths. The simplest bijection of all merely flips the path in the vertical, an involution that we call ReversePath. There is another involution ϕ on Dyck paths, due to Emeric Deutsch [7], that can be defined recursively as follows.

[figure: •; •; •; •; •; •; •; •; P_{1}; ⟶; P_{2}; ϕP_{2}; ϕP_{1}; ⟶; ϵ; ϵ]

The main properties of this involution that we need are as follows (proof by induction): (i) it sends # UUs to # DUs (in fact, being an involution, it interchanges them) (ii) it sends “length of first descent” to “1+# noninitial UDs that terminate the path”.

In particular, it send paths with a short (resp. long) first descent to paths that end DD (resp. UD).

To illustrate property (ii), note that ϕ(U^{k}D^{k}) = (UD)^{k} and U^{k}D^{k} has first descent of length k while (UD)^{k} terminates with k − 1 noninitial UDs. For paths other than those of the form (UD)^{k}, the UDs terminating the path are all necessarily noninitial.

We mention in passing that, using the well known “walkaround” bijection from binary trees to Dyck paths, ϕ has a simple explicit description: given a Dyck path, pass to the corresponding binary tree, flip it in the vertical, then pass back. We will refer to this involution as DeutschInvol.

A Levine-(r, s) pair (apparently first considered in [8] ) is a pair (B, T) of nonintersecting lattice paths of steps North (N = (0, 1)) and East (E = (1, 0)), where B (the bottom path) runs from (1,0) to (r, s−1) and T (the top path) runs from (0, 1) to (r−1, s). There is a well known bijection, LevineToDyck, from Levine-(r, s) pairs by way of ascent/descent sequences to Dyck-(r + s − 1) paths with r peaks, illustrated below with r = 4, s = 5.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; (0,0); (4,5); •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; a = (1, 0, 2, 1); d = (0, 0, 2, 2); asc = (2, 1, 3, 2); des = (1, 1, 3, 3); Levine pair; Dyck path; ⟶]

Set a = (a_{i})_{i=1}^{r} with a_{i} = number of consecutive Ns preceding the ith E in the top path (a_{r} = # terminal Ns) and likewise define d = (d_{i})_{i=1}^{r} for the bottom path. Then use 1 + a and 1 + d as the ascent lengths (left to right) and descent lengths respectively of the corresponding Dyck-(r + s − 1) path. The Dyck path has r ascents and hence r peaks. Note that if the top path T ends N (resp. E), then the last ascent of the Dyck path is long (resp. short).

6. Dyck Paths by Long Interior Inclines

The number a_{n,k} of Dyck n-paths containing k long nonterminal inclines is \frac{1}{n} \binom{n}{k}\binom{n}{k+1} — the Narayana distribution [4]. It turns out that the number b_{n,k} of Dyck n-paths containing k long interior inclines also has a simple distribution. In fact, such a path either begins with a short ascent, that is, a hill (a_{n−1,k} choices) or a long ascent (a_{n,k+1} − a_{n−1,k+1} choices), and hence b_{n,k} = a_{n,k+1} − a_{n−1,k+1} + a_{n−1,k} which simplifies to \frac{2}{n+1} \binom{n+1}{k+2}\binom{n−2}{k}.

We wish to give a direct bijective proof that b_{n,k} = \frac{2}{n+1} \binom{n+1}{k+2}\binom{n−2}{k}. We have

\frac{2}{n + 1}\binom{n + 1}{k + 2}\binom{n − 2}{k} = \binom{n − 2}{k}\binom{n}{k + 1} − \binom{n − 2}{k − 1}\binom{n}{k + 2}

and, by the beautiful Gessel-Viennot determinant theorem for nonintersecting paths [9, 10], this is the number of pairs (B, T) of nonintersecting lattice paths consisting of steps N and E where B runs from (1, 0) to (k+2, n−1−k) and T runs from (0, 1) to (k, n−1−k). On this set, the map “delete last step of B, flip it (N ↔ E), then append it to T ” is a bijection (i) from the pairs in which B ends N to the set A of Levine-(k + 2, n − 1 − k) pairs in which the top path ends E, and (ii) from the pairs in which B ends E to the set B of Levine-(k + 1, n − k) pairs in which the top path ends N.

We are about to exhibit a sequence of bijections from A (resp. B) to Dyck n-paths containing k long interior inclines and ending DD (resp. UD). But first we need to relate the number of long interior inclines in a Dyck path P to the number of DXDs in the elevated path E(P) (to elevate a path, prepend U and append D, thus E(P) = UP D).

Lemma. For n ≥ 1 and P a Dyck n-path, # long interior inclines in P + # DXDs in E(P) = n − 1.

Proof. In E(P), each of its n + 1 Ds is either (i) preceded by UU, (ii) preceded by DU, (iii) an interior D in a long descent, or (iv) the last D in a long descent. The Ds in the respective classes correspond in an obvious way to (i) long ascents, (ii) DUDs, (iii) DDDs, and (iv) long descents in E(P). Since the first and last inclines in E(P) are necessarily long, the result follows. □

Since each noninitial U in a Dyck n-path P is preceded either by a U or a D, we also have the obvious result for P: # UUs + # DUs = n − 1. And it is all but obvious that # UDs = 1 + # DUs.

Finally, here are the promised sequences of bijections:

A

LevineToDyck

⟶

Dyck n-paths with a short last ascent and k + 2 peaks

⟶^{ReversePath} Dyck n-paths with a short first descent and n − 2 − k UUs

DeutschInvol

⟶

Dyck n-paths that end DD with n − 2 − k DUs

⟶^{DUtoDXD} Dyck n-paths that end DD with n − 2 − k DXDs

= Dyck n-paths that end DD with n − 1 − k DXDs in E(P) = Dyck n-paths with k long interior inclines that end DD.

Similarly,

B

LevineToDyck

⟶

Dyck n-paths with a long last ascent and k + 1 peaks

⟶^{ReversePath} Dyck n-paths with a long first descent and n − 1 − k UUs

DeutschInvol

⟶

Dyck n-paths that end UD with n − 1 − k DUs

⟶^{DUtoDXD} Dyck n-paths that end UD with n − 1 − k DXDs

= Dyck n-paths that end UD with n − 1 − k DXDs in E(P) = Dyck n-paths with k long interior inclines that end UD.

7. Another Catalan Number Identity

An identity related to that of the preceding section is

C_{n} = ∑_{k=0}^{n−1} (\binom{n − 1}{k}^{2} − \binom{n + 1}{k + 2}\binom{n − 3}{k − 2}) , n ≥ 1.

Again using Gessel-Viennot, the summand is the number of pairs (B, T) of nonintersecting lattice paths, B running from (2, 0) to (k + 2, n − 1 − k) and T running from (0, 0) to (k, n − 1 − k). Delete the last step of B, flip it and append to T as in the last section. Likewise, delete the first step of T, flip it and prepend to B. This produces Levine pairs and then LevineToDyck is a bijection to Dyck n-paths, establishing the identity.

In fact, the identity counts Dyck-n paths by the statistic X := X_{1} + X_{2} where X_{1} = # long interior inclines and X_{2} = [path is strict] where strict means the path returns to ground level only at its terminal point. To see this, let b_{n,k} = \frac{2}{n+1} ∑_{k=0}^{n−2} \binom{n+1}{k+2}\binom{n−2}{k} denote the number of Dyck n-paths containing k long interior inclines as in the preceding section, and let c_{n,k} denote the number of strict Dyck n-paths containing k long interior inclines. Clearly, c_{n,k} = b_{n−1,k}. Splitting paths with X = k into those that are strict and those that aren’t, we find the total count is c_{n,k−1} + (b_{n,k} − c_{n,k}). A routine if tedious simplification gives the summand above.

Is there a more “natural” statistic on Dyck paths (or on some other manifestation of the Catalan numbers) with this distribution?

8. Ordered Trees by Nodes Adjacent to a Leaf

Following Deutsch and Shapiro [11], we define a node in an ordered tree to be a vertex that is neither a leaf nor the root. Thus the vertices are partitioned into 3 classes: root, nodes, leaves.

The number a_{n,k} of ordered trees on n edges containing k nodes adjacent to a leaf is given in the following table for small n, k,

n \ k 0 1 2 3 4
1 1
2 1 1
3 1 4
4 1 10 3
5 1 20 21
6 1 35 84 12
7 1 56 252 120
8 1 84 630 660 55

Table of values of a_{n,k}

and it turns out that a_{n,k} = \frac{1}{n+1} ∑_{k} \binom{n+1}{2k+1}\binom{n+k}{k}.

The referee kindly supplied a proof using generating functions and Lagrange inversion. One version goes like this. Let F (x, y) = ∑_{n≥0,k≥0} a_{n,k}x^{n}y^{k}, and let G(x, y), H(x, y) respectively denote the analogous generating functions for trees whose root has outdegree 1 and trees whose root has no child that is a leaf. Then one sees combinatorially that

H = \frac{1}{1 − (G − x)},

that F = 1 + GF, or equivalently,

G = 1 − \frac{1}{F} ,

and that

F = \overbrace{1}^{(1)} + \overbrace{xF}^{(2)} + \overbrace{x(H − 1)F}^{(3)} + \overbrace{x^{2}yF^{2}}^{(4)} + \overbrace{xy(G − x)(F − H)F}^{(5)} .

With c denoting the first child of the root, the five summands count as follows: (1) the no-edge tree, (2) c is a leaf, (3) c has at least one child but no leaf child, (4) first child of c is a leaf, (5) c has at least one leaf child but first child of c is not a leaf. Eliminating G and H leads to the recursion

F = 1 + xF + x^{2}yF^{3}.

Set z = y/x and f(x, z) = xF (x, xz). Then

f = x(1 + f + zf^{3})

and Lagrange inversion tells us that

[x^{n}]f = \frac{1}{n}[f^{n−1}](1 + f + zf^{3})^{n}

leading to the formula a_{n,k} = \frac{1}{n+1} ∑_{k} \binom{n+1}{2k+1}\binom{n+k}{k} above.

To obtain this result bijectively, we first show directly that \binom{n+1}{2k+1}\binom{n+k}{k} counts certain marked balanced paths. Then we exhibit a bijection from these marked paths to (plain) balanced n-paths with n − 2k odd-length ascents. Next we apply §3 to see that \frac{1}{n+1} ∑_{k} \binom{n+1}{2k+1}\binom{n+k}{k} counts Dyck n-paths with n − 2k odd-length ascents. Finally, we exhibit a bijection from the latter paths to Dyck paths that correspond, under a familiar bijection (variously known as the walkaround, glove or accordion bijection), to ordered trees on n edges containing k nodes adjacent to a leaf.

Recall DF refers to paths with downstep-free vertices available for marking. Now we show that \binom{n+1}{2k+1}\binom{n+k}{k} counts DFmarked balanced n-paths containing n − 2k marked vertices and satisfying the property: for each ascent, its length minus its number of marked vertices is even. Start with a row of n upsteps. They determine n + 1 gaps: the n − 1 gaps between them and a gap at each end. Choose 2k + 1 of these gaps — \binom{n+1}{2k+1} choices — and label them G_{1}, G_{2}, …, G_{2k+1} from left to right. Insert a mark in each of the remaining n − 2k gaps. Distribute n downsteps arbitrarily among the odd-labeled gaps, that is, among gaps G_{1}, G_{3}, G_{5}, …, G_{2k+1} — \binom{n+k}{k} choices — and concatenate to form a typical path of the type specified. An example with n = 8, k = 2 is illustrated (slanted lines represent the upsteps).

[figure: G_{1}; G_{2}; G_{3}; G_{4}; G_{5}; •; •; •; •]

Say 3 Ds go into gap G_{1}, 1 D goes into G_{3} and 4 Ds go into G_{5}. (In general, of course, some of these gaps might remain empty.) Then the resulting DFmarked path is

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

Here is a bijection from these marked paths to (plain) balanced n-paths, that sends marks to odd-length ascents. Given such a marked path, first erase the marks (if any) on vertices at ground level. Each vertex V above ground level has a matching vertex in the path: the first one encountered directly east of V. For each marked vertex V above ground level, delete the upstep starting at V and reinsert it at V ’s matching vertex (without the mark). Do likewise for marked vertices below ground level, replacing the word “east” by “west”. The path illustrated above yields (transferred steps shown in green merely as a visual aid)

[figure: ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

The transferred steps above ground level appear in the image path as the initial steps of odd-length ascents above ground level that do not start the path. Similarly, transferred steps below ground level appear in the image path as the terminal steps of odd-length ascents below ground level that do not end the path. The erased marks at ground level correspond to odd-length ascents that either cross ground level or start or end the path. Hence this map sends “# marks” to “# odd-length ascents” and is invertible. From §3 we conclude that \frac{1}{n+1} \binom{n+1}{2k+1}\binom{n+k}{k} counts Dyck n-paths with n − 2k odd-length ascents.

An ordered tree on n edges corresponds to a Dyck n-path under an obvious bijection: burrow up all edges from the root and open out accordion-style so that each edge produces an upstep and matching downstep, as illustrated.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; ⟶; root; numbered upsteps are hill-producing; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ordered tree; Dyck path; 1; 2; 3; 4; 1; 2; 3; 4]

Each non-root vertex in the tree has a unique parent edge: the first one on the path to the root. The parent edges of nodes ( = non-root non-leaf vertices) that are adjacent to a leaf, numbered in the illustration, correspond to upsteps U in the Dyck path with the following property: the Dyck subpath lying strictly between U and its matching D contains at least one hill. We’ll call such a U a hill-producing upstep.

Now consider placing nonoverlapping dimers (dominos), each the length of two steps, to cover as many upsteps as possible in a Dyck path. They can all be covered except for one upstep in each odd-length ascent. Clearly, the number of odd-length ascents in a Dyck n-path has the same parity (even or odd) as n. Hence, if this number is n − 2k, then k dimers can be placed. Thus we have shown that the number of Dyck n-paths accommodating k dimers on the upsteps is \frac{1}{n+1} \binom{n+1}{2k+1}\binom{n+k}{k}. In the next section we exhibit a bijection on Dyck paths that sends # accommodated dimers to # hill-producing upsteps. As we have seen, the latter correspond to nodes adjacent to a leaf in an ordered tree, and the result follows.

9. The Dimer to Hill-Producing Upstep Bijection

Here we define a bijection, ϕ, on Dyck n-paths that sends # accommodated dimers to # hill-producing upsteps. Our definition of ϕ is recursive and it is convenient to introduce a little more notation. A strict Dyck path is a Dyck path with exactly one return to ground level (necessarily at the end of the path). In particular, a strict Dyck path is nonempty. The interior of a strict Dyck path is the Dyck path obtained by deleting its initial upstep and terminal downstep. Every nonempty Dyck path is representable uniquely as a concatenation of one or more strict Dyck paths, called its components. We abbreviate first ascent length as FAL. The interior of the first component of a nonempty Dyck path P is denoted I(P), and I^{2}(P) = I(I(P)) and so on. Thus if P has FAL = k, then I^{j}(P) ≠ ϵ for 1 ≤ j ≤ k − 1 and I^{k}(P) = ϵ. Recall a Dyck path is Fine if it contains no hills (peaks at level 1); otherwise it is Hill.

Now define ϕ ϵ = ϵ, ϕ UD = UD, and for nonstrict P with components P_{1}, …, P_{k} (k ≥ 2), ϕP = ϕP_{1} ϕP_{2} … ϕP_{k}. It remains to define ϕ on strict Dyck paths with FAL ≥ 2 and the image is another strict Dyck path of the same size. Thus, in particular, ϕ preserves the Fine property of a path. In the Table below, the left column partitions strict Dyck paths with FAL ≥ 2 into six classes (four with FAL even and two with FAL odd). The right column lists properties that (as we will see) distinguish the image classes. The diagrams following the Table define ϕ on each of the six classes in terms of ϕ acting on smaller paths.

Case  ϕ : P ⟶ Q

FAL of P is even and: I(Q) is Hill and:

1.  I(P) is Fine  I^{2}(Q) is Hill
2.  I(P) is Hill, I^{2}(P) = ϵ  I^{2}(Q) = ϵ
3. I(P) is Hill, I^{2}(P) ≠ ϵ is Fine I^{2}(Q) ≠ ϵ is Fine, I^{3}(Q) is Hill
4. I(P) is Hill, I^{2}(P) ≠ ϵ is Hill I^{2}(Q) ≠ ϵ is Fine, I^{3}(Q) is Fine

FAL of P is odd and: I(Q) is nonempty Fine and:

5.  I(P) is Fine  I^{2}(Q) is Hill
6.  I(P) is Hill  I^{2}(Q) is Fine

Classification of strict Dyck paths for the bijection ϕ

[FAL = first ascent length, I(P) denotes interior of first component of P]

We note in passing that, restricted to the paths in the top two boxes, ϕ is a bijection between two known manifestations of the Fine numbers [5, p. 263].

In the diagrammed paths, P_{1}, P_{2}, … represent Dyck paths subject only to the restrictions specified. Case 1.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; P_{1}; P_{2}; ⟶; ϕP_{1}; ϕP_{2}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P_{1} ≠ ϵ has FAL even; P_{2} is Fine]

Case 2.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; P_{2}; ⟶; ϕP_{2}; •; •; •; •; •; •; •; •; •; •; •; •]

Case 3.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; P_{1}; P_{2}; ⟶; ϕP_{1}; ϕP_{2}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; P_{1} ≠ ϵ has FAL even; P_{1} is Fine, P_{2} is Hill]

Case 4.

[figure: .....; .....; .....; .....; .....; .....; .....; P_{1}; ⟶; ϕP_{1}; •; •; •; •; •; •; •; •; P_{1} has FAL odd, P_{1}; and I(P_{1}) both Hill]

Case 5.

[figure: .....; .....; .....; .....; .....; .....; .....; P_{1}; ⟶; ϕP_{1}; •; •; •; •; •; •; •; •; P_{1} has FAL even; and is Fine]

Case 6.

[figure: ^{.....}; ^{.....}; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; …; …; P_{0}; P_{1}; P_{ℓ}; ⟶; ϕP_{0}; ϕP_{1}; ϕP_{ℓ}; 0; 1; ℓ; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ℓ ≥ 1, P_{0} ≠ ϵ has FAL even; P_{0}, P_{1}, …, P_{ℓ} all Fine]

By induction, ϕ sends paths with FAL even (resp. odd) to paths whose first component has an interior with (resp. without) hills, and the classification of image paths in the Table follows. Only in Case 1 is the form of the image path not obviously unique and the hill displayed in that case is recovered as the last hill in the interior of the image since ϕ sends Fine paths to Fine paths. So an inverse for ϕ can be recursively defined by reversing everything.

To establish the key property of ϕ, let ν(P) = # dimers accommodated by P, and μ(P) = # hill-producing upsteps in P. It is easy to verify by induction that ν(P) = μ(ϕP). For example, in Case 1, ν(P) = 1 (due to initial UU) + ν(P_{1}) + ν(P_{2}) while μ(ϕP) = 1 (the first U is hill-producing) + μ(ϕP_{1}) + μ(ϕP_{2}) and induction establishes this case. The others are similar. This completes the proof.

10. Touchard for the Fine Numbers

Touchard’s Catalan number identity,

C_{n} = ∑_{k≥0} \binom{n − 1}{2k}2^{n−1−2k}C_{k},

counts Dyck n-paths by number k of long noninitial ascents. Here we show that the identity

F_{n} = \frac{1}{n + 1} ∑_{k≥0} \binom{n − 2 − k}{k} 2^{n−2−2k}\binom{n + 1}{k + 1}

counts Fine n-paths by the same statistic.

The initial ascent of a nonempty Fine path is always long; so it suffices to show that \frac{1}{n+1} \binom{n−1−k}{k−1}\binom{n−2k}{j}\binom{n+1}{k} is the number of Fine n-paths with j short ascents and k long ascents, and then sum over j. To show this, with IA again short for interior ascent, define an IAmarked balanced (n, j, k)-path to be a balanced n-path with k long ascents and j marked IA vertices. An IAmarked balanced path is Fine-like if it contains no short ascents (and thus every ascent has at least one interior vertex) and the first interior vertex of each ascent is not marked.

The number of Fine-like IAmarked balanced (n, j, k)-paths is \binom{n−1−k}{k−1}\binom{n−2k}{j}\binom{n+1}{k} as follows: start with a row of n upsteps. From the n − 1 gaps between them, choose k nonconsecutive gaps including the first one — \binom{n−k−1}{k−1} choices — to serve as the first interior vertices of the ascents. Choose j gaps for marks from the n − 2k gaps available (the k originally chosen gaps and their immediate predecessors are not available) — \binom{n−2k}{j} choices. Finally, distribute n Ds among the k gaps preceding the originally chosen gaps and the “gap” after the last upstep, with at least one D in each gap save possibly the first and last of them — \binom{n+1}{k} choices — to get a typical path of the type being counted.

Again from §3 we have that there are \frac{1}{n+1} \binom{n−1−k}{k−1}\binom{n−2k}{j}\binom{n+1}{k} Fine-like IAmarked Dyck (n, j, k)-paths. Now we exhibit a bijection from Fine-like IAmarked Dyck paths to (plain) Fine paths that preserves size of path and number of long ascents, and turns marks into short ascents. An example with n = 12 upsteps, j = 3 marks, and k = 4 long ascents is illustrated below. For each marked vertex v, take the upstep U terminating at v, locate the matching downstep D for U, and transfer U to the initial vertex of D (erasing the mark) as indicated by the arrows in the top figure.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; ↓; Fine-like IA Dyck path; •; •; •; ——; ↗; •; ————–; ↗; ———————————————————; ↗; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; Fine path; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

The transferred steps can be recovered as the short ascents in the image path. To reverse the map, delete each short ascent U and reinsert it with a mark on its top vertex at the initial vertex of the associated upstep (as defined in §2) of the downstep preceding U. Note that, as in the example, several upsteps may be reinserted at the same vertex. This completes the proof.

Acknowledgment

I thank an anonymous referee for a very detailed review, for suggesting the inclusion of analytic proofs and for supplying them, and for several helpful remarks.

References

[1] David Callan, Pair them up!: A visual approach to the Chung-Feller theorem, College Mathematics Journal 26 (1995) 196–198.

[2] David Callan, Polygon Dissections and Marked Dyck Paths, 2005, preprint.

[3] Emeric Deutsch, A bijective proof of the equation linking the Schröder numbers, large and small. Discrete Math. 241 (2001), no. 1-3, 235–240.

[4] Robert Sulanke, Constraint-sensitive Catalan path statistics having the Narayana distribution, Discrete Math. 204 (1999), 397–414.

[5] Emeric Deutsch and Louis Shapiro, A survey of the Fine numbers, Discrete Math. 241 (2001), 241–265.

[6] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999. Exercise 6.19 and related material on Catalan numbers are available online at

http://www-math.mit.edu/~rstan/ec/.

[7] Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math. 204 (1999), 163–166.

[8] Jack Levine, Note on the number of pairs of non-intersecting routes, Scripta Math. 24 (1959), 335– 338.

[9] Ira M. Gessel and Xavier G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

[10] Martin Aigner and Günter M. Ziegler, Proofs from the book, 3rd ed., Springer, 2003.

[11] Emeric Deutsch and Louis Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Discrete Math. 256 (2002), 655–670.