TAOCP 5.1.3 Exercise 27

Let \(F(n,k)\) denote the number of increasing forests on the vertex set \(\{1,2,\dots,n\}\) that have exactly \(k+1\) leaves.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.3: Runs

Exercise 27. ▶ [M21] An increasing forest is an oriented forest in which the nodes are labeled ${1, 2, \ldots, n}$ such that parents have smaller numbers than their children. Show that $\binom{n}{k}$ is the number of $n$-node increasing forests with $k + 1$ leaves.

Verified: yes
Solve time: 13m49s

Solution

Let (F(n,k)) denote the number of increasing forests on the vertex set ({1,2,\dots,n}) that have exactly (k+1) leaves. For (n=0) we define (F(0,0)=1) and (F(0,k)=0) for (k\ne0), matching the convention (\left\langle 0 \atop k \right\rangle = \delta_{k0}).

For (n\ge 1), consider an increasing forest (T) on ({1,\dots,n}). The vertex (n) is the largest label, so it cannot have children; it is either a root (a tree consisting solely of (n)) or a child of some vertex (i<n). Removing (n) yields an increasing forest (T') on ({1,\dots,n-1}). Let (L(T)) and (L(T')) be the numbers of leaves of (T) and (T'), respectively. There are three cases:

  1. (n) is a root. Then (L(T)=L(T')+1).
  2. (n) is a child of a leaf of (T'). That leaf ceases to be a leaf, so (L(T)=L(T')).
  3. (n) is a child of a non-leaf of (T'). Then (L(T)=L(T')+1).

Given (T') with (L') leaves, the number of ways to attach (n) is:

  • as a root: (1) way,
  • as a child of a leaf: (L') ways,
  • as a child of a non-leaf: ((n-1)-L') ways.

Thus from a forest (T') with (L') leaves we obtain forests (T) with

  • (L = L'+1) leaves in (1 + (n-1-L') = n-L') ways,
  • (L = L') leaves in (L') ways.

We want (L = k+1). Hence (T') must have either (L'=k+1) leaves (and we attach (n) to a leaf, in (k+1) ways) or (L'=k) leaves (and we attach (n) as a root or to a non-leaf, in (n-k) ways). This gives the recurrence [ F(n,k) = (k+1)F(n-1,k) + (n-k)F(n-1,k-1),\qquad n\ge1, ] with the understanding that (F(m,k)=0) for (k<0) or (k>m).

Comparing with the definition of the Eulerian numbers (\left\langle n \atop k \right\rangle) in the text (equations (2) and (3)), we see that (F(n,k)) satisfies exactly the same recurrence and boundary conditions. Therefore [ F(n,k) = \left\langle n \atop k \right\rangle ] for all (n\ge0) and (k\ge0).

In other words, the number of (n)-node increasing forests with (k+1) leaves is the Eulerian number (\left\langle n \atop k \right\rangle).

This completes the proof. ∎