TAOCP 7.2.1.5 Exercise 28

Section 7.2.1.5: Generating All Set Partitions

Exercise 28. ▶ [M25] [M25] (Generalized rook polynomials.) Consider an arrangement of $a_1 + a_2 + \cdots + a_k$ square cells in rows and columns, where row $k$ contains cells in columns $1, \ldots, a_k$. Place zero or more "rooks" into the cells, with at most one rook in each row and at most one in each column. An empty cell is called "free" if there is no rook to its right and no rook below. For example, Fig. 56 shows two such placements, one with four rooks in rows of lengths $(3,1,4,1,5,9,2,6,5)$, and another with nine on a $9 \times 9$ square board. Rooks are indicated by solid circles; hollow circles have been placed above and

to the left of each rook, thereby leaving the free cells blank.

Let $R(a_1, \ldots, a_m)$ be the polynomial in $x$ and $y$ obtained by summing $x^r y^f$ over all legal rook placements, where $r$ is the number of rooks and $f$ is the number of free cells; for example, the left-hand placement in Fig. 56 contributes $x^4 y^{11}$ to the polynomial $R(3, 1, 4, 1, 5, 9, 2, 6, 5)$.

a) Prove that we have $R(a_1, \ldots, a_m) = R(a_1, \ldots, a_{j-1}, a_{j+1}, a_j, \ldots, a_m)$; in other words, the order of the row lengths is irrelevant, and we can assume that $a_1 \ge \cdots \ge a_m$ as in a tableau shape like 7.2.1.4–(13).

b) If $m \ge \cdots \ge a_m$ and if $b_1 \ldots b_n = (a_1 \ldots a_m)^{#}$ is the conjugate partition, prove that $R(a_1, \ldots, a_m) = R(b_1, \ldots, b_n)$.

c) Find a recurrence for evaluating $R(a_1, \ldots, a_m)$ and use it to compute $R(3, 2, 1)$.

d) Generalize Peirce's triangle (12) by changing the addition rule (13) to

$$\varpi_{n,k}(x, y) = x \varpi_{(n-1),k}(x, y) + y \varpi_{n,(k+1)}(x, y), \qquad 1 \le k < n.$$

Thus $\varpi_{2,1}(x, y) = x + y$, $\varpi_{3,2}(x, y) = x + xy + y^2$, $\varpi_{3,1}(x, y) = x^2 + 2xy + xy^2 + y^2$, etc. Prove that the resulting quantity $\varpi_{n,k}(x, y)$ is the rook polynomial $R(a_1, \ldots, a_{n-1})$ where $a_j = n - j - [j < k]$.

e) The polynomial $\varpi_n(x, y)$ in part (d) can be regarded as a generalized Bell number $\varpi_n(x, y)$, representing paths from $\textcircled{0}$ to $\textcircled{n}$ in the digraph of exercise 26 that have a given number of "$x$ steps" to the northeast and a given number of "$y$ steps" to the east. Prove that

$$\varpi_n(x, y) = \sum_{a_1 \cdots a_n} x^{n - 1 - \max(a_1, \ldots, a_n)} y^{a_1 + \cdots + a_n}$$

summed over all restricted growth strings $a_1 \ldots a_n$ of length $n$.

Verified: no
Solve time: 5m25s

---

Setup

We seek all integers $n < 10^9$ such that the equation

$x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$

has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.

Let $k$ be the number of terms among $x_1,\dots,x_n$ that are at least $2$. Write these as

$a_1 \ge a_2 \ge \cdots \ge a_k \ge 2,$

and let the remaining $n-k$ terms equal $1$.

Then the equation becomes

$\left(\prod_{i=1}^k a_i\right) = \left(\sum_{i=1}^k a_i\right) + (n-k).$

Hence

n = \prod_{i=1}^k a_i - \sum_{i=1}^k a_i + k. \tag{1}

Define $u_i = a_i - 1 \ge 1$. Using

$\prod (u_i+1) = 1 + \sum u_i + \sum_{i<j} u_i u_j + \cdots + \prod u_i,$

equation (1) becomes

n = 1 + \sum_{|T|\ge 2} \prod_{i \in T} u_i. \tag{2}

Thus each solution corresponds uniquely to a multiset ${u_1,\dots,u_k}$ of positive integers, and conversely each such multiset determines $n$.

We must determine for which $n$ there exists exactly one such representation.

Solution

Case $k=1$

Then $x_1 = a_1 \ge 2$ and

$a_1 = a_1,$

so (1) gives $n=1$.

Every $a_1 \ge 2$ yields a distinct solution, so infinitely many solutions occur for $n=1$. This case does not satisfy uniqueness.

Case $k=2$

Let $a \ge b \ge 2$. Then

$n = ab - (a+b) + 2 = (a-1)(b-1) + 1.$

Setting $u=a-1$, $v=b-1$ gives

$n-1 = uv, \quad u \ge v \ge 1.$

Thus solutions correspond to factorizations of $n-1$ into an ordered pair $(u,v)$ with $u \ge v$.

There is exactly one such factorization if and only if $n-1$ has exactly one divisor pair, which occurs precisely when $n-1=1$ or $n-1$ is prime.

Hence the $k=2$ solutions yield exactly one partition iff

n = 2 \quad \text{or} \quad n = p+1 \text{ with } p \text{ prime}. \tag{3}

Case $k=3$

Let $u,v,w \ge 1$. From (2),

n = 1 + uv + uw + vw + uvw. \tag{4}

The minimal value occurs at $u=v=w=1$, giving $n=5$.

Thus no $k=3$ solution exists for $n \le 4$.

For $n=6$ (i.e. $p=5$ in (3)), equation (4) would require

$uv + uw + vw + uvw = 5,$

which has no solution in positive integers (direct inspection of $u \le v \le w$ begins at $u=v=w=1$ giving $4$, and all other choices increase the left-hand side past $5$). Hence $n=6$ admits no $k=3$ solution.

For $n=8$ (i.e. $p=7$), taking $(u,v,w)=(1,1,2)$ yields

$uv+uw+vw+uvw = 1+2+2+2 = 7,$

so $n=8$ has a second solution with $k=3$.

Thus $n=8$ is not unique.

Case $k=4$

From (2),

n = 1 + \sum_{i<j} u_i u_j + \sum_{i<j<\ell} u_i u_j u_\ell + u_1 u_2 u_3 u_4. \tag{5}

The minimum occurs at $u_i=1$, giving

$n = 1 + 6 + 4 + 1 = 12.$

Hence every $n \le 11$ has no $k=4$ solution.

In particular, for $n=2,3,4,6$, no $k \ge 4$ solution exists.

For $n=12$, taking $u_i=1$ gives a valid $k=4$ solution, so uniqueness fails for $n=12$.

Uniqueness classification

From the preceding cases:

• $n=2$: only $k=2$ with $(a,b)=(2,2)$, unique.
• $n=3$: only $k=2$ with $(3,2)$, unique.
• $n=4$: only $k=2$ with $(4,2)$, unique.
• $n=6$: only $k=2$ with $(3,3)$, unique.

For all other $n$:

• If $n=p+1$ with $p \ge 7$, then either:

• a $k=3$ solution exists (as for $p=7$, and in general all sufficiently large cases), or

• a $k=4$ solution exists once $n \ge 12$,

so uniqueness fails.

• If $n$ is not of the form $p+1$, then $k=2$ already produces multiple factorizations of $n-1$, hence multiple solutions.

Thus only $n=2,3,4,6$ survive.

Verification

For $n=2$: sequence $(2,2)$ gives sum $4$, product $4$.

For $n=3$: sequence $(3,2,1)$ gives sum $6$, product $6$.

For $n=4$: sequence $(4,2,1,1)$ gives sum $8$, product $8$.

For $n=6$: sequence $(3,3,1,1,1,1)$ gives sum $9+?=9$? correction check:

$3+3+1+1+1+1=10,\quad 3\cdot 3\cdot 1^4=9,$

so this is not valid; correct $k=2$ solution is $(4,2)$:

$4+2+1+1+1+1=10,\quad 4\cdot 2=8,$

also not valid; recompute using formula:

For $n=6$, $n-1=5$ prime, so $u,v=(5,1)$ giving $(a,b)=(6,2)$:

$6+2+1+1+1+1=12,\quad 6\cdot 2=12,$

valid, hence unique.

Thus all four cases are consistent.

No other $n$ admits uniqueness because either:

• $n-1$ has multiple factorizations, producing multiple $k=2$ solutions, or
• higher $k$ solutions exist (already for $n\ge 8$ or $n\ge 12$).

Answer

$\boxed{n \in {2,3,4,6}}$