TAOCP 7.2.1.3 Exercise 40

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-medium

Section 7.2.1.3: Generating All Combinations

Exercise 40. [M22] [M22] What is the millionth combination in Chase’s sequence Cst, when s = 12 and t = 14?

Verified: no
Solve time: 5m16s

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.