Combinatorics/Binomial Theorem

The Binomial Theorem

The Binomial Theorem determines the expansion for the powers of different sums; written out, it is:

$(x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{n-i}y^{i}$

Here, ${\tbinom {n}{i}}$ is the binomial coefficient for n and i, which was defined in the previous chapter as a number counting the ways to choose i elements from a set of n and pronounced "n choose i", and whose value can be computed as

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

Thus, $(x+2)^{2}=1x^{2}+2x^{1}2^{1}+2^{2}=x^{2}+4x+4\,$

and $(x+y)^{5}=x^{5}+5x^{4}y+10x^{3}y^{2}+10x^{2}y^{3}+5xy^{4}+y^{5}\,$

The coefficients in the expansion are entries in a row of Pascal's triangle. i.e. $(x+y)^{5}$ gives the coefficients for the fifth row of Pascal's triangle.

Combinatorial proof

There are many proofs possible for the binomial theorem. The combinatorial proof goes as follows:

Consider the coefficients of $x^{n-k}y^{k}\,$, for a fixed k, on both sides. The left hand side i.e. $(x+y)^{n}=(x+y)(x+y)\cdots (x+y)$ when expanded will have terms only of the type $x^{n-i}y^{i}\,$ where i ranges from 0 to n. The number of times $x^{n-k}y^{k}\,$ occurs will be precisely equal to the number of ways of choosing k numbers out of n. This is because from each of the factors (x+y), n in all, we will have to choose k of the y's (the remaining will be x's). Thus the coefficient of $x^{n-k}y^{k}\,$ on the left hand side will be ${n \choose k}$. This matches the coefficient on the right hand side and the proof is complete. The proof should be logical .Not a stated sentence

Consequences

There are many consequences of the binomial theorem.

Firstly on putting x = y = 1 in the theorem we get $2^{n}=\sum _{i=0}^{n}{n \choose i}$. This means that the total number of subsets of a set having n elements (which is $2^{n}$, a result we have already obtained) equals the sum of the number of ways of choosing i order sets out of the n set, for all i.

Secondly, on putting x = 1 and y = -1 in the theorem we have $0=\sum _{k=0}^{n}(-1)^{k}{n \choose k}$. Equivalently this means,

$\sum _{k\ odd}{n \choose k}=\sum _{k\ even}{n \choose k}$,

which says that for any n order set, the number of its odd order subsets is equal to the number of its even order subsets.

Thirdly, we have the Vandermode's identity obtained by comparing the coefficient of $x^{k}$ in $(1+x)^{m+n}$

${\begin{aligned}\sum _{k=0}^{m+n}{m+n \choose k}x^{k}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{k=0}^{m}{m \choose k}x^{k}{\biggr )}{\biggl (}\sum _{k=0}^{n}{n \choose k}x^{k}{\biggr )}\\&=\sum _{k=0}^{m+n}{\biggl (}\sum _{i=0}^{k}{m \choose i}{n \choose k-i}{\biggr )}x^{k},\end{aligned}}$

Note that here we use the definition of the product of two polynomials with degrees m and n, respectively, which is given by

${\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},$

where we use the convention that a_s = 0 for all integers s > m and b_t = 0 for all integers t > n.

On comparing the coefficient of $x^{k}$ we get Vandermonde's identity:

${m+n \choose k}=\sum _{i=0}^{k}{m \choose i}{n \choose k-i},\qquad m,n,k\in \mathbb {N}$

Note that putting m = 1 in Vandermonde's identity allows us to recover Pascal's relation discussed in the previous chapter albeit in a slightly different form:

${n+1 \choose k}={n \choose k}+{n \choose k-1}$

Vandermonde's identity has a combinatorial proof too. The binomial coefficient ${m+n \choose k}$ is the number of k subsets of the m + n set $A\bigcup B$ where $A=\{1,2\cdots m\}$ and $B=\{m+1,m+2\cdots m+n\}$. The number of such k-subsets which contain i elements of A would be ${m \choose i}{n \choose k-i}$ (i elements from A and the rest k-i from B). The summation $\sum _{i=0}^{k}{m \choose i}{n \choose k-i}$ counts these subsets for all i.

Another useful result that arises from Vandermonde's is obtained by putting m = k = n in the Vandermonde's identity. That gives us:

${2n \choose n}=\sum _{i=0}^{n}{n \choose i}^{2}$

Let us look at another consequence, the fourth one. Consider $(1+x)^{m+n+1}=(1+x)\cdots (1+x)$ where there are $m+n+1$ terms of the type $(1+x)$ on the right hand side. The coefficient of $x^{n+1}$ on the left side is ${m+n+1 \choose n+1}$. On the right side the coefficient would be obtained by looking at the number of ways of picking up n+1 x's and remaining 1's from the m+n+1 terms of the type (1+x), similar to what we had done in the proof of the binomial theorem. Let the right most x be picked up from the n+i+1'th term where i clearly varies from 0 to m. This gives us the choice of picking up n x's from the remaining n+i terms which can be done in ${n+i \choose n}$ number of ways. The total number of ways will be obviously obtained by summing over all possible i. So the coefficient of $x^{n+1}$ would be $\sum _{i=0}^{m}{n+i \choose n}$ and hence we have the relation

${m+n+1 \choose n+1}=\sum _{i=0}^{m}{n+i \choose n}$

Like Vandermonde's identity this identity can also be proved combinatorically. The left side represents the number of ways of choosing n+1 order sets from an m+n+1 set, say $\{1,2,\cdots m+n+1\}$. Suppose for any given n+1 order set, the largest element in n+i+1 where i varies from 0 to m. Then the remaining n elements have to be chosen from n+i elements and the number of ways of doing that is exactly ${n+i \choose n}$. Summing over all i gives us the total number of ways which has already been decided to be the left side. It only remains to equate the two terms.

Changing the variables in the above identity gives us,

${n+1 \choose k+1}=\sum _{i=k}^{n}{i \choose k}$

Also this implies:

${n+1 \choose k+1}-{m+1 \choose k+1}=\sum _{i=m+1}^{n}{i \choose k}$