TAOCP 7.2.1.3 Exercise 41

For real $x \ge t-1$, define the generalized binomial coefficients \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.1.3: Generating All Combinations

Exercise 41. [M27] [M27] Show that there is a permutation c(0), c(1), c(2), . . . of the nonnegative integers such that the elements of Chase’s sequence Cst are obtained by complementing the least significant s + t bits of the elements c(k) for 0 ≤k < 2s+t that have weight ν(c(k)) = s. (Thus the sequence ¯c(0), . . . , ¯c(2n −1) contains, as subsequences, all of the Cst for which s + t = n, just as Gray binary code g(0), . . . , g(2n −1) contains all the revolving-door sequences Γst.) Explain how to compute the binary representation c(k) = ( . . . a2a1a0)2 from the binary representation k = ( . . . b2b1b0)2.

Verified: no
Solve time: 5m04s

Setup

For real $x \ge t-1$, define the generalized binomial coefficients

$$ \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!}, \qquad \binom{x}{t-1} = \frac{x(x-1)\cdots(x-t+2)}{(t-1)!}. $$

The function $x \mapsto \binom{x}{t}$ is strictly increasing on $[t-1,\infty)$ since

$$ \frac{\binom{x+1}{t}}{\binom{x}{t}} = \frac{x+1}{x-t+1} > 1 \quad (x \ge t-1). $$

Hence for each integer $N \ge 0$ there exists a unique real $x \ge t-1$ such that

$$ N = \binom{x}{t}. $$

Define the real-valued function

$$ \kappa_t^{(\mathbb{R})}(N) = \binom{x}{t-1} \quad \text{where } N = \binom{x}{t}. $$

Let the integer version $\kappa_t^{(\mathbb{Z})}(N)$ be defined as follows: choose the unique integer $m \ge t-1$ such that

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

and set

$$ \kappa_t^{(\mathbb{Z})}(N) = \binom{m}{t-1}. $$

The goal is to prove

$$ \kappa_t^{(\mathbb{R})}(N) \ge \kappa_t^{(\mathbb{Z})}(N) \quad \text{for all integers } t \ge 1, ; N \ge 0. $$

Equality holds when $x$ is an integer.

Solution

Fix $t \ge 1$ and $N \ge 0$. Let $x \ge t-1$ be the unique real number such that

$$ N = \binom{x}{t}. $$

Let $m$ be the integer determined by

$$ \binom{m}{t} \le \binom{x}{t} < \binom{m+1}{t}. $$

Since $x \mapsto \binom{x}{t}$ is strictly increasing on $[t-1,\infty)$, the inequality

$$ \binom{m}{t} \le \binom{x}{t} $$

implies $m \le x$, and the strict monotonicity forces $m \le x < m+1$.

Thus

$$ m \le x. $$

Consider the function

$$ f(x) = \binom{x}{t-1}. $$

For $x \ge t-1$, compute the ratio

$$ \frac{f(x+1)}{f(x)} = \frac{\binom{x+1}{t-1}}{\binom{x}{t-1}} = \frac{x+1}{x-t+2}. $$

Since $x \ge t-1$, one has $x+1 \ge t$ and $x-t+2 \le x+1$, hence

$$ \frac{x+1}{x-t+2} > 1, $$

so $f(x)$ is strictly increasing on $[t-1,\infty)$.

From $m \le x$ and monotonicity of $f$, it follows that

$$ \binom{m}{t-1} \le \binom{x}{t-1}. $$

Substituting definitions gives

$$ \kappa_t^{(\mathbb{Z})}(N) \le \kappa_t^{(\mathbb{R})}(N). $$

If $x$ is an integer, then necessarily $x=m$, so equality holds.

This completes the proof. ∎

Verification

The argument uses only two monotonicity facts, both derived directly from explicit ratios of generalized binomial coefficients. The inequality $m \le x$ follows from strict monotonicity of $\binom{x}{t}$ on $[t-1,\infty)$, and the comparison of $\kappa$ values reduces to monotonicity of $\binom{x}{t-1}$. No additional assumptions are used.