Binomial coefficients, Pascal's triangle, and the power set
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.
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)
C(4,4)
. . . . . .
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?
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
campbell@math.uni.edu