4.1 Binomial coefficients and expansions

Counting before expanding

The binomial theorem is often remembered as a formula, but the formula is a counting statement. When expanding $(x+y)^n$, each product comes from choosing either $x$ or $y$ from each of the $n$ factors. Different choices can produce the same monomial. Its coefficient records how many choices produce it, so we need to distinguish the choices made during multiplication from the terms left after collecting like terms.

The central question is therefore: how many ways can we select the factors that contribute $y$? Their positions matter, even though the order in which we name those positions does not. Factorials, permutations, and combinations make this distinction precise. They also explain why the coefficients are integers and why a short coefficient calculation can replace a long expansion.

Factorials, permutations, and combinations

Definition

Factorial

For a positive integer $n$,

$$n! = n(n-1)(n-2)\cdots 2\cdot 1.$$

By convention, $0! = 1$.

To arrange all of $n$ distinct objects in a row without repetition, there are $n$ choices for the first position, then $n-1$ for the second, and so on. Multiplying these numbers gives the factorial. At each stage, every partial arrangement has the stated number of possible next choices; this is the sequential product rule. The convention at zero corresponds to one empty arrangement, rather than no arrangements.

Definition

Permutation

Let $n$ and $k$ be integers with $0 ≤ k ≤ n$. A $k$-permutation of $n$ distinct objects is an ordered arrangement of $k$ of those objects, without repetition. The number of such arrangements is

$$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.$$

When $k=0$, the product is empty and has value $1$.

There are exactly $k$ factors in the product: the last choice has $n-(k-1)=n-k+1$ possibilities. The factorial quotient cancels the unused factors from $n-k$ down to $1$; it does not introduce a further choice. In particular, $P(n,n)=n!$ counts arrangements of all the objects, while $P(n,0)=1$ counts the empty ordered selection.

An unordered selection specifies only which objects are chosen. An ordered selection also specifies their positions; arranging a previously chosen set specifies only their order. For example, from the letters $A,B,C,D,E$, selecting three letters in order gives $P(5,3)=5\cdot4\cdot3=60$ results. The sequences $A,B,C$ and $C,B,A$ are different ordered results, but represent the same three-element selection. This distinction must be settled before choosing a counting formula.

Definition

Binomial coefficient

For integers $n$ and $k$ with $0 ≤ k ≤ n$,

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$$

It counts the number of $k$-element subsets of an $n$-element set, also called $k$-combinations. The notation $C(n,k)$ denotes the same number.

Each fixed selection of $k$ distinct objects has exactly $k!$ internal orders. Thus the ordered selections split into equally sized groups: two ordered selections belong to the same group precisely when they contain the same objects. Counting by groups gives

$$P(n,k)=\binom{n}{k}k!, \qquad \binom{n}{k}=\frac{P(n,k)}{k!}.$$

This explains both the division and the fact that the quotient is an integer. In the five-letter example, each group has $3!=6$ orders, so there are $60/6=10$ unordered selections. Dividing by $k!$ is justified because every selected object is distinct and every selection has the same number of orders. It would be incorrect to divide again after a combination has already removed those orders.

Worked example

Arrange objects with a restriction

Suppose $m$ distinct girls and $n$ distinct boys are seated in a row, with $m\gt n$, and no two boys may sit together. We count the positions of individual people, so exchanging two girls or two boys gives a different seating.

First arrange the $m$ girls. This can be done in $m!$ ways. For any fixed order, they create $m+1$ gaps: one before the first girl, one between each consecutive pair, and one after the last girl. Each gap can contain at most one boy; placing two boys in the same gap would make them adjacent.

Choose $n$ occupied gaps in $\binom{m+1}{n}$ ways, then arrange the $n$ boys among those gaps in $n!$ ways. The gaps already have a left-to-right order; it is the boys that are assigned to them. Consequently,

$$\binom{m+1}{n}n!=P(m+1,n)=\frac{(m+1)!}{(m+1-n)!}.$$

Multiplying by the number of girl arrangements gives

$$m!\binom{m+1}{n}n!=m!P(m+1,n) =m!\frac{(m+1)!}{(m+1-n)!}.$$

There is no double counting: a finished seating uniquely determines the order of the girls, the occupied gaps, and the boy in each gap. Conversely, each such choice gives a valid seating. The original assumption $m\gt n$ guarantees enough gaps, but the argument works for nonnegative integers satisfying $n ≤ m+1$. When $m=0$, the empty row is regarded as one gap. If $n=m+1$, every gap is occupied. If $n\gt m+1$, a valid seating is impossible, so the answer is zero; the displayed factorial quotient is not used there.

Pascal's identity

Theorem

Basic binomial identities

Let $n$ be a nonnegative integer. For integers $k$ with $0 ≤ k ≤ n$,

$$\binom{n}{0}=\binom{n}{n}=1, \qquad \binom{n}{k}=\binom{n}{n-k}.$$

For integers $k$ with $0 ≤ k ≤ n-1$,

$$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}.$$

There is exactly one empty subset and exactly one subset containing every object. These explain the endpoint values, including $\binom00=1$ when the underlying set is empty. Symmetry follows by taking complements: each selected $k$-element subset determines a unique unselected $(n-k)$-element subset, and taking the complement again recovers the original choice. Thus the two kinds of selection have equal counts. In the factorial formula, the same symmetry exchanges the two denominator factors.

The last identity is Pascal's identity. Its upper index increases because we are now selecting from one more object. To count $(k+1)$-element subsets of $n+1$ distinct objects, distinguish one object and separate the subsets into two cases. Those containing that object require $k$ more objects from the remaining $n$, giving $\binom nk$. Those excluding it require all $k+1$ objects from the remaining $n$, giving $\binom n{k+1}$. The cases are disjoint and exhaustive, so their counts add. The index range ensures both selections are within the factorial definition above.

Proof

Algebraic proof of Pascal's identity

For an integer $k$ with $0 ≤ k ≤ n-1$, compute

$$\binom{n}{k}+\binom{n}{k+1} =\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}.$$

Use the common denominator $(k+1)!(n-k)!$. The first numerator is multiplied by $k+1$, whereas the second is multiplied by $n-k$. Their sum is

$$n!(k+1)+n!(n-k)=n!(n+1).$$

Therefore

$$\binom{n}{k}+\binom{n}{k+1} =\frac{(n+1)!}{(k+1)!(n-k)!} =\binom{n+1}{k+1}.$$

The remaining factorial is correct because $(n+1)-(k+1)=n-k$. Checking this difference helps prevent a shift of one in the final indices.

Pascal's triangle places $\binom nk$ in row $n$, starting at row zero, with $k$ running from zero to $n$. Its first five rows are

$$\begin{array}{c} 1\\ 1\quad1\\ 1\quad2\quad1\\ 1\quad3\quad3\quad1\\ 1\quad4\quad6\quad4\quad1 \end{array}$$

Each row starts and ends with one. Each interior entry is the sum of the two entries immediately above it, and complement symmetry makes every row read the same from either end. These are consequences of counting, rather than separate patterns that must be memorized.

Worked example

Lattice paths

How many paths go from $(0,0)$ to $(5,3)$ if each step is either one unit right or one unit up?

Every path has $8$ steps: $5$ right steps and $3$ up steps. Choosing which $5$ of the $8$ positions are right steps determines all remaining steps, hence the entire path. Conversely, every such selection reaches the destination. Thus the number is

$$\binom{8}{5}=\binom{8}{3}=56.$$

We do not multiply by $5!$ or $3!$: the right steps are not individually labelled, and exchanging two right steps leaves the path unchanged. More generally, paths to $(k,n-k)$ are counted by $\binom nk$.

This also gives a geometric reading of Pascal's identity. A path to $(k+1,n-k)$ arrives either from $(k,n-k)$ by a right step or from $(k+1,n-k-1)$ by an up step. Counting by the final step gives precisely $\binom nk+\binom n{k+1}=\binom{n+1}{k+1}$ for $0 ≤ k ≤ n-1$.

The binomial theorem

Theorem

Binomial theorem

For every positive integer $n$,

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

Concept lensCombinatorial

A subset is a choice of terms in the expansion

Let $n\ge1$ and $0\le k\le n$ be integers, and regard $x,y$ as commuting variables. Label the $n$ factors of $(x+y)^n$ by $1,\ldots,n$.

Selection view. A $k$-element subset $S$ of these labels specifies exactly which factors supply $y$; every other factor supplies $x$. Naming the elements of $S$ in another order changes no choice, so the count is $\binom nk$, without a further factor of $k!$.

Algebraic view. Distributivity produces one product for each such choice. Commutativity makes all products with $k$ choices of $y$ the same monomial $x^{n-k}y^k$. Conversely, each choice producing these formal exponents determines one such subset. Collecting these contributions gives coefficient $\binom nk$. The coefficient identity then holds for all real substitutions, including zero.

Here $k$ counts the $y$ choices; counting $x$ choices instead replaces $k$ by $n-k$. The endpoint subsets $S=\varnothing$ and $S=\{1,\ldots,n\}$ each give one choice. Over all subset sizes there are $2^n$ products before collection.

Every product has total degree $n$: the two exponents sum to $n$. As $k$ increases from zero to $n$, the exponent of $x$ decreases and that of $y$ increases. This gives $n+1$ monomial positions after collection. The endpoint terms are $x^n$ and $y^n$, each with coefficient one. Counting the positions that contribute $x$ instead gives the equivalent indexing

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

Either convention is valid, but a single calculation must use its chosen convention consistently. Complement symmetry explains why the coefficients match when the order of the sum is reversed.

Pascal's identity also explains the induction step. Multiplying the expansion for power $n$ by $x+y$, an interior term $x^{n+1-j}y^j$ receives contributions from $x$ times the old term indexed by $j$, and $y$ times the old term indexed by $j-1$. For $1 ≤ j ≤ n$, their combined coefficient is $\binom nj+\binom n{j-1}=\binom{n+1}j$. The two endpoint terms each arise once. Starting with power one, this recovers the next row at every step.

Worked example

Expand a small power

For $n=3$,

$$(x+y)^3=x^3+3x^2y+3xy^2+y^3.$$

The coefficient $3$ of $x^2y$ counts the products $yxx$, $xyx$, and $xxy$: exactly one of the three factors supplies $y$. Similarly, choosing two positions for $y$ gives the three products contributing $xy^2$. Choosing no $y$ or choosing $y$ from every factor gives the two endpoint terms. Thus the $8$ products before collection become $4$ monomial terms, with coefficients $1,3,3,1$; the sum of the coefficients still counts all eight choices.

Substitution makes this last observation general. Set $x=y=1$; every monomial becomes one, so the sum of the coefficients is $2^n$. Set $x=1$ and $y=-1$; terms acquire alternating signs and their sum is zero. For positive integers $n$, these statements are

$$\sum_{k=0}^n\binom nk=2^n, \qquad \sum_{k=0}^n(-1)^k\binom nk=0.$$

The second equality says that the counts of even-sized and odd-sized subsets are equal. The positive-integer condition matters: at $n=0$ the alternating sum contains only the single value one. Both substitutions use the finite binomial theorem already proved.

Coefficient extraction

The binomial theorem is especially useful when only one term is needed. Begin with its general term, treating each entire summand in the original bracket as one unit. Keep the binomial coefficient, numerical powers, sign, and variable exponent separate. The exponent identifies which index is relevant; it does not by itself give the coefficient.

For an expression of the form $(ax^p+bx^q)^n$, with numerical constants $a,b$ and integer exponents $p,q$, substitution into the finite theorem gives

$$T_k=\binom nk (ax^p)^{n-k}(bx^q)^k =\binom nk a^{n-k}b^k x^{p(n-k)+qk}, \qquad k=0,1,\ldots,n.$$

If a negative exponent occurs, take $x\ne0$. To find the coefficient of $x^r$, solve $p(n-k)+qk=r$ and keep only integer indices with $0 ≤ k ≤ n$. For each valid index, evaluate $\binom nk a^{n-k}b^k$, including any sign carried by the constants. If there is no valid index, the coefficient is zero. When $p\ne q$ there is at most one matching index; if several terms have the same exponent, their coefficients must be added.

Worked example

Find a constant term

Find the constant term of

$$\left(x^3-\frac{1}{x}\right)^9, \qquad x\ne0.$$

Here the second summand is the whole expression $-1/x$, so choosing it $k$ times contributes both $(-1)^k$ and $x^{-k}$. The general term is

$$\binom{9}{k}(x^3)^{9-k}\left(-\frac1x\right)^k =\binom{9}{k}(-1)^k x^{27-4k}.$$

A constant term has exponent zero. The equation $27-4k=0$ gives $k=27/4$, which is not an integer. Therefore this expansion has no constant term: its constant coefficient is zero. Rounding the index would select a different power of $x$, not an approximate constant term.

Compare the closely related expression $(x^2-1/x)^9$, again for $x\ne0$. Changing the first exponent changes the general term to

$$\binom9k(x^2)^{9-k}\left(-\frac1x\right)^k =\binom9k(-1)^k x^{18-3k}.$$

Now $18-3k=0$ gives $k=6$, an integer in the allowed range. The constant term is $\binom96(-1)^6=84$. The sign is positive because six negative factors were selected. These two expressions show why the exponent equation and the validity check must be performed anew for each question.

Use the following procedure whenever a particular coefficient is requested:

1. Write the general term and specify what the index counts.
2. Simplify the variable exponent, retaining all scalar powers and signs.
3. Set the exponent equal to the requested power.
4. Check that each resulting index is an integer with $0 ≤ k ≤ n$.
5. Substitute valid indices into the numerical coefficient and add any contributions to the same power.

Common mistake

The binomial index must be an integer in range

The index counts selected factors, so it cannot be fractional, negative, or larger than the total number of factors. An inadmissible index means the requested term is absent. Even for an admissible index, the coefficient is not usually just the binomial coefficient: the numerical powers and signs in the two summands still contribute. A constant term means exponent zero; it does not mean substituting zero for the variable, especially when the original expression contains reciprocal powers.

Quick checks

Checkpoint

Why is $C(n,k)$ divided by $k!$ while $P(n,k)$ is not?

Compare ordered and unordered selection.

Solution · Answer

$P(n,k)$ counts ordered arrangements. $C(n,k)$ counts unordered selections, so the $k!$ possible internal orders of each selected set must be divided out. Every selected set has exactly that many orders because the objects are distinct.

Checkpoint

How many paths go from $(0,0)$ to $(4,2)$ using only right and up steps?

Count the right-step positions.

Solution · Answer

There are $6$ steps total and $4$ right steps, so the number is $\binom64=15$. Choosing the two up-step positions gives the same count by complement symmetry.

Checkpoint

For an integer $n ≥ 2$, what is the coefficient of $x^{n-2}y^2$ in $(x+y)^n$?

Use the binomial theorem.

Solution · Answer

The coefficient is $\binom n2$: choose exactly two of the factors to supply $y$, while all the others supply $x$.

Exercises

1. Compute $\binom{7}{3}$ and explain its counting meaning.
2. Prove $\binom{n}{k}=\binom{n}{n-k}$ using the factorial formula.
3. Find the coefficient of $x^4$ in $(2x-3)^6$.
4. Find the coefficient of $x^0$ in $(x^2+1/x)^6$, where $x\ne0$.

Guided solutions

Solution · Model solution 1

$\binom73=7!/(3!4!)=(7\cdot6\cdot5)/(3\cdot2\cdot1)=35$. It counts the three-element subsets of a seven-element set. Each subset corresponds to six ordered selections; the division removes those orders.

Solution · Model solution 2

For integers $0 ≤ k ≤ n$, substitute into the formula: $\binom{n}{n-k}=n!/((n-k)!(n-(n-k))!)=n!/((n-k)!k!)=\binom nk$. Both expressions are defined, including the endpoints, by $0!=1$.

Solution · Model solution 3

The general term is $\binom6k(2x)^{6-k}(-3)^k$. To obtain $x^4$, set $6-k=4$, so $k=2$, an allowed integer index. The coefficient is $\binom62 2^4(-3)^2=15\cdot16\cdot9=2160$. Both scalar powers are necessary; the even power makes the contribution positive.

Solution · Model solution 4

The general term is $\binom6k(x^2)^{6-k}x^{-k}=\binom6k x^{12-3k}$. Set $12-3k=0$, so $k=4$, an allowed integer index. The coefficient is $\binom64=15$, with no negative sign because both summands have positive numerical coefficients. This time the exponent equation has a valid solution.