Mathematics for Computer Science

Chapter 15 Cardinality Rules464

by the Bookkeeper Rule. Hence, the coefficient ofankbkis

n

k

. So fornD 4 ,
this means:

.aCb/^4 D

4

0

!

a^4 b^0 C

4

1

!

a^3 b^1 C

4

2

!

a^2 b^2 C

4

3

!

a^1 b^3 C

4

4

!

a^0 b^4

In general, this reasoning gives the Binomial Theorem:

Theorem 15.7.1(Binomial Theorem).For alln 2 Nanda;b 2 R:

.aCb/nD

Xn

kD 0

n

k

!

ankbk

The Binomial Theorem explains why thenchooseknumber is called abinomial
coefficient.
This reasoning about binomials extends nicely tomultinomials, which are sums
of two or more terms. For example, suppose we wanted the coefficient of

bo^2 k^2 e^3 pr

in the expansion of.bCoCkCeCpCr/^10. Each term in this expansion is a
product of 10 variables where each variable is one ofb,o,k,e,p, orr. Now, the
coefficient ofbo^2 k^2 e^3 pris the number of those terms with exactly 1b, 2o’s, 2
k’s, 3e’s, 1p, and 1r. And the number of such terms is precisely the number of
rearrangements of the word BOOKKEEPER:

10

1;2;2;3;1;1

!

D

10Š

1Š 2Š 2Š 3Š 1Š 1Š

:

This reasoning extends to a general theorem.

Theorem 15.7.2(Multinomial Theorem).For alln 2 N,

.z 1 Cz 2 C


Czm/nD

X

k 1 ;:::;km 2 N

k 1 C


CkmDn

n

k 1 ;k 2 ;:::;km

!

z 1 k^1 z 2 k^2 


zkmm:

You’ll be better off remembering the reasoning behind the Multinomial Theorem
rather than this cumbersome formal statement.