Chapter 15 Generating Functions630
donuts, and by (15.6) we have
B.x/D
1
.1 x/^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 leavesn kbananas to
be selected, which by definition can be done inbn kways. So the total number
of ways to selectkapples andn kbananas isakbn k. 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 CCanb 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 CCanb 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