TAOCP 2.3.4.6 Exercise 3

Label the vertices of the convex $n$-gon by $1,2,\dots,n$ in cyclic order.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.6: History and Bibliography

Exercise 3. [**] [M30] Consider all ways of partitioning the vertices of a convex $n$-gon into $k$ nonempty parts, in such a way that no diagonal between two vertices of one part crosses a diagonal between two vertices of another part.

a) Find a one-to-one correspondence between noncrossing partitions and an interesting class of tree structures.

b) Given $n$ and $k$, how many ways are there to make such a partition?

Verified: no
Solve time: 4m01s

Label the vertices of the convex $n$-gon by $1,2,\dots,n$ in cyclic order.

A noncrossing partition means that if $a,b$ lie in one block and $c,d$ lie in another block with $a<c<b<d$ in cyclic order, then this configuration is forbidden. Equivalently, convex hulls of distinct blocks do not intersect in their interiors.

(a) Correct tree structure and bijection

Let $\mathcal{P}$ be a noncrossing partition of ${1,\dots,n}$.

Step 1: Convex-hull laminar structure

For each block $B \in \mathcal{P}$, let $\operatorname{conv}(B)$ be its convex hull in the polygon.

A standard and crucial fact for noncrossing partitions of points on a circle is:

For any two blocks $B_1,B_2$, their convex hulls are either disjoint or one is contained in the other.

This follows directly from the noncrossing condition: if the hulls intersect without containment, then one can find alternating vertices $a<c<b<d$ with $a,b\in B_1$ and $c,d\in B_2$, producing crossing diagonals.

Hence the family ${\operatorname{conv}(B)}$ forms a laminar family of convex sets.

Step 2: Define the tree

Construct a graph $T$ as follows.

  • Vertices of $T$:

  • one vertex for each block $B \in \mathcal{P}$,

  • one additional vertex $r$ representing the exterior of the polygon.

  • Edges:

  • For each block $B$, define its parent as the unique minimal block $C$ (if it exists) such that

$$ \operatorname{conv}(B) \subsetneq \operatorname{conv}(C). $$

  • If no such $C$ exists, connect $B$ to the root $r$.
  • Add one edge from each block to its parent.

Step 3: Well-definedness

We must justify:

Uniqueness of parent.

If $B$ is strictly contained in two blocks $C_1,C_2$, then their convex hulls intersect and neither contains the other, contradicting laminarity. Hence at most one minimal containing block exists.

Existence of root attachment.

Blocks not contained in any other block connect to $r$.

Thus each block has exactly one parent.

Step 4: $T$ is a tree

  • Each vertex except $r$ has exactly one parent, so the number of edges is $|\mathcal{P}|$.
  • There are $|\mathcal{P}|+1$ vertices total.
  • Hence if $T$ is connected, it must be a tree.

Connectivity.

Starting from any block $B$, repeatedly move to its parent. This strictly increases convex hull inclusion, and there are finitely many blocks, so the process terminates at $r$. Thus every vertex connects to $r$, so the graph is connected.

Therefore $T$ is connected with $|V|-1$ edges, hence acyclic. So $T$ is a tree.

Step 5: Plane tree structure

Around each block $B$, the incident children correspond to maximal sub-blocks contained in the “gaps” between consecutive vertices of $B$ on the circle. These inherit a cyclic order from the polygon. Thus $T$ is naturally a rooted plane tree.

Step 6: Bijection

  • From a partition, we constructed a unique tree $T$.
  • From such a tree, we recover the partition by assigning each polygon vertex $i$ to the unique block corresponding to the smallest convex-hull node whose region contains $i$.

This reconstruction is well-defined because the nesting structure partitions the disk into regions indexed by tree nodes.

Thus the correspondence is bijective.

(b) Enumeration

Fix vertex $1$. Let its block have size $m \ge 1$. Write its elements in cyclic order:

$$ 1 = a_1 < a_2 < \cdots < a_m. $$

Step 1: Decomposition into intervals

The vertices between consecutive $a_i, a_{i+1}$ form $m$ disjoint cyclic intervals around the polygon:

$$ I_1, I_2, \dots, I_m. $$

Noncrossing implies:

  • each interval $I_j$ is independent,
  • each carries an arbitrary noncrossing partition,
  • total structure is a product of $m$ smaller noncrossing partitions.

Let $N_{n,k}$ be the number of noncrossing partitions of $n$ vertices into $k$ blocks.

Then for fixed $m$,

$$ N_{n,k} = \sum_{m \ge 1} \sum_{\substack{k_1+\cdots+k_m = k-1}} \prod_{j=1}^m N_{|I_j|,k_j}. $$

This recursion is the standard Catalan-type decomposition.

Step 2: Closed form

It is known (and follows from solving the above convolution via generating functions or Lagrange inversion) that

$$ N_{n,k} $$

satisfies the Narayana distribution.

The generating function $C(x)$ for Catalan structures satisfies

$$ C(x) = 1 + x C(x)^2, $$

and refinement by number of blocks yields Narayana numbers.

The resulting closed form is

$$ N_{n,k} = \frac{1}{n}\binom{n}{k}\binom{n}{k-1}. $$

Final answers

(a)

Noncrossing partitions correspond bijectively to rooted plane trees obtained from the laminar inclusion structure of convex hulls of blocks: each block is a node, edges connect each block to its minimal containing block (or the exterior root), yielding a rooted plane tree.

(b)

The number of such partitions is

$$ \boxed{\frac{1}{n}\binom{n}{k}\binom{n}{k-1}}. $$