In Combinations, we introduced binomial coefficients as the number of ways to choose objects from a set of size . Binomial coefficients also arise naturally when considering powers of binomial expressions, as shown in the following theorem.
The two different ideas mentioned above are actually very closely related to each other. When we expand , each term in the expansion comes from choosing either or from each of the binomials in the product. This is why the terms in our expression are of the form . To get the term , we have to multiply copies of and copies of . If we choose of the binomials from which to use the term , then we are left with of the binomials from which to use the term . The total number of ways to choose of the binomials is , which is why this is the coefficient of the term .
The binomial coefficients can be arranged into a chart called Pascal’s Triangle that uses the relation . The th row of Pascal’s triangle has the binomial coefficients . The first row is considered row 0 and contains the coefficient .
By plugging in the values of the binomial coefficients, we obtain Pascal's Triangle:
When working with binomial coefficients, we can generally approach problems in two different ways, either algebraically (by manipulating the expressions), or combinatorially (by interpreting the expressions).
1. Show algebraically that .
Solution: We expand the expression on the left hand side in terms of factorials:
2. Show combinatorially that .
Solution: The right hand side counts the number of ways to choose people from people. If we consider one of the people, then either they are chosen in the set of people or they are not. The number of ways to choose people which includes this person is (we need to choose of the other people). The number of ways to choose people which do not include this person is (we need to choose of the other people).
3. Show that .
Algebraic solution: From the Binomial Theorem, we have
If we let , this expression becomes
Combinatorics solution: We use the technique of Double Counting. Consider the number of ways to choose a team out of players. From Combinations, there are ways to choose a team of exactly players; therefore, the left hand side represents the number of ways to choose a team according to the number of players. On the other hand, we can choose a team by deciding if a specified player is in the team or not. By the Rule of Product, there are ways to do this which is the right hand side. Hence, the two sides are equal.