Mathematics for Computer Science

15.2. Counting with Generating Functions 629

15.2 Counting with Generating Functions

Generating functions are particularly useful for representing and counting the num-

ber of ways to selectnthings. For example, suppose there are two flavors of donuts,

chocolate and plain. Letdnbe the number of ways to selectnchocolate or plain

flavored donuts.dnDnC 1 , because there arenC 1 such donut selections—all

chocolate, 1 plain andn 1 chocolate, 2 plain andn 2 chocolate,... , all plain. We

define a generating function,D.x/, for counting these donut selections by letting

the coefficient ofxnbedn. This gives us equation (15.5)

D.x/D

1

.1x/^2

: (15.6)

15.2.1 Apples and Bananas too

More generally, suppose we have two kinds of things—say, apples and bananas—

and some constraints on how many of each may be selected. Say there areanways

to selectnapples andbnways to selectnbananas. The generating function for

counting apples would be

A.x/WWD

X^1

nD 0

anxn;

and for bananas would be

B.x/WWD

X^1

nD 0

bnxn:

Now suppose apples come in baskets of 6, so there is no way to select 1 to 5

apples, one way to select 6 apples, no way to select 7, etc. In other words,

anD

(

1 ifnis a multiple of 6;

0 otherwise:

In this case we would have

A.x/D 1 Cx^6 Cx^12 C


Cx6nC




D 1 CyCy^2 C


CynC


 whereyDx^6 ;

D

1

1 y

D

1

1 x^6

:

Let’s also suppose there are two kinds of bananas—red and yellow. Now,bnD

nC 1 by the same reasoning used to count selections ofnchocolate and plain