Mathematics for Computer Science

Chapter 15 Generating Functions648

Class Problems

Problem 15.5.
LetA.x/D

P 1

nD 0 anx

n. Then it’s easy to check that

anD

A.n/.0/

nŠ

;

whereA.n/is thenth derivative ofA. Use this fact (which you may assume) instead
of the Convolution Counting Principle 15.2.3, to prove that

1

. 1 x/k

D

X^1

nD 0

nCk 1

k 1

!

xn:

So if we didn’t already know the Bookkeeper Rule from Section 14.6, we could
have proved it from this calculation and the Convolution Rule for generating func-
tions.

Problem 15.6. (a)Let

S.x/WWD

x^2 Cx

.1x/^3

:

What is the coefficient ofxnin the generating function series forS.x/?

(b)Explain whyS.x/=.1x/is the generating function for the sums of squares.
That is, the coefficient ofxnin the series forS.x/=.1x/is

Pn

kD 1 k

(^2).
(c)Use the previous parts to prove that
Xn
kD 1
k^2 D
n.nC1/.2nC1/
6

:

Homework Problems

Problem 15.7.
We will use generating functions to determine how many ways there are to use
pennies, nickels, dimes, quarters, and half-dollars to givencents change.

(a)Write the generating functionP.x/for for the number of ways to use only
pennies to makencents.

(b)Write the generating functionN.x/for the number of ways to use only nickels
to makencents.