TAOCP 7.2.1.3 Exercise 76

The function $\kappa_t N$ arises from the combinatorial number system in which an integer $N$ is written uniquely in the form N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, with...

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.3: Generating All Combinations

Exercise 76. [M20] [M20] Find a simple formula for κt(N + 1) −κtN.

Verified: no
Solve time: 13m43s

Solution

The function $\kappa_t N$ arises from the combinatorial number system in which an integer $N$ is written uniquely in the form

$$ N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, $$

with strictly decreasing upper indices, as developed in the preceding exercises. In this representation, $\kappa_t N$ is the largest upper index that appears in the degree-$t$ component of this expansion, equivalently the first term in the chain $\kappa_k \kappa_{k+1} \cdots \kappa_t N$ of equation (60) when $k=t$.

Thus $\kappa_t N$ is the inverse of the partial sums of binomial coefficients in the sense that it records the unique integer $n$ such that $N$ lies in the interval

$$ \binom{n}{t} \le N < \binom{n+1}{t}, $$

with the convention that equality at the left endpoint corresponds to the left-closed boundary of the interval decomposition of the nonnegative integers by $t$-combinations.

Let $n=\kappa_t N$. Then by definition,

$$ \binom{n}{t} \le N < \binom{n+1}{t}. $$

The behavior of $\kappa_t$ under increment of $N$ depends on whether $N+1$ crosses the boundary $\binom{n+1}{t}$.

If $N+1 < \binom{n+1}{t}$, then both $N$ and $N+1$ lie in the same interval determined by $n$, hence

$$ \kappa_t(N+1)=\kappa_t N=n, $$

so the difference is $0$.

If $N+1 = \binom{n+1}{t}$, then $N$ lies in the interval for $n$, while $N+1$ lies at the left endpoint of the next interval, which corresponds to $n+1$, hence

$$ \kappa_t(N)=n,\qquad \kappa_t(N+1)=n+1, $$

so the difference is $1$.

The case $N+1 > \binom{n+1}{t}$ cannot occur under the defining property of $n$, since $N < \binom{n+1}{t}$ implies $N+1 \le \binom{n+1}{t}$.

The increment therefore occurs exactly at those $N$ for which $N+1$ is a pure binomial boundary of order $t$, that is when $N+1=\binom{m}{t}$ for some integer $m$.

This yields the closed form

$$ \kappa_t(N+1)-\kappa_t N = \begin{cases} 1, & \text{if } N+1=\binom{m}{t}\text{ for some integer } m,\[6pt] 0, & \text{otherwise}. \end{cases} $$

This completes the solution. ∎