Binomial coefficients, Pascal's triangle, and the power set

Binomial coefficients

An expression like (a + b) or (1 + x) is called a binomial because it involves two symbols or quantities. Squaring (a + b) entails multiplying each summand in the first factor by each summand in the second factor: (a + b)^2 = a × a + a × b + b × a + b × b = a^2 + 2ab + b^2. Note that each summand in the final answer has a total power of 2 (because there are originally two factors). Note also that there is only one way to choose an a from each factor, hence a^2 appears alone (i.e., multiplied by 1), one can obtain ab from either and a int the first factor and a b in the second factor or from a b in the first factor and an a in the second factor, and there is only one way to choose a b from each factor, hence b^2 appears alone. In general, in the expansion of (a + b)^n, (a^k)(b^(n-k)) [note that the exponents sum to n] is multiplied by C(n,k), because there are C(n,k) ways to choose k of the factors to contribute an a and (n-k) of the factors to contribute a b (each factor contributes either an a or a b). For this reason, C(n,k) is sometimes called a binomial coefficient; it is the coefficient of (it multiplies) (a^k)(b^(n-k) in the expansion of (a + b)^n. For example, verify that (a + b)^4 = a^4 + 4(a^3)(b) + 6(a^2)(b^2) + 4(a)(b^3) + b^4.

Pascal's triangle

One way to find binomial coefficients is with Pascals triangle. Pascal's triange is:

                 1                                    C(0,0)
	      1     1                           C(1,0)      C(1,1)
           1     2     1                  C(2,0)      C(2,1)      C(2,2)
         1    3     3    1          C(3,0)      C(3,1)      C(3,2)      C(3,3)
       1   4     6     4   1  C(4,0)      C(4,1)      C(4,2)      C(4,3)     
               . . .                                  . . .

Note that there are 1's down each side, and every other entry is the sum of the two entries which are diagonally above it. This can be expressed an C(n,k) = C(n-1, k-1) + C(n-1, k) which is easily verified. Also note the symmetry of Pascal's triangle, which manifests the fact that C(n,k) = C(n,n-k),

Exercise: Expand (a+b)^5; expand (1+x)^5; expand (2+x)^5, in particular, what is the coefficient of x^3 in (2+x)^5?

What is the sum of the entries in a row of Pascal's triangle? Why?

The power set

How many subsets are there of a set with n members? This question can be visualized as lining the n members up, and deciding whether or not to include each in the subset. Hence by the multiplication rule for counting, there are 2^n subsets of a set with n members (this includes the empty set and the entire set). One can ask more specific questions, such as how many subsets with three members are there of a set with n members. The answer is C(n,3), you choose 3 members to be included in the subset and n-k members to be excluded. Summing over all subset sizes from 0 to n yields 2^n. One context in which the power set arises is the question of how many different pizzas one can order if n toppings are available; the empty set corresponds to a plain cheese pizza, while the entire set corresponds to a pizza with everything on it. C(n,3) is the number of different 3-topping pizzas.

Competencies: What is (a+b)^7? What is the coefficient of x^3 in the expansion of (1+x)^7? What is the coefficient of x^3 in (3+x)^7?

Reflection: What are some examples other than pizza making where the power set occurs?.

Challenge: What is the alternating sum of the rows of Pascal's triange (i.e., when every other term is multiplied by -1: 1-1; 1-2+1; 1-3+3-1; etc.) Why is this true?

May 2003

return to index