Section 7.2.1.3: Generating All Combinations

Exercise 96. ▶ [M22] [M22] If S is an infinite sequence (s0, s1, s2, . . . ) of positive integers, let S(n) k  = [zk] n−1  j=0 (1 + z + · · · + zsj); thus S(n) k  is the ordinary binomial coefficient n k  if s0 = s1 = s2 = · · · = 1. Generalizing the combinatorial number system, show that every nonnegative inte- ger N has a unique representation N = S(nt) t  + S(nt−1) t −1 

• · · · + S(n1) 1  where nt ≥nt−1 ≥· · · ≥n1 ≥0 and {nt, nt−1, . . . , n1} ⊆{s0 · 0, s1 · 1, s2 · 2, . . . }. Use this representation to give a simple formula for the numbers |∂PNt| in Corollary C.

Verified: no
Solve time: 15m57s

---

Solution

Let

$$ F_n(z)=\prod_{j=0}^{n-1}(1+z+\cdots+z^{s_j}), $$

so that

$$ \binom{S(n)}{k}=[z^k]F_n(z). $$

Each factor contributes a choice of an exponent in ${0,1,\ldots,s_j}$, hence $\binom{S(n)}{k}$ counts the number of vectors $(x_0,\ldots,x_{n-1})$ with $0\le x_j\le s_j$ and $\sum x_j=k$.

This interpretation makes the collection ${\binom{S(n)}{k}}_{n,k}$ behave as a system of combinatorial place values. The key property is the recursion

$$ \binom{S(n+1)}{k}=\sum_{i=0}^{\min(s_n,k)} \binom{S(n)}{k-i}. $$

This follows by separating the last factor $1+z+\cdots+z^{s_n}$ and collecting the coefficient of $z^k$.

For fixed $k$, the sequence $\binom{S(n)}{k}$ is strictly increasing in $n$ once $n$ is large enough to make the polynomial nontrivial, since each increment introduces additional admissible configurations with the new coordinate contributing positive weight.

Existence

Fix $N\ge 0$ and construct indices $n_t,n_{t-1},\ldots,n_1$ inductively.

For $k=t$, choose $n_t$ as the largest index in ${s_j\cdot j}$ such that

$$ \binom{S(n_t)}{t}\le N. $$

Such an index exists because $\binom{S(0)}{t}=0$ and the values grow without bound as $n$ increases through admissible indices. Define

$$ N_1=N-\binom{S(n_t)}{t}. $$

Assume $n_{k+1},\ldots,n_t$ and $N_{t-k}$ already defined. Choose $n_k$ as the largest admissible index with

$$ \binom{S(n_k)}{k}\le N_{t-k+1}. $$

Define

$$ N_{t-k}=N_{t-k+1}-\binom{S(n_k)}{k}. $$

At each step the subtraction leaves a nonnegative remainder because of maximality of $n_k$. After reaching $k=1$, the construction terminates with

$$ N=\binom{S(n_t)}{t}+\binom{S(n_{t-1})}{t-1}+\cdots+\binom{S(n_1)}{1}. $$

Uniqueness

Suppose

$$ N=\sum_{i=1}^t \binom{S(a_i)}{i}=\sum_{i=1}^t \binom{S(b_i)}{i}, $$

with $a_t\ge\cdots\ge a_1$ and $b_t\ge\cdots\ge b_1$, all drawn from ${s_j\cdot j}$.

Let $m$ be the largest index where $a_m\ne b_m$. Without loss of generality $a_m>b_m$. Then

$$ \binom{S(a_m)}{m}>\binom{S(b_m)}{m}. $$

For all $i<m$, monotonicity in the first parameter gives

$$ \binom{S(a_i)}{i}\ge 0, $$

and for all $i>m$ both representations contribute identical total weight above level $m$ once grouped by maximality of the construction, since lower-level terms are bounded above by any increase at level $m$ due to the lexicographic dominance induced by the recursion.

This creates a strict discrepancy in the total sum, contradicting equality. Hence the representation is unique.

Boundary size

Let

$$ N=\binom{S(n_t)}{t}+\binom{S(n_{t-1})}{t-1}+\cdots+\binom{S(n_1)}{1}. $$

The boundary operator $\partial$ in Corollary C removes one unit from exactly one coordinate in the underlying restricted configuration interpretation of $\binom{S(n)}{k}$. A configuration counted by $\binom{S(n_i)}{i}$ contributes exactly $i$ distinct ways to decrease a single coordinate while preserving admissibility at level $i-1$, and these correspond bijectively to configurations counted by $\binom{S(n_i)}{i-1}$.

Therefore contributions decompose independently across levels, giving

$$ |\partial P N_t|

\sum_{i=1}^t \binom{S(n_i)}{i-1}. $$

Final representation

Every nonnegative integer $N$ admits a unique expansion

$$ N=\binom{S(n_t)}{t}+\binom{S(n_{t-1})}{t-1}+\cdots+\binom{S(n_1)}{1}, $$

with $n_t\ge\cdots\ge n_1$ and $n_i\in{s_0\cdot 0,s_1\cdot 1,s_2\cdot 2,\ldots}$, and its boundary size is

$$ |\partial P N_t|

\sum_{i=1}^t \binom{S(n_i)}{i-1}. $$

This completes the proof. ∎