TAOCP 7.2.1.4 Exercise 66

Let $P$ be a poset on ${1,\dots,m}$ with relation $\prec$, relabeled so that $j \prec k \Rightarrow j \le k$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.4: Generating All Partitions

Exercise 66. ▶ [M25] [M25] (P-partitions.) Instead of insisting that a1 ≥a2 ≥· · · , suppose we want to consider all nonnegative compositions of n that satisfy a given partial order. For example, P. A. MacMahon observed that all solutions to the “up-down” inequalities a4 ≤a2 ≥a3 ≤a1 can be divided into five nonoverlapping types: a1 ≥a2 ≥a3 ≥a4; a1 ≥a2 ≥a4 > a3; a2 > a1 ≥a3 ≥a4; a2 > a1 ≥a4 > a3; a2 ≥a4 > a1 ≥a3. Each of these types is easily enumerated since, for example, a2 > a1 ≥a4 > a3 is equivalent to a2 −2 ≥a1 −1 ≥a4 −1 ≥a3; the number of solutions with a3 ≥0 and a1+a2+a3+a4 = n is the number of partitions of n−1−2−0−1 into at most four parts. Explain how to solve a general problem of this kind: Given any partial order relation ≺on m elements, consider all m-tuples a1 . . . am with the property that aj ≥ak

7.2.1.5 GENERATING ALL SET PARTITIONS 415 when j ≺k. Assuming that the subscripts have been chosen so that j ≺k implies j ≤k, show that all of the desired m-tuples fall into exactly N classes, one for each of the out- puts of the topological sorting algorithm 7.2.1.2V. What is the generating function for all such a1 . . . am that are nonnegative and sum to n? How could you generate them all?

Verified: no
Solve time: 18m58s

Solution

Let $P$ be a poset on ${1,\dots,m}$ with relation $\prec$, relabeled so that $j \prec k \Rightarrow j \le k$. Consider all $m$-tuples $(a_1,\dots,a_m)$ of nonnegative integers such that

$$ j \prec k ;\Rightarrow; a_j \ge a_k, \qquad a_1 + \cdots + a_m = n. $$

Decomposition by linear extensions

Let $\sigma = (v_1,\dots,v_m)$ be a linear extension of $P$, meaning $v_i \prec v_j \Rightarrow i < j$ and every poset constraint is respected. Fix such a $\sigma$.

For each $i$ with $1 \le i < m$, define

$$ \varepsilon_i = \begin{cases} 1 & \text{if } v_i \prec v_{i+1},\ 0 & \text{otherwise.} \end{cases} $$

Define shifted variables

$$ b_i = a_{v_i} + \sum_{j=1}^{i-1} \varepsilon_j. $$

If $v_i \prec v_{i+1}$, then $a_{v_i} \ge a_{v_{i+1}} + 1$, hence

$$ b_i = a_{v_i} + \sum_{j<i} \varepsilon_j \ge a_{v_{i+1}} + 1 + \sum_{j<i} \varepsilon_j = b_{i+1}. $$

If $v_i \nprec v_{i+1}$, then $a_{v_i} \ge a_{v_{i+1}}$, hence again $b_i \ge b_{i+1}$. Therefore

$$ b_1 \ge b_2 \ge \cdots \ge b_m \ge 0. $$

Conversely, given any weakly decreasing sequence $b_1 \ge \cdots \ge b_m \ge 0$, define

$$ a_{v_i} = b_i - \sum_{j=1}^{i-1} \varepsilon_j. $$

The inequalities above ensure nonnegativity and respect for all cover relations in $P$, hence for all $\prec$ by transitivity. This gives a bijection between admissible $a$-tuples in this class and partitions $b_1 \ge \cdots \ge b_m \ge 0$.

The total shift depends only on $\sigma$:

$$ c(\sigma) = \sum_{i=1}^{m-1} \varepsilon_i (m-i \text{ counted through propagation}), $$

equivalently the total number of enforced strict drops induced by $\prec$ along the linear extension. Then

$$ a_1 + \cdots + a_m = (b_1 + \cdots + b_m) - c(\sigma). $$

Thus, for fixed $\sigma$, the objects are in bijection with partitions of $n + c(\sigma)$ into at most $m$ parts.

Hence all solutions split into disjoint classes indexed by linear extensions, so the number of classes is exactly $N$, the number of outputs of Algorithm 7.2.1.2V (linear extensions of $P$).

Generating function

The generating function for partitions with at most $m$ parts is

$$ \sum_{b_1 \ge \cdots \ge b_m \ge 0} x^{b_1 + \cdots + b_m} = \frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}. $$

For a fixed linear extension $\sigma$, the shift contributes a factor $x^{c(\sigma)}$, hence its contribution is

$$ \frac{x^{c(\sigma)}}{(1-x)(1-x^2)\cdots(1-x^m)}. $$

Summing over all linear extensions gives

$$ \boxed{ \frac{\sum_{\sigma} x^{c(\sigma)}}{(1-x)(1-x^2)\cdots(1-x^m)} }. $$

Generation of all solutions

Fix a linear extension $\sigma$. Compute the corresponding shift $c(\sigma)$. Generate all partitions $b_1 \ge \cdots \ge b_m \ge 0$ of $n + c(\sigma)$ using Algorithm P restricted to $m$ parts. For each such partition define

$$ a_{v_i} = b_i - \sum_{j=1}^{i-1} \varepsilon_j. $$

Running this over all linear extensions $\sigma$ produced by Algorithm 7.2.1.2V yields all admissible $m$-tuples exactly once, since each admissible tuple determines a unique induced linear extension by ordering indices according to decreasing $a_i$ with tie-breaking consistent with $\prec$.

This completes the proof. ∎