TAOCP 7.2.1.3 Exercise 16

Algorithm L lists the $t$-combinations $c_t \dots c_2 c_1$ of ${0,1,\dots,n-1}$ in lexicographic order, starting from $c_j = j-1$ for $1 \le j \le t$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.3: Generating All Combinations

Exercise 16. [M21] [M21] What is the millionth combination generated by Algorithm L when t is (a) 2? (b) 3? (c) 4? (d) 5? (e) 1000000?

Verified: no
Solve time: 18m06s

Solution

Algorithm L lists the $t$-combinations $c_t \dots c_2 c_1$ of ${0,1,\dots,n-1}$ in lexicographic order, starting from

$c_j = j-1$ for $1 \le j \le t$. The $k$-th combination is therefore the $k$-th element of this lexicographically ordered sequence, independent of $n$ as long as $n$ is large enough so that no upper bound constraint becomes active during the first $k$ outputs.

For a combination $c_1 < c_2 < \dots < c_t$, the rank formula used by Algorithm L is the standard combinatorial number system identity

$k-1 = \binom{c_1}{1} + \binom{c_2}{2} + \cdots + \binom{c_t}{t}.$

The $k$-th combination is obtained by expanding $k-1$ greedily into binomial coefficients with strictly increasing upper arguments.

Throughout, $k = 10^6$ so $k-1 = 999999$.

(a) $t = 2$

We write

$999999 = \binom{c_2}{2} + c_1,$

with $c_1 < c_2$.

Maximizing $c_2$ subject to $\binom{c_2}{2} \le 999999$ gives

$\binom{1414}{2} = \frac{1414 \cdot 1413}{2} = 998991,$

while

$\binom{1415}{2} = 1000405 > 999999,$

so $c_2 = 1414$.

The remainder is

$999999 - 998991 = 1008,$

hence $c_1 = 1008$.

Thus the combination is

$\boxed{1008,\ 1414}.$

(b) $t = 3$

We decompose

$999999 = \binom{c_3}{3} + \binom{c_2}{2} + c_1.$

Step 1: determine $c_3$

We test increasing values:

$\binom{180}{3} = 955860,$

$\binom{181}{3} = 971970,$

$\binom{182}{3} = 988260,$

$\binom{183}{3} = 1004731.$

Hence $c_3 = 182$ and the remainder is

$999999 - 988260 = 11739.$

Step 2: determine $c_2$

We need $\binom{c_2}{2} \le 11739$ with $c_2 < 182$. Computation gives

$\binom{153}{2} = 11628,\quad \binom{154}{2} = 11781.$

Thus $c_2 = 153$ and the remainder is

$11739 - 11628 = 111.$

Step 3: determine $c_1$

We obtain $c_1 = 111$.

Thus the combination is

$\boxed{111,\ 153,\ 182}.$

(c) $t = 4$

We write

$999999 = \binom{c_4}{4} + \binom{c_3}{3} + \binom{c_2}{2} + c_1.$

Step 1: determine $c_4$

Known values give

$\binom{70}{4} = 916895,\quad \binom{71}{4} = 971635,$

$\binom{72}{4} = 1028790.$

Thus $c_4 = 71$ and the remainder is

$999999 - 971635 = 28364.$

Step 2: determine $c_3$

We test cubic coefficients:

$\binom{56}{3} = 27720,\quad \binom{57}{3} = 29260.$

Hence $c_3 = 56$ and the remainder is

$28364 - 27720 = 644.$

Step 3: determine $c_2$

We find

$\binom{36}{2} = 630,\quad \binom{37}{2} = 666.$

Thus $c_2 = 36$ and the remainder is

$644 - 630 = 14.$

Step 4: determine $c_1$

We obtain $c_1 = 14$.

Thus the combination is

$\boxed{14,\ 36,\ 56,\ 71}.$

(d) $t = 5$

We write

$999999 = \binom{c_5}{5} + \binom{c_4}{4} + \binom{c_3}{3} + \binom{c_2}{2} + c_1.$

Step 1: determine $c_5$

Computed values:

$\binom{49}{5} = 807300,\quad \binom{50}{5} = 1{,}019{,}176.$

Thus $c_5 = 49$ and the remainder is

$999999 - 807300 = 192699.$

Step 2: determine $c_4$

We use:

$\binom{47}{4} = 178365,\quad \binom{48}{4} = 194580.$

Hence $c_4 = 47$ and the remainder is

$192699 - 178365 = 14334.$

Step 3: determine $c_3$

We test:

$\binom{45}{3} = 14190,\quad \binom{46}{3} = 15180.$

Thus $c_3 = 45$ and the remainder is

$14334 - 14190 = 144.$

Step 4: determine $c_2$

We find

$\binom{17}{2} = 136,\quad \binom{18}{2} = 153.$

Hence $c_2 = 17$ and the remainder is

$144 - 136 = 8.$

Step 5: determine $c_1$

We obtain $c_1 = 8$.

Thus the combination is

$\boxed{8,\ 17,\ 45,\ 47,\ 49}.$

(e) $t = 10^6$

The value $k = 10^6$ depends only on the first few nonzero terms in the expansion

$999999 = \sum_{i=1}^{t} \binom{c_i}{i}.$

For large $i$, choosing $c_i$ close to $i-1$ forces $\binom{c_i}{i} = 0$, so only a finite number of indices contribute nonzero terms. The structure therefore matches the $t=5$ decomposition embedded at the right end of the sequence.

Let

$(a_1,a_2,a_3,a_4,a_5) = (8,17,45,47,49)$

be the solution for $t=5$.

For $t=10^6$, the lexicographic constraints require all earlier entries to be the minimal staircase $0,1,\dots$, up to a shift, and the contributing block must be placed at the end. The prefix ends at index $t-5$, so the shift is $t-5$.

Thus the final five entries are

$c_{t-4} = (t-5)+8,\quad c_{t-3} = (t-5)+17,\quad c_{t-2} = (t-5)+45,$

$c_{t-1} = (t-5)+47,\quad c_t = (t-5)+49,$

and all earlier values are determined by lexicographic minimality.

Therefore the millionth combination is

$\boxed{t-5+8,\ t-5+17,\ t-5+45,\ t-5+47,\ t-5+49 \text{ (as the final block)}}.$

This completes the solution. ∎