TAOCP 7.2.1.5 Exercise 63

Section 7.2.1.5: Generating All Set Partitions

Exercise 63. ▶ [M35] (J. Pitman.) Prove that there is an elementary way to locate the maximum Stirling numbers, and many similar quantities, as follows: Suppose $0 \le p_k \le 1$.

a) Let $f(z) = (1 + p_1(z-1)) \cdots (1 + p_n(z-1))$ and $a_k = [z^k] f(z)$; thus $a_k$ is the probability that $k$ heads turn up after $n$ independent coin flips with the respective probabilities $p_1, \ldots, p_n$. Prove that $a_{k-1} < a_k$ whenever $k \le \mu = p_1 + \cdots + p_n$, $a_k \ne 0$.

b) Similarly, prove that $a_{k+1} < a_k$ whenever $k \ge \mu$ and $a_k \ne 0$.

c) If $f(z) = a_0 + a_1 z + \cdots + a_n z^n$ is an arbitrary nonzero polynomial with nonnegative coefficients and with $n$ real roots, prove that $a_{k-1} < a_k$ when $k \le \mu$ and $a_{k+1} < a_k$ when $k \ge \mu$, where $\mu = f'(1)/f(1)$. (Therefore if $a_m = \max(a_0, \ldots, a_n)$ we must have either $m = \lfloor \mu \rfloor$ or $m = \lceil \mu \rceil$.)

d) Under the hypotheses of (c), and with $a_j = 0$ when $j < 0$ or $j > n$, show that there are indices $s \le t$, such that $a_{s-1} = a_{s} < a_{s+1} < \cdots < a_t > a_{t+1} = a_{t+2}$, or show that if $s \le k \le t$ then the sequence $(a_0, a_1, \ldots, a_n)$ is always "bell-shaped.")

e) What do these results tell us about Stirling numbers?

Verified: no
Solve time: 5m42s

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}}$