Mathematics for Computer Science

Chapter 15 Generating Functions632

15.2.4 Counting Donuts with the Convolution Rule

We can use the Convolution Rule to derive in another way the generating function
D.x/for the number of ways to select chocolate and plain donuts given in (15.6).
To begin, there is only one way to select exactlynchocolate donuts. That means
every coefficient of the generating function for selectingnchocolate donuts equals
one. So the generating function for chocolate donut selections is1=.1x/; likewise
for the generating function for selecting only plain donuts. Now by the Convolution
Rule, the generating function for the number of ways to selectndonuts when both
chocolate and plain flavors are available is

D.x/D

1

1 x

1

1 x

D

1

.1x/^2

:

So we have derived (15.6) without appeal to (15.5).
Our application of the Convolution Rule for two flavors carries right over to the
general case ofkflavors; the generating function for selections of donuts whenk
flavors are available is1=.1x/k. We already derived the formula for the number
of ways to select andonuts whenkflavors are available, namely,

nC.k1/

n

from
Corollary 14.5.3. So we have

Œxnç



1

.1x/k



D

nC.k1/

n

!

: (15.10)

Extracting Coefficients from Maclaurin’s Theorem

We’ve used a donut-counting argument to derive the coefficients of1=.1x/k,
but it’s instructive to derive this coefficient algebraically, which we can do using
Maclaurin’s Theorem:

Theorem 15.2.1(Maclaurin’s Theorem).

f.x/Df.0/Cf^0 .0/xC

f^00 .0/

2Š

x^2 C

f^000 .0/

3Š

x^3 C


C

f.n/.0/

nŠ

xnC


:

This theorem says that thenth coefficient of1=.1x/kis equal to itsnth deriva-
tive evaluated at 0 and divided bynŠ. Computing thenth derivative turns out not to
be very difficult

dn

dnx

1

.1x/k

Dk.kC1/


.kCn1/.1x/.kCn/