Combinatorics/Binomial Theorem< Combinatorics
The Binomial TheoremEdit
The Binomial Theorem determines the expansion for the powers of different sums; written out, it is:
Here, 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
The coefficients in the expansion are entries in a row of Pascal's triangle. i.e. gives the coefficients for the fifth row of Pascal's triangle.
There are many proofs possible for the binomial theorem. The combinatorial proof goes as follows:
Consider the coefficients of , for a fixed k, on both sides. The left hand side i.e. when expanded will have terms only of the type where i ranges from 0 to n. The number of times 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 on the left hand side will be . This matches the coefficient on the right hand side and the proof is complete.
There are many consequences of the binomial theorem.
Firstly on putting x = y = 1 in the theorem we get . This means that the total number of subsets of a set having n elements (which is , 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 . Equivalently this means,
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 in
Note that here we use the definition of the product of two polynomials with degrees m and n, respectively, which is given by
where we use the convention that as = 0 for all integers s > m and bt = 0 for all integers t > n.
On comparing the coefficient of we get Vandermonde's identity:
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:
Vandermonde's identity has a combinatorial proof too. The binomial coefficient is the number of k subsets of the m + n set where and . The number of such k-subsets which contain i elements of A would be (i elements from A and the rest k-i from B). The summation 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:
Let us look at another consequence, the fourth one. Consider where there are terms of the type on the right hand side. The coefficient of on the left side is . 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 number of ways. The total number of ways will be obviously obtained by summing over all possible i. So the coefficient of would be and hence we have the relation
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 . 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 . 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,
Also this implies: