Mathematics for Computer Science

15.2. Counting with Generating Functions 633

(see Problem 15.5), so

Œxnç



1

.1x/k



D



dn

dnx

1

.1x/k



.0/

1

nŠ

D

k.kC1/


.kCn1/.10/.kCn/

nŠ

D

nC.k1/

n

!

:

In other words, instead of using the donut-counting formula (15.10) to find the
coefficients ofxn, we could have used this algebraic argument and the Convolution
Rule to derive the donut-counting formula.

15.2.5 The Binomial Theorem from the Convolution Rule

The Convolution Rule also provides a new perspective on the Binomial Theo-
rem 14.6.4. Here’s how: first, work with the single-element setfa 1 g. The gen-
erating function for the number of ways to selectndifferent elements from this set
is simply 1 Cx: we have 1 way to select zero elements, 1 way to select the one
element, and 0 ways to select more than one element. Similarly, the number of
ways to selectnelements from any single-element setfaighas the same generating
function 1 Cx. Now by the Convolution Rule, the generating function for choosing
a subset ofnelements from the setfa 1 ;a 2 ;:::;amgis the product,.1Cx/m, of
the generating functions for selecting from each of themone-element sets. Since
we know that the number of ways to selectnelements from a set of sizemis

m

n

,

we conclude that that

Œxnç.1Cx/mD

m

n

!

;

which is a restatement of the Binomial Theorem 14.6.4. Thus, we have proved
the Binomial Theorem without having to analyze the expansion of the expression
.1Cx/minto a sum of products.
These examples of counting donuts and deriving the binomial coefficients illus-
trate where generating functions get their power:

Generating functions can allow counting problems to be solved by algebraic

manipulation, and conversely, they can allow algebraic identities to be derived by

counting techniques.