TAOCP 7.2.1.6 Exercise 26

Section 7.2.1.6: Generating All Trees

Exercise 26. [M31] [M31] (The Kreweras lattice.) Let $F$ and $F'$ be $n$-node forests with their nodes numbered 1 to $n$ in preorder. We write $F \prec F'$ ($F$ coalesces $F''$) if $j$ and $k$ are siblings in $F$ whenever they are siblings in $F'$, for $1 \le j < k \le n$. Figure 60 illustrates this partial ordering in the case $n = 4$; each forest is encoded by the sequence $c_1 \ldots c_n$ of (11) and (15), which specifies the depth of each node. (With this encoding, $j$ and $k$ are siblings if and only if $c_j = c_k \le c_{j+1}, \ldots, c_{k-1}$.)

a) Let $\Pi$ be a partition of ${1, \ldots, n}$. Show that there exists a forest $F$, with nodes labeled $(1, \ldots, n)$ in preorder and with

$$j \equiv k \pmod{\Pi} \iff j \text{ is a sibling of } k \text{ in } F,$$

if and only if $\Pi$ satisfies the noncrossing property

$$i < j < k < l \text{ and } i \equiv k \pmod{\Pi} \text{ and } j \equiv l \pmod{\Pi} \implies i \equiv j \equiv k \equiv l \pmod{\Pi}.$$

b) Given any two $n$-node forests $F'$ and $F''$, explain how to compute their least upper bound $F \vee F'$, the element such that $F \prec G$ and $F'' \prec G$ if and only if $F \vee F'' \prec G$.

c) Show that if $F'$ covers $F$, it has exactly one less leaf than $F$.

d) Show that if $F'$ covers $F$, when node $k$ has $c_k$ children for $1 \le k \le n$?

e) How many forests cover $F$, when node $k$ has $c_k$ children for $1 \le k \le n$?

f) Using the definition of duality in exercise 19, what is the dual of the forest $(2)$?

g) Prove that $F \prec F'$ holds if and only if $F^D \prec F^{\prime D}$. (Because of this property, dual elements have been placed symmetrically in the center of Fig. 60.) h) Given any two $n$-node forests $F$ and $F'$, explain how to compute their greatest lower bound $F \wedge F'$; that is, $G \preccurlyeq F$ and $G \preccurlyeq F'$ if and only if $G \preccurlyeq F \wedge F'$. i) Does this lattice satisfy a semimodular law analogous to exercise 7.1.5–12(f)?

Verified: no
Solve time: 6m10s

---

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