Contents
The binomial coefficient "n choose k", written
![\[{n \choose k} = \frac{(n)_{k}}{k!} = \frac{n!}{k!\cdot (n-k)!},\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_32cb3e00e1f9363061103682cdeb3e8f4c485d3a_p1.png "\[{n \choose k} = \frac{(n)_{k}}{k!} = \frac{n!}{k!\cdot (n-k)!},\]")
counts the number of k-element subsets of an n-element set.
The name arises from the binomial theorem, which says that
![\[(x+y)^n = \sum_{k=0}^{\infty} {n \choose k} x^k y^{n-k}.\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_15f74fcd776b1e3fac9c382877f20558200f5b85_p1.png "\[(x+y)^n = \sum_{k=0}^{\infty} {n \choose k} x^k y^{n-k}.\]")
For integer n, we can limit ourselves to letting k range from 0 to n. The most general version of the theorem lets k range over all of ℕ, and relies on the binomial coefficient to zero out the extra terms. It holds for any integer n ≥ 0 or (with a suitable definition of binomial coefficients) for any n if |x/y| < 1 (which guarantees that the sum converges).
The connection to counting subsets is straightforward: expanding (x+y)n using the distributive law gives 2n terms, each of which is a unique sequence of n x's and y's. If we think of the x's in each term as labeling a subset of the n positions in the term, the terms that get added together to get xkyn-k correspond one-to-one to subsets of size k. So there are
such terms, accounting for the coefficient on the right-hand side.
1. Recursive definition
If we don't like computing factorials, we can also compute binomial coefficients recursively.
Base cases:
- If k = 0, then there is exactly one zero-element set of our n-element set—it's the empty set—and we have
If k > n, then there are no k-element subsets, and we have
Recursive step: We'll use Pascal's identity, which says that
![\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_b7abf97f5a3722349048f6b2aedbd941e134a165_p1.png "\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]")
The proof of this identity is combinatorial, which means that we will construct an explicit bijection between a set counted by the left-hand side and a set counted by the right-hand side. This is often one of the best ways of understanding simple binomial coefficient identities.
On the left-hand side, we are counting all the k-element subsets of an n-element set S. On the right hand side, we are counting two different collections of sets: the (k-1)-element and k-element subsets of an (n-1)-element set. The trick is to recognize that we get an (n-1)-element set S' from our original set by removing one of the elements x. When we do this, we affect the subsets in one of two ways:
- If the subset doesn't contain x, it doesn't change. So there is a one-to-one correspondence (the identity function) between k-subsets of S that don't contain x and k-subsets of S'. This bijection accounts for the first term on the right-hand side.
- If the subset does contain x, then we get a (k-1)-element subset of S' when we remove it. Since we can go back the other way by reinserting x, we get a bijection between k-subsets of S that contain x and (k-1)-subsets of S'. This bijection accounts for the second term on the right-hand side.
Adding the two cases together (using the sum rule), we conclude that the identity holds.
Using the base case and Pascal's identity, we can construct Pascal's triangle, a table of values of binomial coefficients:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...
Each row corresponds to increasing values of n, and each column to increasing values of k, with
in the upper left-hand corner. To compute each entry, we add together the entry directly above it and the entry diagonally to the left.
1.1. Pascal's identity: algebraic proof
Using the binomial theorem plus a little bit of algebra, we can prove Pascal's identity without using a combinatorial argument (this is not necessarily an improvement). The additional fact we need is that if we have two equal series
![\[\sum_{k=0}^{\infty} a_k x^k = \sum_{k=0}^{\infty} b_k x^k\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_37c4743c8ff8372bfa2178726fef1ce776216bf1_p1.png "\[\sum_{k=0}^{\infty} a_k x^k = \sum_{k=0}^{\infty} b_k x^k\]")
then ai = bi for all i.
Here's the proof:
![\begin{eqnarray*}
\sum_{k=0}^n {n \choose k} x^k
&=& (1+x)^n \\
&=& (1+x)(1+x)^{n-1} \\
&=& (1+x)^{n-1} + x(1+x)^{n-1} \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + x \sum_{k = 0}^{n-1} {n-1 \choose k} x^k \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + \sum_{k = 0}^{n-1} {n-1 \choose k} x^{k+1} \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + \sum_{k = 1}^{n} {n-1 \choose k-1} x^{k} \\
&=& \sum_{k = 0}^{n} {n-1 \choose k} x^k + \sum_{k = 0}^{n} {n-1 \choose k-1} x^{k} \\
&=& \sum_{k = 0}^{n} \left[{n-1 \choose k} + {n-1 \choose k-1}\right] x^{k}.
\end{eqnarray*}](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_6af59dfc59abaa3cff2d2625b18bf6bcab82cb7f_p1.png "\begin{eqnarray*}
\sum_{k=0}^n {n \choose k} x^k
&=& (1+x)^n \\
&=& (1+x)(1+x)^{n-1} \\
&=& (1+x)^{n-1} + x(1+x)^{n-1} \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + x \sum_{k = 0}^{n-1} {n-1 \choose k} x^k \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + \sum_{k = 0}^{n-1} {n-1 \choose k} x^{k+1} \\
&=& \sum_{k = 0}^{n-1} {n-1 \choose k} x^k + \sum_{k = 1}^{n} {n-1 \choose k-1} x^{k} \\
&=& \sum_{k = 0}^{n} {n-1 \choose k} x^k + \sum_{k = 0}^{n} {n-1 \choose k-1} x^{k} \\
&=& \sum_{k = 0}^{n} \left[{n-1 \choose k} + {n-1 \choose k-1}\right] x^{k}.
\end{eqnarray*}")
and now we equate matching coefficients to get
![\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_5db4077b888cdb0fbb291c45f8c83c2eca510151_p1.png "\[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}\]")
as advertised.
2. Vandermonde's identity
Vandermonde's identity says that, provided r does not exceed m or n,
![\[{m+n \choose r} = \sum_{k=0}^{r} {m \choose r-k}{n \choose k}.\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_c4129c9afa4345f940345e2002d79f0c8b7d20e2_p1.png "\[{m+n \choose r} = \sum_{k=0}^{r} {m \choose r-k}{n \choose k}.\]")
2.1. Combinatorial proof
To pick r elements of an m+n element set, we have to pick some of them from the first m elements and some from the second n elements. Suppose we choose k elements from the last n; there are
different ways to do this, and
different ways to choose the remaining r-k from the first m. This gives (by the product rule)
ways to choose r elements from the whole set if we limit ourselves to choosing exactly k from the last n. The identity follow by summing over all possible values of k.
2.2. Algebraic proof
Here we use the fact that, for any sequences of coefficients {ai} and {bi},
![\[\left(\sum_{i=0}^{n} a_i x^i\right) \left(\sum_{i=0}^m b_i x^i\right)
= \sum_{i=0}^{m+n} \left(\sum_{j=0}^i a_j b_{i-j}\right) x^i.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_e9e9a6c81222c63c923b208c1579bdcbfb960679_p1.png "\[\left(\sum_{i=0}^{n} a_i x^i\right) \left(\sum_{i=0}^m b_i x^i\right)
= \sum_{i=0}^{m+n} \left(\sum_{j=0}^i a_j b_{i-j}\right) x^i.
\]")
So now consider
and now equate terms with matching exponents.
Is this more enlightening than the combinatorial version? It depends on what kind of enlightnment you are looking for. In this case the combinatorial and algebraic arguments are counting essentially the same things in the same way, so it's not clear what if any advantage either has over the other. But in many cases it's easier to construct an algebraic argument than a combinatorial one, in the same way that it's easier to do arithmetic using standard grade-school algorithms than by constructing explicit bijections. On the other hand, a combinatorial argument may let you carry other things you know about some structure besides just its size across the bijection, giving you more insight into the things you are counting. The best course is probably to have both techniques in your toolbox.
3. Sums of binomial coefficients
What is the sum of all binomial coefficients for a given n? We can show
![\[\sum_{k=0}^{n} {n \choose k} = 2^n
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_caa67b38cbddc96f232d5687913caf2c89b7262f_p1.png "\[\sum_{k=0}^{n} {n \choose k} = 2^n
\]")
combinatorially, by observing that adding up all subsets of an n-element set of all sizes is the same as counting all subsets. Alternatively, apply the binomial theorem to (1+1)n.
Here's another sum, with alternating sign. This is useful if you want to know how the even-k binomial coefficients compare to the odd-k binomial coefficients.
![\[\sum_{k=0}^{n} (-1)^k {n \choose k} = 0. \mbox{(Assuming $n \neq 0$.)}\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_94e3dda017a3b0a7a4a63024450369ea7d3950ce_p1.png "\[\sum_{k=0}^{n} (-1)^k {n \choose k} = 0. \mbox{(Assuming $n \neq 0$.)}\]")
Proof: (1-1)n = 0n = 0 when n is nonzero. (When n is zero, the 0n part still works, since 00 = 1 = (0 choose 0)(-1)0.)
By now it should be obvious that
![\[\sum_{k=0}^{n} 2^k {n \choose k} = 3^n.\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_968427400ac83ee343e1dfd4676a7d73b7503d73_p1.png "\[\sum_{k=0}^{n} 2^k {n \choose k} = 3^n.\]")
It's not hard to construct more examples of this phenomenon.
4. Application: the inclusion-exclusion formula
We've previously seen that |A∪B| = |A| + |B| - |A∩B|. The generalization of this fact from two to many sets is called the inclusion-exclusion formula and says
![\[
\left| \bigcup_{i=1}^n A_i \right|
=
\sum_{S \subseteq \{1 \ldots n\}, S \neq \emptyset}
(-1)^{|S|+1} \left| \bigcap_{j \in S} A_j \right|.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_b31d64a6df9febd2592f88b45cc1a65bbccf2f36_p1.png "\[
\left| \bigcup_{i=1}^n A_i \right|
=
\sum_{S \subseteq \{1 \ldots n\}, S \neq \emptyset}
(-1)^{|S|+1} \left| \bigcap_{j \in S} A_j \right|.
\]")
This rather horrible expression means that to count the elements in the union of n sets A1 through An, we start by adding up all the individual sets |A1| + |A2| + ... |An|, then subtract off the overcount from elements that appear in two sets -|A1 ∩ A2| - |A1 ∩ A3| - ..., then add back the resulting undercount from elements that appear in three sets, and so on.
Why does this work? Consider a single element x that appears in k of the sets. We'll count it as +1 in (k choose 1) individual sets, as -1 in (k choose 2) pairs, +1 in (k choose 3) triples, and so on, adding up to
![\[
\sum_{i=1}^{k} (-1)^{k+1} {k \choose i}
= -\left(\sum_{i=1}^{k} (-1)^k {k \choose i}\right)
= -\left(\sum_{i=0}^{k} (-1)^k {k \choose i} - 1\right)
= -\left(0 - 1\right)
= 1.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_97bf9f4c20558d0fd9b9c19a60dd5074833299d9_p1.png "\[
\sum_{i=1}^{k} (-1)^{k+1} {k \choose i}
= -\left(\sum_{i=1}^{k} (-1)^k {k \choose i}\right)
= -\left(\sum_{i=0}^{k} (-1)^k {k \choose i} - 1\right)
= -\left(0 - 1\right)
= 1.
\]")
5. Negative binomial coefficients
Though it doesn't make sense to talk about the number of k-subsets of a (-1)-element set, the binomial coefficient (n choose k) has a meaningful value for negative n, which works in the binomial theorem. We'll use the lower-factorial version of the definition:
![\[
{-n \choose k}
= (-n)_{k}/k!
= \left(\prod_{i=-n-k+1}^{-n} i\right) / k!
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_278f3392b3e91bd1d4be3a52889658ab1f32722f_p1.png "\[
{-n \choose k}
= (-n)_{k}/k!
= \left(\prod_{i=-n-k+1}^{-n} i\right) / k!
\]")
Note we still demand that k∈ℕ; we are only allowed to do funny things with the upper index n.
So for example:
![\[
{-1 \choose k}
= (-1)_{k}/k!
= \left(\prod_{i=-1-k+1}^{-1} i\right) / k!
= \left(\prod_{i=-k}^{-1} i\right)/\left(\prod_{i=1}^{k} i\right)
= (-1)^k.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_6ae7d2328d8a7cc2c96102f9f309cb175222230f_p1.png "\[
{-1 \choose k}
= (-1)_{k}/k!
= \left(\prod_{i=-1-k+1}^{-1} i\right) / k!
= \left(\prod_{i=-k}^{-1} i\right)/\left(\prod_{i=1}^{k} i\right)
= (-1)^k.
\]")
This means, for example, that
![\[
\frac{1}{1-z}
= (1-z)^{-1}
= \sum_{n=0}^{\infty} {-1 \choose n} 1^{-1-n} (-z)^n
= \sum_{n=0}^{\infty} (-1)^n (-z)^n
= \sum_{n=0}^{\infty} z^n.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_7fa7a1675232002cb0a37eec693a2c7b4d5e4a34_p1.png "\[
\frac{1}{1-z}
= (1-z)^{-1}
= \sum_{n=0}^{\infty} {-1 \choose n} 1^{-1-n} (-z)^n
= \sum_{n=0}^{\infty} (-1)^n (-z)^n
= \sum_{n=0}^{\infty} z^n.
\]")
In computing this sum, we had to be careful which of 1 and -z got the n exponent and which got -1-n. If we do it the other way, we get
![\[
\frac{1}{1-z}
= (1-z)^{-1}
= \sum_{n=0}^{\infty} {-1 \choose n} 1^{n} (-z)^{-1-n}
= -\frac{1}{z} \sum_{n=0}^{\infty} \frac{1}{z^n}
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_68c8aaeab1aac9bb218c021e32e27e68da935c53_p1.png "\[
\frac{1}{1-z}
= (1-z)^{-1}
= \sum_{n=0}^{\infty} {-1 \choose n} 1^{n} (-z)^{-1-n}
= -\frac{1}{z} \sum_{n=0}^{\infty} \frac{1}{z^n}
\]")
This turns out to actually be correct: applying the geometric series formula turns the last line into
![\[
-\frac{1}{z} \cdot \frac{1}{1-1/z}
= - \frac{1}{z - 1}
= \frac{1}{1-z},
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_8d256361b47b128e342de1604423228e762985aa_p1.png "\[
-\frac{1}{z} \cdot \frac{1}{1-1/z}
= - \frac{1}{z - 1}
= \frac{1}{1-z},
\]")
but it's a lot less useful.
What happens for a larger upper index? One way to think about (-n)k is that we are really computing (n+k-1)k and then negating all the factors (which corresponds to multiplying the whole expression by (-1)k. So this gives us the identity
![\[
{-n \choose k}
= (-n)_{k}/k!
= (-1)^k (n+k-1)_{k} / k!
= (-1)^k {n+k-1 \choose k}.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_2d809e7436ad00c407689c06c39f8e046bd2adb3_p1.png "\[
{-n \choose k}
= (-n)_{k}/k!
= (-1)^k (n+k-1)_{k} / k!
= (-1)^k {n+k-1 \choose k}.
\]")
So, for example,
![\[
\frac{1}{(1-z)^2}
= (1-z)^{-2}
= \sum_{n} {-2 \choose n} 1^{-2-n} (-z)^n
= \sum_{n} (-1)^n {n+1 \choose n} (-z)^n
= \sum_{n} (n+1) z^n.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_070dd185a5a15baf5bfd1c377c8a3ec223a808da_p1.png "\[
\frac{1}{(1-z)^2}
= (1-z)^{-2}
= \sum_{n} {-2 \choose n} 1^{-2-n} (-z)^n
= \sum_{n} (-1)^n {n+1 \choose n} (-z)^n
= \sum_{n} (n+1) z^n.
\]")
These facts are useful when we look at GeneratingFunctions.
6. Fractional binomial coefficients
Yes, we can do fractional binomial coefficients, too. Exercise: Find the value of
![\[
{ 1/2 \choose n } = \frac{(1/2)_{n}}{n!}.
\]](/pinewiki/BinomialCoefficients?action=AttachFile&do=get&target=latex_eacc8d162da1eadb971df6dab2b32096105e1ace_p1.png "\[
{ 1/2 \choose n } = \frac{(1/2)_{n}}{n!}.
\]")
7. Further reading
ConcreteMathematics §5.1–5.3 is an excellent source for information about all sorts of facts about binomial coefficients.