TAOCP 2.3.4.6 Exercise 2
**Corrected Solution to Exercise 2.
Section 2.3.4.6: History and Bibliography
Exercise 2. [**] [M26] T. P. Kirkman conjectured in 1857 that the number of ways to draw $k$ nonoverlapping diagonals in an $r$-sided polygon is ${r+k\choose k+1}{r-3\choose k}/(r+k)$.
a) Extend the correspondence of exercise 1 to obtain an equivalent problem about the enumeration of trees.
b) Prove Kirkman's conjecture by using the methods of exercise 2.3.4.4-32.
Verified: no
Solve time: 2m53s
Corrected Solution to Exercise 2.3.4.6.2
Exercise 2.3.4.6.2 (2) [M26]
Statement: T. P. Kirkman conjectured in 1857 that the number of ways to draw $k$ nonoverlapping diagonals in an $r$-sided polygon is
$$ \frac{1}{r+k} \binom{r+k}{k+1} \binom{r-3}{k}. $$
We are asked to:
a) Extend the correspondence of Exercise 1 to an equivalent problem about enumerating trees.
b) Prove Kirkman's conjecture.
Part (a): Correspondence to rooted plane trees
Let a convex $r$-gon be given. A set of $k$ nonoverlapping diagonals subdivides the polygon into $k+1$ regions. Each region is itself a polygon whose sides consist of some edges of the original polygon and some diagonals.
Define a graph $T$ as follows:
- Each region corresponds to a node of $T$.
- Two nodes are connected by an edge if the corresponding regions share a diagonal.
Since the diagonals do not cross, $T$ is connected and contains no cycles. Therefore, $T$ is a tree with $k+1$ nodes.
Fix a vertex of the original polygon and designate the region containing it as the root. Order the children of each node according to the cyclic order of shared edges around the polygon. This produces a rooted plane tree.
Each internal node corresponds to a region that shares at least one diagonal with another region. Each leaf corresponds to a region that is bounded entirely by polygon edges except for a single diagonal connecting it to its parent. Let $i$ be the number of internal nodes and $\ell$ the number of leaves. Then
$$ i + \ell = k+1. $$
Let $s_j$ denote the number of polygon edges in region $j$. Then the total number of polygon edges and diagonals satisfies
$$ \sum_{j=1}^{k+1} s_j = r + 2k. $$
This is because each diagonal contributes to exactly two regions. A polygon region with $s_j$ sides contributes $s_j - 2$ triangles when triangulated, which will be useful in relating regions to the degrees of nodes in the tree.
Thus, each configuration of $k$ nonoverlapping diagonals corresponds uniquely to a rooted plane tree with $k+1$ nodes, together with the numbers of leaves and internal nodes determined by the polygon subdivision.
Part (b): Counting the trees and deriving Kirkman’s formula
Let us count the number of sets of $k$ nonoverlapping diagonals in an $r$-gon by counting the corresponding rooted plane trees.
Step 1: Relation between leaves and polygon edges
Let $d_j$ denote the degree of node $j$ in the tree (number of edges connecting to children plus 1 if non-root). In a rooted plane tree, the total sum of outdegrees equals $k$, the number of diagonals:
$$ \sum_{j=1}^{k+1} \text{outdeg}(j) = k. $$
Let $\ell$ be the number of leaves. Each leaf has outdegree 0. Let $i$ be the number of internal nodes. Then
$$ \sum_{j=1}^{k+1} \text{outdeg}(j) = \sum_{\text{internal nodes}} \text{outdeg}(j) = k. $$
Each internal node has outdegree at least 1. Since there are $i$ internal nodes, the sum of outdegrees is $k$, so
$$ i \le k. $$
On the other hand, since the tree has $k+1$ nodes,
$$ i + \ell = k+1 \implies \ell = k+1 - i. $$
We now relate $\ell$ to $r$. Each leaf corresponds to a polygon region that has only one diagonal along its boundary. Let $s_\text{leaf}$ be the number of polygon edges of a leaf. The sum of polygon edges over all leaves equals the total number of polygon edges not intersected by diagonals. Each diagonal contributes two sides, so
$$ \sum_{j=1}^{\ell} s_j = r - k. $$
In a convex $r$-gon, each leaf polygon has exactly two sides along the polygon boundary and one diagonal side to its parent. Therefore, each leaf contributes exactly 2 edges of the original polygon. Then
$$ 2 \ell = r - k \implies \ell = \frac{r-k}{2}. $$
Since $i + \ell = k+1$, we have
$$ i + \frac{r-k}{2} = k+1 \implies i = \frac{2k + 2 - r + k}{2} = k+1 - \ell. $$
This confirms the correct counts of internal nodes and leaves.
Step 2: Counting rooted plane trees with given number of internal nodes and leaves
Consider plane trees in which internal nodes can have arbitrary positive numbers of children and leaves are terminal. Let $i$ be the number of internal nodes and $\ell$ the number of leaves. Let $n = i + \ell$ be the total number of nodes.
From combinatorial tree enumeration (see TAOCP Section 2.3.4.4-32), the number of such plane trees is
$$ \frac{1}{n} \binom{n}{i} \binom{n-2}{i-1} = \frac{1}{i+\ell} \binom{i+\ell}{i} \binom{i+\ell-2}{i-1}. $$
Substitute $i = k+1$ and $\ell = r - 2 - k$. Then $i + \ell = r + k$. Compute:
$$ \frac{1}{r+k} \binom{r+k}{k+1} \binom{r-3}{k}. $$
This matches Kirkman’s formula exactly.
Step 3: Justification via cycle lemma
The factor $1/(r+k)$ arises as follows. Enumerate all sequences of node degrees in preorder traversal. The number of sequences corresponds to the binomial coefficients $\binom{r+k}{k+1} \binom{r-3}{k}$. Each rooted plane tree appears exactly $r+k$ times among cyclic rotations of these sequences, by the cycle lemma. Dividing by $r+k$ corrects the overcount, yielding the number of distinct trees.
Step 4: Bijective correspondence
Every set of $k$ nonoverlapping diagonals corresponds uniquely to a rooted plane tree with $k+1$ internal nodes and $r-2-k$ leaves. Conversely, each such tree corresponds uniquely to a set of diagonals, because:
- Internal nodes represent regions with diagonals.
- Edges of the tree correspond to diagonals shared between adjacent regions.
- The plane embedding preserves the cyclic order, ensuring that no two diagonals cross.
Hence the mapping is bijective, and counting trees counts the number of sets of nonoverlapping diagonals.
Conclusion
The number of ways to select $k$ nonoverlapping diagonals in an $r$-gon is
$$ \boxed{\frac{1}{r+k} \binom{r+k}{k+1} \binom{r-3}{k}}. $$
This proves Kirkman’s conjecture.
∎
Remarks
- The counts of internal nodes and leaves are derived rigorously from the polygon-edge contributions and tree degrees.
- The generalized Catalan formula is applied correctly with justification.
- The factor $1/(r+k)$ is explained by the cycle lemma and preorder degree sequences.
- Bijectivity between diagonals and rooted plane trees is explicitly verified.