Discrete Math Home

## Binomial Coefficients

In this section, we will learn an expansion formula of $$(x+y)^n$$ for any positive integer $$n$$. For example, consider the fifth power of the binomial $$x+y$$: $(x+y)^5=(x+y)(x+y)(x+y)(x+y)(x+y).$ The terms in the expansion of the above are $$x^{5-k}y^k$$ for $$k=0,1,2,3,4,5$$. Now we have to figure out the coefficient of $$x^{5-k}y^k$$ by counting the number of times it appears in the expansion. We get $$x^{5-k}y^k$$ by choosing $$y$$ from $$k$$ factors (and $$x$$ from the rest $$5-k$$ factors) which can be done in $$\displaystyle\binom{5}{k}$$ ways. Then the coefficient of $$x^{5-k}y^k$$ in the expansion of $$(x+y)^5$$ is $$\displaystyle\binom{5}{k}$$ which is called a binomial coefficient. Thus $\begin{eqnarray*} (x+y)^5 &=& \binom{5}{0}x^5y^0+\binom{5}{1}x^{4}y^1+\binom{5}{2}x^3y^2+\binom{5}{3}x^2y^3+\binom{5}{4}x^1y^4+\binom{5}{5}x^0y^5\\ &=& x^5+5x^{4}y+10x^3y^2+10x^2y^3+5xy^4+y^5. \end{eqnarray*}$

Theorem (The binomial theorem). Let $$n$$ be a positive integer and $$x$$ and $$y$$ be variables. Then $(x+y)^n=\sum_{k=0}^n \binom{n}{k}x^{n-k}y^k =\binom{n}{0}x^n+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^2+\cdots +\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n.$ Corollary. From the binomial theorem, we have the following:

1. $$(1+x)^n=\displaystyle\sum_{k=0}^n \binom{n}{k}x^k$$ (obtained by plugging $$x=1$$ and $$y=x$$).

2. $$\displaystyle\sum_{k=0}^n \binom{n}{k}=2^n$$ (obtained by plugging $$x=y=1$$).

3. $$\displaystyle\sum_{k=0}^n (-1)^k\binom{n}{k}=0$$ (obtained by plugging $$x=1$$ and $$y=-1$$).

Example.

1. How many terms are there in the expansion of $$\left(x^2-\frac{1}{x} \right)^{50}$$?

2. What is the coefficient of $$x^{11}$$ in the expansion of $$\left(x^2-\frac{1}{x} \right)^{61}$$?

Solution.

1. By the binomial theorem, there are 51 terms in the expansion of $$\left(x^2-\frac{1}{x} \right)^{50}$$.

2. Suppose the $$(k+1)$$th term of the expansion of $$\left(x^2-\frac{1}{x} \right)^{61}$$ contains $$x^{11}$$. The $$(k+1)$$th term is $\binom{61}{k}(x^2)^{61-k}\left( -\frac{1}{x} \right)^k =(-1)^k \binom{61}{k} x^{122-3k}.$ Since the $$(k+1)$$th term contains $$x^{11}$$, $x^{122-3k}=x^{11} \implies 122-3k=11 \implies k=37.$ Thus the coefficient of $$x^{11}$$ in the expansion of $$\left(x^2-\frac{1}{x} \right)^{61}$$ is $(-1)^{37} \binom{61}{37}=-\binom{61}{37}.$

Definition (Combinatorial proof). A combinatorial proof is a proof of an identity by counting the same objects in two different ways.

Example. Let $$n$$ be a positive integer. Provide a combinatorial proof of the following identity: $\sum_{k=0}^n \binom{n}{k}=2^n$ Solution. Let $$S=\{x_1,x_2,\ldots,x_n\}$$. We prove the identity by counting $$|\mathcal P(S)|$$, the number of subsets of $$S$$ in two different ways.
There are $$\displaystyle\binom{n}{k}$$ subsets of $$S$$ with $$k$$ elements for $$k=0,1,2,\ldots,n$$. Then $|\mathcal P(S)|=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=\sum_{k=0}^n \binom{n}{k}.$ To count $$|\mathcal P(S)|$$ differently, note that a subset $$T$$ of $$S$$ corresponds to bit string $$(a_1,a_2,\ldots,a_n)$$ such that $$a_i=1$$ when $$x_i\in T$$ and $$a_i=0$$ when $$x_i\notin T$$. For example, $$(0,1,1,0,\ldots,0)$$ corresponds to $$\{x_2,x_3\}$$. Because of this one-to-one correspondence between subsets of $$S$$ and bit strings of length $$n$$, $\begin{eqnarray*} |\mathcal P(S)|&=&|\{(a_1,a_2,\ldots,a_n)\;|\;a_i\in \{0,1\}\}|\\ &=&|\{0,1\}\times \{0,1\} \times\cdots\times \{0,1\}|\\ &=&|\{0,1\}|^n \; (\text{by the product rule})\\ &=&2^n. \end{eqnarray*}$ Thus $\sum_{k=0}^n \binom{n}{k}=2^n.$ Example. Let $$n$$ and $$k$$ be positive integers and $$k\leq n$$. Provide (a) a direct proof and (b) a combinatorial proof of the Pascal's identity: $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$ Solution.

1. Direct proof. $\begin{eqnarray*} \binom{n}{k-1}+\binom{n}{k}&=& \frac{n!}{(k-1)!(n-k+1)!}+\frac{n!}{k!(n-k)!} \\ &=& \frac{n!}{(k-1)!(n-k+1)\cdot (n-k)!}+\frac{n!}{k\cdot (k-1)!(n-k)!} \\ &=& \frac{n!}{(k-1)! (n-k)!}\left[ \frac{1}{n-k+1}+\frac{1}{k} \right] \\ &=& \frac{n!}{(k-1)! (n-k)!} \cdot\frac{n+1}{(n-k+1)k} \\ &=& \frac{(n+1)!}{k!(n-k+1)!} \\ &=& \binom{n+1}{k} \end{eqnarray*}$
2. Combinatorial proof. Let $$S=\{a_1,a_2,\ldots,a_n,a_{n+1}\}$$ and $$T=S\setminus \{a_{n+1}\}=\{a_1,a_2,\ldots,a_n\}$$. We prove the identity by counting the number of subsets of $$S$$ with $$k$$ elements in two different ways. There are $$\displaystyle\binom{n+1}{k}$$ subsets of $$S$$ with $$k$$ elements. To count it differently, note that there are two types of $$k$$-element subsets of $$S$$:

1. $$k$$-element subsets of $$S$$ containing $$a_{n+1}$$: These subsets consist of $$a_{n+1}$$ and $$k-1$$ elements from $$T=\{a_1,a_2,\ldots,a_n\}$$. Since there $$\displaystyle\binom{n}{k-1}$$ ways to choose $$k-1$$ elements from $$T$$, the number of these subsets is $$\displaystyle\binom{n}{k-1}$$.

2. $$k$$-element subsets of $$S$$ not containing $$a_{n+1}$$: These subsets consist of $$k$$ elements from $$T=\{a_1,a_2,\ldots,a_n\}$$. Since there $$\displaystyle\binom{n}{k}$$ ways to choose $$k$$ elements from $$T$$, the number of these subsets is $$\displaystyle\binom{n}{k}$$.
Thus the number of $$k$$-element subsets of $$S$$ is $$\displaystyle\binom{n}{k-1}+\binom{n}{k}$$ and consequently $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}.$

Two well-known identities involving binomial coefficients:

1. Vandermonde's identity: For any nonnegative integers $$m,n,r$$ where $$r\leq m,n$$, $\binom{m+n}{r}=\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}.$ Plugging $$m=r=n$$ in Vandermonde's identity, we have $\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2.$

2. The hockey-stick or Christmas stocking identity: For any nonnegative integers $$m,n,r$$ where $$r\leq n$$, $\binom{n+1}{r+1}=\sum_{k=r}^n \binom{k}{r}.$ The name of this identity makes sense from its visualization from Pascal's triangle.

Pascal's triangle: For each nonnegative integer $$n$$, the $$n$$th row of Pascal's triangle is the following. $\binom{n}{0}\;\;\binom{n}{1}\;\;\binom{n}{2}\cdots \binom{n}{n}$ Note that the top row (zeroth row) of Pascal's triangle consists of $$\displaystyle\binom{0}{0}$$ which is defined to be $$1$$. For $$n\geq 2$$, the middle $$n-1$$ entries of the $$n$$th row of Pascal's triangle can be obtained from $$(n-1)$$th row using Pascal's identity. $\begin{array}{lccccccccccc} n=0\hspace{12pt}& & & & & & 1 & & & & & \cr n=1& & & & & 1 & & 1 & & & & \cr n=2& & & & 1 & & 2 & & 1 & & & \cr n=3& & & 1 & & 3 & & 3 & & 1 & & \cr n=4& & 1 & & 4 & & 6 & & 4 & & 1 & \cr n=5& 1 & & 5 & & 10 & & 10 & & 5 & & 1 \cr \end{array}$ $\hspace{48pt}\text{The first six rows of Pascal's triangle}$

Last edited