Mathematics for Computer Science

Chapter 15 Generating Functions630

donuts, and by (15.6) we have

B.x/D

1

.1x/^2

:

So how many ways are there to select a mix ofnapples and bananas? First, we
decide how many apples to select. This can be any numberkfrom 0 ton. We can
then select these apples inakways, by definition. This leavesnkbananas to
be selected, which by definition can be done inbnkways. So the total number
of ways to selectkapples andnkbananas isakbnk. This means that the total
number of ways to select some sizenmix of apples and bananas is

a 0 bnCa 1 bn 1 Ca 2 bn 2 C


Canb 0 : (15.7)

15.2.2 Products of Generating Functions

Now here’s the cool connection between counting and generating functions: ex-
pression (15.7) is equal to the coefficient ofxnin the productA.x/B.x/.
In other words, we’re claiming that

Rule(Product).

Œxnç.A.x/
B.x//Da 0 bnCa 1 bn 1 Ca 2 bn 2 C


Canb 0 : (15.8)

To explain the generating function Product Rule, we can think about evaluating
the productA.x/
B.x/by using a table to identify all the cross-terms from the
product of the sums:

b 0 x^0 b 1 x^1 b 2 x^2 b 3 x^3 :::

a 0 x^0 a 0 b 0 x^0 a 0 b 1 x^1 a 0 b 2 x^2 a 0 b 3 x^3 :::

a 1 x^1 a 1 b 0 x^1 a 1 b 1 x^2 a 1 b 2 x^3 :::

a 2 x^2 a 2 b 0 x^2 a 2 b 1 x^3 :::

a 3 x^3 a 3 b 0 x^3 :::

::

: :::

In this layout, all the terms involving the same power ofxlie on a 45-degree sloped
diagonal. So, the index-ndiagonal contains all thexn-terms, and the coefficient of