Chapter 6: Binomial Coefficients and Identities

Why Does Choosing a Team in Two Stages Yield Vandermonde's Identity?

Suppose a company needs to form a three-person project team from a pool of seven volunteers: three designers ($D_1, D_2, D_3$) and four engineers ($E_1, E_2, E_3, E_4$). All seven people are distinct, the two groups are disjoint, and the team has no assigned internal hierarchy or roles. How many distinct three-person teams can we form?

We can solve this counting problem in two distinct ways:

1. Direct Selection: Ignore job titles and select any three people directly from the combined pool of seven. This gives $\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ total teams.
2. Two-Stage Selection by Role: Partition the team according to how many designers it contains. If a team contains $j$ designers (where $j \in \{0, 1, 2, 3\}$), it must contain exactly $3-j$ engineers to make up the total size of three.

Calculating the choices for each mutually exclusive case:

The numerical agreement $35 = 35$ is no accident. Every valid team determines a unique pair: $(\text{Designer members}, \text{Engineer members})$. Conversely, specifying any such pair uniquely reconstructs a distinct team. Because this correspondence is a bijection (a reversible one-to-one mapping), both counting procedures must produce the exact same total!

This illustrates the guiding principle of combinatorial proof: to establish an algebraic identity, show that both sides count the exact same set of objects from different vantage points.

---

6.1 Pascal's triangle and combinatorial identities

For non-negative integers $n \ge 0$ and $0 \le k \le n$, the binomial coefficient $\binom{n}{k}$ (read "$n$ choose $k$") counts the number of distinct $k$-element subsets that can be formed from an $n$-element set. It is calculated algebraically as:

By convention, we extend binomial coefficients to boundary cases by setting $\binom{n}{k} = 0$ whenever $k < 0$ or $k > n$, provided $n$ is a non-negative integer.

---

Pascal's Identity

For any integer $n \ge 1$ and $0 \le k \le n$, binomial coefficients satisfy Pascal's identity:

Combinatorial Proof: Consider an $n$-element set $S = \{1, 2, \dots, n-1, \star\}$, where we distinguish one special element called $\star$. We want to choose a $k$-element subset from $S$. Every valid subset falls into exactly one of two mutually exclusive categories:

1. Subsets that EXCLUDE $\star$: We must choose all $k$ elements from the remaining $n-1$ ordinary elements. There are $\binom{n-1}{k}$ ways to do this.
2. Subsets that INCLUDE $\star$: Since $\star$ is already selected, we must choose the remaining $k-1$ elements from the other $n-1$ elements. There are $\binom{n-1}{k-1}$ ways to do this.

Because these two cases are disjoint and together cover every possible $k$-subset, adding their counts proves the identity.

---

Pascal's Triangle and Core Identities

Arranging binomial coefficients into triangular rows creates Pascal's Triangle, where every interior entry is formed by adding the two adjacent entries directly above it:

Pascal's triangle reveals several fundamental properties of binomial coefficients:

• Symmetry Property: $\binom{n}{k} = \binom{n}{n-k}$. Choosing $k$ elements to include in a subset is equivalent to choosing the remaining $n-k$ elements to exclude.
• Row-Sum Identity: $\sum_{k=0}^n \binom{n}{k} = 2^n$. Every element in an $n$-element set has 2 choices (include or exclude). Summing subsets across all possible sizes $k$ yields all $2^n$ possible subsets.

---

Committee-Chairperson Identity

For integers $1 \le k \le n$, the committee-chairperson identity states:

Combinatorial Proof: Suppose we want to choose a committee of $k$ people from $n$ candidates, and designate one committee member as the chairperson. We can count the valid outcomes in two ways:

• Committee-First Approach (Left Side): First pick a $k$-person committee from $n$ candidates in $\binom{n}{k}$ ways. Then pick one of the $k$ committee members to be chairperson in $k$ ways. Total: $k\binom{n}{k}$.
• Chairperson-First Approach (Right Side): First pick the chairperson directly from all $n$ candidates in $n$ ways. Then pick the remaining $k-1$ committee members from the remaining $n-1$ candidates in $\binom{n-1}{k-1}$ ways. Total: $n\binom{n-1}{k-1}$.

---

The Hockey-Stick Identity

For integers $0 \le r \le N$, summing binomial coefficients down a diagonal of Pascal's triangle yields the hockey-stick identity:

Combinatorial Proof: We want to count the number of $(r+1)$-element subsets selected from the set $\{0, 1, 2, \dots, N\}$, which contains $N+1$ total elements. Direct selection gives $\binom{N+1}{r+1}$.

Alternatively, classify each subset according to its largest element $j$:

• The largest element $j$ must satisfy $r \le j \le N$ (since we need at least $r$ smaller elements).
• Once $j$ is fixed as the largest element, the remaining $r$ elements of the subset must be chosen from $\{0, 1, \dots, j-1\}$, which contains $j$ elements.
• There are $\binom{j}{r}$ ways to choose these remaining $r$ elements.

Summing over all possible largest elements $j$ from $r$ to $N$ proves the identity!

6.2 Binomial theorem and generalized binomial series

For a non-negative integer $n$ and commuting variables $x, y$, the binomial theorem expands the $n$-th power of a sum into a polynomial sum of binomial coefficients and monomials:

Combinatorial Explanation: Think of $(x+y)^n$ as multiplying $n$ identical factors: $(x+y)(x+y)\cdots(x+y)$. When expanding this product, every term is formed by choosing either $x$ or $y$ from each factor. To obtain the monomial $x^{n-k}y^k$, we must select $y$ from exactly $k$ factors and $x$ from the remaining $n-k$ factors. The number of distinct ways to select these $k$ factors out of $n$ is precisely $\binom{n}{k}$. Commutativity ensures that all choices for a given $k$ collect into the term $\binom{n}{k}x^{n-k}y^k$.

Special substitutions yield crucial identities:

• Setting $x = y = 1$ gives $\sum_{k=0}^n \binom{n}{k} = 2^n$ (the total row-sum identity).
• Setting $x = 1, y = -1$ gives for $n \ge 1$: $$\sum_{k=0}^n (-1)^k \binom{n}{k} = \binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \dots = 0$$ Combinatorially, toggling one fixed element establishes a perfect 1-to-1 matching (bijection) between all even-sized subsets and odd-sized subsets. (Note: for $n=0$, $2^0=1 \ne 0$).

---

Generalized Binomial Coefficients & Series

For any real number $\alpha$ and integer $k \ge 0$, we define the generalized binomial coefficient as:

Unlike standard binomial coefficients, $\alpha$ can be negative or fractional. If $\alpha$ is a non-negative integer, $\binom{\alpha}{k} = 0$ for all $k > \alpha$. Otherwise, the generalized binomial expansion produces an infinite series that converges for $|x| < 1$:

Proof mechanism for readers familiar with calculus. The coefficients satisfy $(k+1)a_{k+1}=(\alpha-k)a_k$ and $a_0=1$. Their series converges absolutely for $|x|<1$ by the ratio test, unless it already terminates. Differentiating within that interval shows that its sum $F$ satisfies $(1+x)F'=\alpha F$ and $F(0)=1$. Thus the derivative of $F(x)(1+x)^{-\alpha}$ is zero, proving $F(x)=(1+x)^\alpha$. This analytic justification is optional background; the finite counting proofs do not require calculus.

---

6.3 Unimodality and log-concavity

Optional extension. This section studies the shape of a row of coefficients; it is not required for the chapter foundation.

A finite sequence is unimodal if it first weakly increases and then weakly decreases. A non-negative sequence $(a_0, a_1, \dots, a_n)$ is log-concave if every internal term satisfies:

For a positive sequence, divide by $a_{k-1}a_k$ to see that log-concavity means its successive ratios are non-increasing. These ratios can cross from at least one to at most one only once, so a positive log-concave sequence is unimodal. Positivity is sufficient here; arbitrary zero patterns require additional care.

Set $b_k = \binom{n}{k}$. Its successive ratios are:

$$\frac{b_{k+1}}{b_k} = \frac{n-k}{k+1} \qquad (0 \le k \le n-1)$$

The ratio exceeds one before the middle, equals one at the middle transition when $n$ is odd, and is below one afterward. Hence every binomial row is unimodal. For even $n$, there is one maximum at $k=n/2$; for odd $n$, there are two equal central maxima.

For $1 \le k \le n-1$:

$$\frac{b_k}{b_{k-1}} = \frac{n-k+1}{k} > \frac{n-k}{k+1} = \frac{b_{k+1}}{b_k}$$

which proves strict log-concavity at every interior position. This is a proof for all rows, rather than an inference from the triangle's appearance.

Worked example. Row six is $1, 6, 15, 20, 15, 6, 1$. At the center, $20^2 = 400 > 15 \cdot 15 = 225$; at the next position, $15^2 = 225 > 6 \cdot 20 = 120$. The diagram shows the exact coefficients, with bar heights proportional to their values.

The coefficients count subsets of each size. If a subset is chosen uniformly from all $2^n$ subsets, its size has probabilities $\binom{n}{k}/2^n$. Thus the central peak describes the most likely sizes under this particular probability model.

Exercise. Locate the maxima in row seven without computing every entry.
Hint: Determine where $(7-k)/(k+1)$ equals one.
Answer: The two maxima occur at $k=3$ and $k=4$, both with value $35$.

---

6.4 Multinomial theorem

The binomial theorem offers two choices per factor. With $s \ge 1$ commuting variables, the multinomial theorem gives, for integer $n \ge 0$:

To produce the monomial with exponents $(n_1, \dots, n_s)$, choose which $n_i$ factors supply symbol $x_i$. The number of assignments of factors to symbols is the multinomial coefficient from Chapter 4. Every expanded term has exactly one such assignment, proving the theorem.

Worked example. The coefficient of $x^2yz$ in $(x+y+z)^4$ is:

$$\frac{4!}{2!1!1!} = 12$$

Choose two of the four factors for $x$, then one of the remaining two for $y$; the final factor supplies $z$. This gives $\binom{4}{2}\binom{2}{1} = 12$ choices.

Setting every variable equal to one yields:

$$\sum_{\substack{n_1+\dots+n_s=n \\ n_i \ge 0}} \frac{n!}{n_1! \cdots n_s!} = s^n$$

This counts all length-$n$ words over an $s$-symbol alphabet by their symbol multiplicities. It also explains why summing multinomial probabilities gives one: substitute non-negative probabilities $p_1, \dots, p_s$ with sum one into the theorem.

Exercise. Find the coefficient of $xyz$ in $(x+y+z)^3$, and then in $(2x+y+z)^3$.
Hint: The second expression supplies an extra factor of two when its one $x$ is chosen.
Answer: $6$ and $12$.

---

6.5 Vandermonde's identity and Chu–Vandermonde summation

For non-negative integers $m, n, r$, Vandermonde's identity is:

An ordinary binomial coefficient with an impossible lower argument is zero. Consequently, the displayed bounds work even when some cases are impossible. If $r > m+n$, both sides are zero.

Combinatorial proof. Let $A$ and $B$ be disjoint sets of sizes $m$ and $n$. An $r$-subset $T$ of their union determines the pair $(T \cap A, T \cap B)$. Conversely, the union of a $j$-subset of $A$ and an $(r-j)$-subset of $B$ gives an $r$-subset $T$. The intersection and union operations are inverse, so the two counts agree.

Coefficient proof. The product identity

$$(1+x)^m (1+x)^n = (1+x)^{m+n}$$

has coefficient $\sum_j \binom{m}{j}\binom{n}{r-j}$ on the left at $x^r$, and coefficient $\binom{m+n}{r}$ on the right. Polynomial multiplication implements the same split by the number of selected elements from the first group.

Worked example. Choose four people from groups of sizes four and three. The identity gives:

$$0 + 4 + 18 + 12 + 1 = 35 = \binom{7}{4}$$

The zero term corresponds to choosing no members from the first group and four from a group that has only three members.

Generalized convolution. With generalized binomial coefficients, for real parameters $\alpha, \beta$ and integer $r \ge 0$:

$$\sum_{j=0}^r \binom{\alpha}{j} \binom{\beta}{r-j} = \binom{\alpha+\beta}{r}$$

Multiplying the convergent generalized binomial series for $|x| < 1$ proves this by coefficient comparison. Each coefficient involves only finitely many terms. Negative or fractional parameters no longer have the ordinary team-selection interpretation; the identity remains algebraic.

Optional notation bridge: Chu–Vandermonde. Define the rising factorial $(a)_0=1$ and $(a)_j = a(a+1)\cdots(a+j-1)$ for $j \ge 1$. A standard terminating form is:

$$\sum_{j=0}^r \frac{(-r)_j (b)_j}{(c)_j \, j!} = \frac{(c-b)_r}{(c)_r}$$

where $r$ is a non-negative integer and the denominator factors are non-zero. For $r \ge 1$, it suffices to exclude $c = 0, -1, \dots, -(r-1)$. This is the terminating hypergeometric identity recorded in NIST DLMF, equation 15.4.24.

To connect it to the preceding convolution, substitute $\alpha = -b$ and $\beta = c+r-1$, then divide by $\binom{c+r-1}{r} = (c)_r / r!$. The resulting terms are exactly the displayed rising-factorial terms. No knowledge of infinite hypergeometric functions is needed for this finite identity.

For $r=2, b=1, c=3$, the sum is $1 - 2/3 + 1/6 = 1/2$, agreeing with $(2)_2 / (3)_2 = 6/12$.

Exercise. Evaluate $\sum_{j=0}^2 \binom{2}{j}\binom{5}{2-j}$.
Hint: Count two-person teams from seven people.
Answer: $10 + 10 + 1 = 21 = \binom{7}{2}$.

---

6.6 Binomial inversion

Suppose sequences $(a_n)$ and $(b_n)$ satisfy:

$$b_n = \sum_{k=0}^n \binom{n}{k} a_k \qquad (n \ge 0)$$

The sequence $b$ combines information from all subset sizes. Binomial inversion recovers the original sequence:

The sums are finite, and the entries may be ordinary real numbers or exact algebraic quantities; they need not be non-negative counts.

Proof. Substitute the defining expression for $b_k$ into the proposed inverse and collect the coefficient of $a_j$. It is:

$$\sum_{k=j}^n (-1)^{n-k} \binom{n}{k}\binom{k}{j} = \binom{n}{j} \sum_{k=j}^n (-1)^{n-k} \binom{n-j}{k-j}$$

The identity $\binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}$ counts a nested pair of subsets: choose the larger and then the smaller, or the smaller and then its extra elements. If $j < n$, the remaining alternating sum is zero by the binomial theorem. If $j = n$, it consists of the single value one. Thus the substitution leaves exactly $a_n$.

Worked example. Let $a_n = 2^n$. Then:

$$b_n = \sum_{k=0}^n \binom{n}{k} 2^k = 3^n$$

One interpretation is a three-state labeling of each element: unselected, selected with color one, or selected with color two. Choose the selected subset, then color its members. Inverting at $n=3$ gives:

$$a_3 = -1 + 3\cdot 3 - 3\cdot 9 + 27 = 8$$

Application: derangements. A derangement is a permutation with no fixed point. Let $D_k$ count derangements of $k$ elements, including $D_0=1$. Every permutation of $n$ elements has a unique set of $k$ elements that it moves; on that set its restriction is a derangement. Therefore:

$$n! = \sum_{k=0}^n \binom{n}{k} D_k$$

Binomial inversion yields:

$$D_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} k! = n! \sum_{j=0}^n \frac{(-1)^j}{j!}$$

For example, $D_3 = 6(1 - 1 + 1/2 - 1/6) = 2$, corresponding to the two three-cycles.

Exercise. Recover $a_0, a_1, a_2, a_3$ when $b_n = 2^n$.
Hint: Substitute the inverse formula, or recognize $(2-1)^n$.
Answer: All four values are $1$.

---

6.7 Gaussian binomial coefficients and q-analogues

Optional extension. A $q$-analogue replaces a numerical count by an expression involving a variable $q$, with the original result recovered at $q=1$. Here we first use $q$ as a formal weight; no finite-field background is needed.

For a binary word $w$, define $\operatorname{inv}(w)$ as the number of position pairs in which a $1$ occurs before a $0$. Define:

This polynomial is the Gaussian binomial coefficient, also written $\begin{bmatrix} n \\ k \end{bmatrix}_q$. Its coefficient of $q^t$ counts words with exactly $t$ inversions. Inversion-weighted multiset words provide a standard interpretation of q-binomial and q-multinomial coefficients.

Worked example. List all length-four words with two ones:

Thus:

$$G_{4,2}(q) = 1 + q + 2q^2 + q^3 + q^4$$

At $q=1$, every word contributes one, giving $G_{4,2}(1) = 6 = \binom{4}{2}$. The coefficient $2$ records information that the ordinary total does not retain.

A weighted Pascal recurrence. For $n \ge 1$, separate words by their last symbol. A final $1$ adds no inversion; a final $0$ adds one inversion for each of the $k$ earlier ones. Hence:

$$G_{n,k}(q) = G_{n-1,k-1}(q) + q^k G_{n-1,k}(q)$$

with $G_{0,0}=1$ and $G_{n,k}=0$ outside $0 \le k \le n$. This proves polynomiality and non-negative integer coefficients directly. Setting $q=1$ recovers Pascal's identity.

The same recurrence and boundary values establish the familiar product representation:

$$G_{n,k}(q) = \prod_{i=1}^k \frac{1-q^{n-k+i}}{1-q^i}$$

One can verify the recurrence algebraically for this rational expression and then use induction. The factors cancel to give the polynomial defined above. At $q=1$, evaluate that polynomial or take the limit; do not substitute into the uncanceled quotients, which would give $0/0$.

Bridge to finite fields. A field allows addition, subtraction, multiplication, and division by non-zero elements. When $q$ is a prime power, a field with $q$ elements exists. An $n$-dimensional vector space over it has $q^n$ vectors. To count ordered lists of $k$ linearly independent vectors, choose successively outside the spans already created, giving:

$$(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})$$

Each $k$-dimensional subspace has $(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})$ ordered bases. Dividing these counts gives exactly $G_{n,k}(q)$. Thus the same polynomial counts subspaces when its argument is a field size. For example, $G_{3,1}(2) = 1+2+4 = 7$, the seven one-dimensional subspaces of a three-dimensional space over the two-element field.

Finite-field interpretation is developed further in Chapter 42, Sections 42.1 and 42.3, listed in the series roadmap. These later sections are optional background for this bridge; the word-weight model already gives a self-contained definition and proof of the recurrence.

Exercise. Compute $G_{3,1}(q)$ by listing the words $001$, $010$, and $100$.
Hint: Their inversion counts are zero, one, and two.
Answer: $1+q+q^2$, recovering $3$ at $q=1$.

---

6.8 Identities via bijections, generating functions, and algebra

Three proof methods often describe the same structure at different levels. A bijection maps each object reversibly to another object. A generating function stores counts as coefficients. An algebraic proof transforms expressions using already established identities.

For a polynomial or formal power series $F(x)$, write $[x^r]F(x)$ for the coefficient of $x^r$. A formal power series is treated as a sequence of coefficients, without assigning a numerical value to $x$. Its product satisfies:

$$[x^r]\bigl(A(x)B(x)\bigr) = \sum_{j=0}^r a_j b_{r-j}$$

where $a_j = [x^j]A(x)$ and $b_j = [x^j]B(x)$. The sum is finite, so this coefficient rule has no convergence requirement. Evaluating an infinite series at a number is a separate analytic question.

Worked identity: choosing a marked subset. For $n \ge 1$:

$$\sum_{k=0}^n k\binom{n}{k} = n 2^{n-1}$$

Bijection. The left counts pairs $(S,a)$ where $S$ is a subset of an $n$-element set and $a \in S$ is marked. Map the pair to $(a, S \setminus \{a\})$. There are $n$ choices for $a$, and the second component is any subset of the other $n-1$ elements. The inverse restores $a$ to that subset, proving the right-hand count.

Generating-function proof. Marking one selected factor in the product $(1+x)^n$ gives the polynomial:

$$\sum_{k=0}^n k\binom{n}{k} x^k = n x (1+x)^{n-1}$$

Choose which of the $n$ factors is marked; it must supply $x$, and the other factors independently supply $1$ or $x$. Setting $x=1$ proves the identity. Equivalently, readers familiar with derivatives can differentiate $(1+x)^n$ and multiply by $x$.

Algebraic proof. Use $k\binom{n}{k} = n\binom{n-1}{k-1}$ and the row sum:

$$\sum_{k=0}^n k\binom{n}{k} = n \sum_{j=0}^{n-1} \binom{n-1}{j} = n 2^{n-1}$$

The zero term at $k=0$ is omitted before changing variables. For $n=4$, the left side is $0+4+12+12+4=32$, matching $4\cdot 8$.

These methods have different obligations. A proposed bijection needs a well-defined inverse. A coefficient proof needs the correct coefficient and product rule. An algebraic proof needs valid identities and correctly handled boundaries. A numerical check is useful in all three approaches but replaces none of them.

Exercise. Prove $\sum_{k=0}^n \binom{n}{k} 3^k = 4^n$ in two ways.
Hint: Give each element four states, or set $x=3$ in $(1+x)^n$.
Answer outline: Choose a subset and give each selected element one of three colors; every element is either unselected or has one of three colors.

---

Prove one identity by three methods and examine a q-analogue

Pascal's recurrence builds the coefficients, while binomial expansion turns them into a polynomial. Vandermonde's identity then describes how two such polynomials combine. A weighted word model preserves that combination rule while recording inversion counts, revealing why a q-analogue needs an extra weight.

The ordinary convolution also appears in probability. If two disjoint groups of $m$ and $n$ independent trials all have success probability $p$, their success-count distributions combine by convolution. For $0 < p < 1$, the probability of $r$ total successes is:

$$\sum_j \binom{m}{j} \binom{n}{r-j} p^r (1-p)^{m+n-r} = \binom{m+n}{r} p^r (1-p)^{m+n-r}$$

This is useful when aggregating independent batches of tests or events. The shared probability $p$ and independence are essential assumptions; groups with different success probabilities do not reduce to this same formula.