Discrete Mathematics for Computer Science

Combinatorial Identities 459

n!

k! (n - k)!

• C(n, k) 0

In the combinatorial proof that the two sets of subsets are disjoint, we are claiming
that no set in one collection of k sets belongs to the other collection of k sets. This is not
the same as claiming that each k set in one collection is disjoint from each k set in the other
collection, which is clearly not the case.

79.1 Binomial Coefficients

The binomial coefficients derive their name from the role they play as coefficients in the

expansion of a binomial, such as (x + y)^7 .For small exponent n-say, n = 1, 2, 3-the

coefficients of (x + y)n can be remembered, because they are often used. For larger n,
the problem of expanding (x + y)n is not as simple. However, by giving these numbers a
combinatorial interpretation, it is quite easy to write down the coefficients for each term in
the expansion of (x + y)n for any n.

Example 8. Expand (x + y)^3.

Solution. The product is found by choosing, in all possible ways, one term from each of
the three factors and then multiplying those choices together. To see these choices, we have
numbered the elements in each term in the first two steps of the computation.

(x + y)3 = (Xl + yl)(X2 + y2)(X3 + Y3)

= X1X2X3 + X1X2Y3 + X1Y2X3 + X1Y2Y3 + ylX2X3 + ylX2Y3

+ y1y2X3 + Y1Y2Y3

= xxx + 3xxy + 3xyy + yyy

= C(3, O)x^3 + C(3, l)x^2 y + C(3, 2)xy^2 + C(3, 3)y^3. U

We now prove a theorem that shows how to find all coefficients for the expansion of a
binomial.

Theorem 5. (Binomial Theorem) Let n E N. For all x and y,

(X + y)n = C(n, O)xn + C(n, l)xn-ly + C(n, 2)xn-^2 y^2 +... + C(n, n)yn

n

- •C(n, i)xn-iyi

i=0

Proof The proof is by induction on n. Let no = 0 and T = {n E N the identity is true).

(Base step) For n = 0, the formula is

0

(x + y)^0 = EC(O'i) xO-i yi

i=0

= C(O, 0) x

(^0) y^0

=1

which is true.