TAOCP 1.2.6 Exercise 56

For each $n$, choose $a$ as large as possible subject to $\binom{a}{3}\le n$.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.6: Binomial Coefficients

Exercise 56. [20] (The combinatorial number system.) For each integer $n=0,1,2,\ldots,20$, find three integers $a,b,c$ for which

$$ n=\binom{a}{3}+\binom{b}{2}+\binom{c}{1}, \qquad a>b>c\ge 0. $$

Verified: no
Solve time: -

Solution

For each $n$, choose $a$ as large as possible subject to $\binom{a}{3}\le n$. Then choose $b$ as large as possible subject to

$$ \binom{a}{3}+\binom{b}{2}\le n, $$

and finally let

$$ c=n-\binom{a}{3}-\binom{b}{2}. $$

Since $\binom{c}{1}=c$, this gives the desired representation. The inequalities $a>b>c\ge0$ hold in every case.

Using

$$ \binom{0}{3}=0,\quad \binom{1}{3}=0,\quad \binom{2}{3}=0,\quad \binom{3}{3}=1,\quad \binom{4}{3}=4,\quad \binom{5}{3}=10,\quad \binom{6}{3}=20, $$

and

$$ \binom{0}{2}=0,\quad \binom{1}{2}=0,\quad \binom{2}{2}=1,\quad \binom{3}{2}=3,\quad \binom{4}{2}=6,\quad \binom{5}{2}=10, $$

we obtain:

$$ \begin{aligned} 0&=\binom{3}{3}+\binom{2}{2}+\binom{0}{1},\ 1&=\binom{3}{3}+\binom{2}{2}+\binom{1}{1},\ 2&=\binom{3}{3}+\binom{3}{2}+\binom{0}{1},\ 3&=\binom{3}{3}+\binom{3}{2}+\binom{1}{1},\ 4&=\binom{4}{3}+\binom{2}{2}+\binom{0}{1},\ 5&=\binom{4}{3}+\binom{2}{2}+\binom{1}{1},\ 6&=\binom{4}{3}+\binom{3}{2}+\binom{0}{1},\ 7&=\binom{4}{3}+\binom{3}{2}+\binom{1}{1},\ 8&=\binom{4}{3}+\binom{3}{2}+\binom{2}{1},\ 9&=\binom{4}{3}+\binom{4}{2}+\binom{0}{1},\ 10&=\binom{5}{3}+\binom{2}{2}+\binom{0}{1},\ 11&=\binom{5}{3}+\binom{2}{2}+\binom{1}{1},\ 12&=\binom{5}{3}+\binom{3}{2}+\binom{0}{1},\ 13&=\binom{5}{3}+\binom{3}{2}+\binom{1}{1},\ 14&=\binom{5}{3}+\binom{3}{2}+\binom{2}{1},\ 15&=\binom{5}{3}+\binom{4}{2}+\binom{0}{1},\ 16&=\binom{5}{3}+\binom{4}{2}+\binom{1}{1},\ 17&=\binom{5}{3}+\binom{4}{2}+\binom{2}{1},\ 18&=\binom{5}{3}+\binom{4}{2}+\binom{3}{1},\ 19&=\binom{5}{3}+\binom{5}{2}+\binom{0}{1},\ 20&=\binom{6}{3}+\binom{2}{2}+\binom{0}{1}. \end{aligned} $$

Hence the required triples $(a,b,c)$ are

$$ \begin{array}{c|c} n&(a,b,c)\ \hline 0&(3,2,0)\ 1&(3,2,1)\ 2&(3,3,0)\text{ impossible} \end{array} $$

The condition $a>b$ excludes $n=2$ from the preceding line, so we must instead write

$$ 2=\binom{4}{3}+\binom{0}{2}+\binom{-2}{1}, $$

which violates $c\ge0$. Therefore we reconsider the first representations so that the inequalities are always strict.

A correct complete list is:

$$ \begin{array}{c|c} n&(a,b,c)\ \hline 0&(2,1,0)\ 1&(3,1,0)\ 2&(3,2,0)\ 3&(3,2,1)\ 4&(4,1,0)\ 5&(4,2,0)\ 6&(4,2,1)\ 7&(4,3,0)\ 8&(4,3,1)\ 9&(4,3,2)\ 10&(5,1,0)\ 11&(5,2,0)\ 12&(5,2,1)\ 13&(5,3,0)\ 14&(5,3,1)\ 15&(5,3,2)\ 16&(5,4,0)\ 17&(5,4,1)\ 18&(5,4,2)\ 19&(5,4,3)\ 20&(6,1,0) \end{array} $$

since each line satisfies

$$ n=\binom{a}{3}+\binom{b}{2}+\binom{c}{1}, \qquad a>b>c\ge0. $$

Therefore the representations are

$$ \boxed{ \begin{array}{c|c} 0&(2,1,0)\ 1&(3,1,0)\ 2&(3,2,0)\ 3&(3,2,1)\ 4&(4,1,0)\ 5&(4,2,0)\ 6&(4,2,1)\ 7&(4,3,0)\ 8&(4,3,1)\ 9&(4,3,2)\ 10&(5,1,0)\ 11&(5,2,0)\ 12&(5,2,1)\ 13&(5,3,0)\ 14&(5,3,1)\ 15&(5,3,2)\ 16&(5,4,0)\ 17&(5,4,1)\ 18&(5,4,2)\ 19&(5,4,3)\ 20&(6,1,0) \end{array}} $$