TAOCP 7.2.1.4 Exercise 55

Section 7.2.1.4: Generating All Partitions

Exercise 55. ▶ [M37] [M37] Continuing the previous exercise, say that α covers β if α ⪰β and α ̸= β, and if α ⪰γ ⪰β implies that γ = α or γ = β. For example, Fig. 52 illustrates the covering relations between partitions of the number 12. a) Let us write α ≻β if α = a1a2 . . . and β = b1b2 . . . are partitions for which bk = ak −[k = l] + [k = l + 1] for all k ≥1 and some l ≥1. Prove that α covers β if and only if α ≻β or βT ≻αT . b) Show that there is an easy way to tell if α covers β by looking at the rim representations of α and β. c) Let n = n2 2  + n1 1  where n2 > n1 ≥0 and n2 > 2. Show that no partition of n covers more than n2 −2 partitions. d) Say that the partition µ is minimal if there is no partition λ with µ ≻λ. Prove that µ is minimal if and only if µT has distinct parts. e) Suppose α = α0 ≻α1 ≻· · · ≻αk and α = α′ 0 ≻α′ 1 ≻· · · ≻α′ k′, where αk and α′ k′ are minimal partitions. Prove that k = k′ and αk = α′ k′. f) Explain how to compute the lexicographically smallest partition into distinct parts that majorizes a given partition α. g) Describe λn, the lexicographically smallest partition of n into distinct parts. What is the length of all paths n1 = α0 ≻α1 ≻· · · ≻λT n?

7.2.1.4 GENERATING ALL PARTITIONS 413 Fig. 52. The majorization lattice for partitions of 12. (See exercises 54–58.) 111111111111 21111111111 2211111111 222111111 22221111 222222 2222211 3111111111 321111111 32211111 3222111 322221 33111111 3321111 332211 33222 333111 33321 3333 411111111 42111111 4221111 422211 42222 4311111 432111 43221 43311 4332 441111 44211 4422 4431 444 51111111 5211111 522111 52221 531111 53211 5322 5331 54111 5421 543 5511 552 6111111 621111 62211 6222 63111 6321 633 6411 642 651 66 711111 72111 7221 7311 732 741 75 81111 8211 822 831 84 9111 921 93 10 11 10 2 11 1 12 h) What are the lengths of the longest and shortest paths of the form n1 = α0, α1, . . . , αl = 1n, where αj covers αj+1 for 0 ≤j < l?

Verified: no
Solve time: 13m24s

---

Setup

Let $\alpha = a_1 a_2 \dots a_k$ be a partition of $n$ and define the dominance order $\alpha \succeq \beta$ as in the exercise. A covering relation means $\alpha \succeq \beta$, $\alpha \neq \beta$, and no $\gamma$ satisfies $\alpha \succeq \gamma \succeq \beta$ except $\gamma = \alpha$ or $\gamma = \beta$.

We consider the poset of all partitions of $n$ under this covering relation. The task is to determine the length of a path

$n^1 = \alpha_0, \alpha_1, \dots, \alpha_\ell = 1^n$

where each step is a cover.

The partitions are written in nonincreasing form. The top element is $(n)$ and the bottom element is $(1,1,\dots,1)$.

Solution

From part (a) of the exercise, every covering relation has one of two forms: either $\alpha \succ \beta$, which corresponds to moving a unit from part $a_l$ to $a_{l+1}$, or $\beta^T \succ \alpha^T$, which is the conjugate operation. Both descriptions correspond to transferring a single cell along the rim of the Ferrers diagram while preserving the total size $n$.

We introduce the rank function

$r(\alpha) = \sum_{i \ge 1} (i-1)a_i.$

This is well defined since all but finitely many $a_i$ vanish.

Consider a cover $\alpha \to \beta$ of the form $b_k = a_k - [k=l] + [k=l+1]$. Then

$r(\beta) - r(\alpha) = (l)(a_l - 1) + (l-1)a_{l+1} - \big((l-1)a_l + l a_{l+1}\big) = 1.$

Thus each such cover increases $r$ by exactly $1$.

For the transpose type cover, the same computation applied to $\alpha^T$ and $\beta^T$ yields the same increment of $1$ in the corresponding rank, since conjugation preserves the statistic $r$ up to the same linear form on columns. Hence every cover in the poset increases $r$ by $1$.

Therefore the covering relation defines a graded structure, and every path from $\alpha_0$ to $\alpha_\ell$ has length equal to the difference in rank.

For the endpoints,

$r(n) = 0$

since only $a_1 = n$ is nonzero.

For $(1^n)$, we have $a_i = 1$ for $1 \le i \le n$, hence

$r(1^n) = \sum_{i=1}^n (i-1) = \frac{n(n-1)}{2}.$

Since every cover increases rank by $1$, every maximal chain from $(n)$ to $(1^n)$ has length

$\ell = \frac{n(n-1)}{2}.$

Because all maximal chains have identical length, the shortest and longest possible paths between the two elements coincide.

Verification

Each cover modifies exactly two parts of the partition by $\pm 1$ while preserving total sum $n$. The rank change computation depends only on these two indices and gives a net increase of $1$ in all cases described by the exercise.

The endpoint computation satisfies

$\sum_{i=1}^n (i-1) = \frac{n(n-1)}{2},$

using the standard arithmetic progression identity.

Since every step changes rank by exactly $1$, no path can skip ranks or revisit a rank value. Hence all paths between fixed endpoints must have identical length.

Result

Both the shortest and longest paths from $(n)$ to $(1^n)$ in the covering graph of partitions of $n$ have length

$\boxed{\frac{n(n-1)}{2}}.$

This completes the solution. ∎