Mathematics for Computer Science

Chapter 15 Generating Functions650

 She brings a positive number of songbirds, which always come in pairs.

 She may or may not bring her alligator, Freddy.

 She brings at least 2 cats.

 She brings two or more chihuahuas and labradors leashed together in a line.

LetPndenote the number of different collections ofnpets that can accompany
her, where we regard chihuahuas and labradors leashed in different orders as dif-
ferent collections.
For example,P 6 D 4 since there are 4 possible collections of 6 pets:

 2 songbirds, 2 cats, 2 chihuahuas leashed in line

 2 songbirds, 2 cats, 2 labradors leashed in line

 2 songbirds, 2 cats, a labrador leashed behind a chihuahua

 2 songbirds, 2 cats, a chihuahua leashed behind a labrador

(a)Let

P.x/WWDP 0 CP 1 xCP 2 x^2 CP 3 x^3 C

be the generating function for the number of Miss McGillicuddy’s pet collections.
Verify that

P.x/D

4x^6

.1x/^2 .12x/

:

(b)Find a closed form expression forPn.

Problem 15.11.
Every day in the life of Dangerous Dan is a disaster filled withmishaps.

 Dan may or may notspillhis breakfast cereal on his computer keyboard.

 Danblurtssomething foolish an even number of times.

 Danbreaksa sequence of two or more dinnerware items (where each item is

either a bowl or a plate or a cup.)