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:
Example.
Solution.
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.
Two well-known identities involving binomial coefficients:
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