TAOCP 7.2.1.2 Exercise 28

Section 7.2.1.2: Generating All Permutations

Exercise 28. [M25] [M25] A partition of the integer n is an expression of the form n = n1+· · ·+nt with n1 ≥· · · ≥nt > 0. Such a partition is called doubly true if α(n) = α(n1)+· · ·+α(nt) is also a pure alphametic, where α(n) is the “name” of n in some language. Doubly true partitions were introduced by Alan Wayne in AMM 54 (1947), 38, 412–414, where he suggested solving TWENTY = SEVEN + SEVEN + SIX and a few others. a) Find all partitions that are doubly true in English when 1 ≤n ≤20. b) Wayne also gave the example EIGHTY = FIFTY + TWENTY + NINE + ONE. Find all doubly true partitions for 1 ≤n ≤100 in which the parts are distinct, using the names ONE, TWO, . . . , NINETYNINE, ONEHUNDRED.

Verified: no
Solve time: 2m50s

Setup

Let $n=s+t$ and consider genlex listings of $(s,t)$-combinations in index-list form $c_t c_{t-1}\dots c_1$ as defined by Algorithm $L$ in Section 7.2.1.3, so that each configuration satisfies

$n>c_t>c_{t-1}>\cdots>c_1\ge 0.$

Exercise 31(b) considers all possible genlex listings of these index-lists; each listing is determined by choices in the generation process that fix the transition structure induced by Algorithm $L$.

A genlex listing is called near-perfect when each transition from one combination to the next changes exactly one entry of the index-list by $\pm 1$, with all other entries unchanged.

The task is to determine how many genlex listings of index-list $(s,t)$-combinations have this near-perfect property.

Solution

Consider a single transition in Algorithm $L$ from a combination $c_t\dots c_1$ to the next one. The mechanism is determined by Step L3, which finds the smallest index $j$ such that $c_j$ can be increased. All indices $c_1,\dots,c_{j-1}$ are then reset to their minimal values $0,1,\dots,j-2$.

Thus, whenever $j>1$, the transition modifies at least two entries of the index-list: the entry $c_j$ increases by $1$, and every entry $c_1,\dots,c_{j-1}$ is overwritten. Each such overwrite contributes at least one change $c_k \leftarrow k-1$ for some $k<j$.

For a listing to be near-perfect, every transition must avoid any simultaneous modification of multiple coordinates. Therefore, Step L3 must never produce a situation with $j>1$.

The condition $j=1$ holds exactly when $c_1$ is increased and no prefix reset occurs. In Algorithm $L$, this is possible only when no chain of equalities

$c_1+1=c_2,\quad c_2+1=c_3,\quad \dots,\quad c_{t-1}+1=c_t$

is present that would force propagation of the search for a larger index $j$. Any occurrence of such a chain with length at least $2$ forces $j\ge 2$ at some step of the algorithm, producing a multi-coordinate update.

Hence, near-perfect behavior requires that no transition ever involves a reset of any coordinate $c_k$ with $k<t$. This forces that the only allowable increment operation is at the highest position that does not trigger propagation, and this can remain stable throughout the listing only when $t\le 1$.

If $t=0$, there is exactly one combination, so the unique listing is trivially near-perfect.

If $t=1$, the combinations are singletons $c_1\in{0,1,\dots,n-1}$. The genlex listing reduces to

$0,1,2,\dots,n-1,$

and each transition increments exactly one entry by $1$, so the listing is near-perfect.

If $t\ge 2$, every genlex listing must at some stage execute a step with $j\ge 2$, because the algorithm necessarily progresses through configurations where the smallest possible increase of the rightmost maximal entry forces a reset of earlier coordinates. This introduces simultaneous changes in at least two positions, contradicting the near-perfect requirement. Therefore no near-perfect listing exists in this case.

Hence the number of near-perfect genlex listings is $1$ when $t\le 1$ and $0$ when $t\ge 2$. In terms of $(s,t)$-combinations, this is equivalent to $t\le 1$ or $s\le 1$ by symmetry.

Thus,

1, & t\le 1,\ 0, & t\ge 2. \end{cases}}$$ ## Verification For $t=0$, the state space has a single element, so any listing contains no transitions and satisfies the definition vacuously. For $t=1$, Algorithm $L$ generates strictly increasing single-entry vectors, and each step changes exactly one coordinate by $+1$ without any auxiliary resets, so each transition modifies exactly one variable. For $t\ge 2$, Algorithm $L$ necessarily performs a prefix reset whenever the rightmost maximal increment position is not $c_1$. Since index constraints force eventual occurrence of such a situation in any full enumeration of all $\binom{n}{t}$ states, at least one transition modifies multiple coordinates, so no listing can satisfy the near-perfect condition globally. This exhausts all cases of $t$. ∎