Pascal’s Rule for Binomial Coefficients
Pascal’s Rule is also known as Pascal’s Identity. It states that “C(n+1, k) = C(n, k-1) + C(n, k).”
While it is possible to prove this algebraically, it might be simpler to use a combinatorial proof.
Let ‘A’ be a set with “n+1” elements, from which ‘k’ elements will be selected randomly. There are C(n+1, k) ways to do so.
However, consider isolating one specific element, ‘e’, by removing it from this original set ‘A’. The new set ‘A~’ has only ‘n’ elements.
We can now create the k-subsets of ‘A~’, guaranteeing that none have element ‘e’. There are C(n, k) such sets; let’s call them “”
However, we could create the (k-1)-subsets from ‘A~’, and then add element ‘e’ to each. These subsets now have ‘k’ elements each, and every such subset has ‘e’. There are C(n, k-1) such sets, collectively called .
Realize that each original k-subset of ‘A’ is either in the collection or , and there is no overlap between these collections.
Therefore the number of k-subsets of ‘A’ is precisely the same as the number of plus subsets. Therefore “C(n+1, k) = C(n, k) + C(n, k-1)” as required.
How Many k-Subsets can be Chosen?
How many different k-subsets can be chosen from a set with ‘n’ elements?
As shown in the image, this is the sum of the binomial coefficient “C(n, k)” for all values of ‘k’ from zero to ‘n’. It equals “2 to the power ‘n’ = 2^n.”
Let’s prove this algebraically, using the binomial theorem.
- = (1 + 1)^n
- = C(n, 0)*(1^n)*(1^0) + C(n, 1)*(1^(n-1))*(1^1) + C(n, 2)*(1^(n-2))*(1^2) + … + C(n, n-2)*(1^2)*(1^(n-2)) + C(n, n-1)*(1^1)*(1^(n-1)) + C(n, n)*(1^0)*(1^n)
- = C(n, 0) + C(n, 1) + C(n, 2) + … + C(n, n-2) + C(n, n-1) + C(n, n) , because all the “1 to the power of whatever” factors simply equal ‘1’
- = Σ[j = zero to n]( C(n, j) ) , as required.
For a set ‘A‘, this collection of all the k-subsets of ‘A‘ is known as the power set of ‘A‘, or P (A).
Concluding the Binomial Coefficient
The binomial coefficient formula concisely prescribes the coefficient for any term of a binomial expansion of the form “(x + y)^n.”
The binomial coefficient is equally important in the discipline of combinatorics, a mathmatical study tied closely to probability theory, where it lends its name to the binomial distribution.
Bloomfied, A. Binomial Coefficients. University of Virginia. Accessed August 26, 2012.
matte, Sanchez, P., Bukh, B., Slone, M., Woo, C. binomial coefficient. (version 27). PlanetMath. Accessed August 26, 2012.