Discrete Mathematics

-- Chapter 9: Generating Function

Hung-Yu Kao (高宏宇)

Department of Computer Science and Information Engineering,
N
Nationall Cheng
Ch Kung
K University
U
 Outline
z Calculational Techniques
z Partitions of Integers
z The Exponential Generating Function
z The Summation Operator

2009 Spring Discrete Mathematics – CH9 2

 Enumeration again
z Chapter 1: c1+c2+c3+c4=25, where ci>= 0
z Chapter 8: c1+c2+c3+c4=25,
=25 where 10>ci>= 0
z In chapter 9, c2 to be even and c3 to be a multiple
off 3

z the coefficient xy2 in (x+y)3

z ffi i t x4 in
th coefficient
the ( + 2)(x
i (x+x )( 2+x
+ 3+x
+ 4)(1+x+2x
)(1+ +2 2)

2009 Spring Discrete Mathematics – CH9 3

 9.1 Introductory Examples
z Ex 9.1 :
z One mother buys 12 oranges
f three
for th children,
hild Grace,
G Mary,
M
and Frank.
z Grace gets at least four, and Mary and Frank gets at least two,
but Frank gets no more than five.
z Solution
z c1 + c2 + c3 = 12, where 4 ≤ c1 ,2 ≤ c2 , and 2 ≤ c3 ≤ 5
z Generating function:
( 4+ x5+ x6+ x7+ x8)(x
f( ) = (x
f(x) )( 2+ x3+x+ 4+ x5+ x6)(x)( 2+ x3+x
+ 4+ x5)
product xjxjxk → every triple (i, j, k)
z The coefficient of x12 in f(
f(x)) yields
y the solution.

2009 Spring Discrete Mathematics – CH9 4

 Introductory Examples
z Ex 9.2 :
z There is an unlimited number of red, green, white, and black jelly
beans.
z In how many ways can we select 24 jelly beans so that we have an
even number of white beans and at least six black ones?
z Solution
z red (green): 1+ x1+ x2+….+ x23+ x24
z white: 1+ x2+ x4+….+ x22+ x24
z black: x6+ x7+….+ x23+ x24
z Generating function:
(1+ x1+ x2+….+
f(x) = (1 …. x23+ x24)2(1 (1+ x2+ x4+….+
…. x22+ x24)
(x6+ x7+….+ x23+ x24)
z The coefficient of x24 in f(x) is the answer.

2009 Spring Discrete Mathematics – CH9 5

 Introductory Examples
z Ex 9.3 : How
H many nonnegative
ti integer
i t solutions
l ti are there
th forf
c1+c2+c3+c4 = 25?
z Solution
z Alternatively, in how many ways 25 pennies can be distributed among
four children?
z Generating function:
f(x) = (1+ x1+ x2+…+ x24+ x25)4 (polynomial)
z The coefficient of x25 is the solution.
z Note:
z g(x) = (1+ x1+ x2+…+ x24+ x25 + x26+…)4 (power series)
can also generate the answer
∞
f ( x ) = ∑ an ( x − c ) n
n =0

z Easier to compute
p with a power
p series than with a polynomial
p y

2009 Spring Discrete Mathematics – CH9 6

 9.2 Definition and Examples:
Calculational Techniques

z Definition 9.1:

z Ex 9.4 : (1 + x ) n = (0n ) + (1n )x + (n2 )x 2 + ⋅ ⋅ ⋅ + (nn )x n

so,, ((1 + x))n is the g
generatingg function for the sequence q

(0n ), (1n ), (2n ),⋅ ⋅ ⋅, (nn ),0,0,0,⋅ ⋅ ⋅

2009 Spring Discrete Mathematics – CH9 7
 Definition and Examples:
p Calculational
Techniques
z Ex 9.5 :
a) (1 - xn+1)/(1 - x) is the generating function for the sequence 1,
1, 1,…, 1, 0, 0, 0,…, where the first n+1 terms are 1.
Q (1 − x n +1 ) = (1 − x )(1 + x + x 2 + ⋅ ⋅ ⋅ + x n ).
b) 1/(1 x) is the generating function for the sequence 1,
1/(1-x) 1 1,1 1,1
1,… Q while | x |< 1, 1− x = 1 + x + x + x + ⋅ ⋅ ⋅
1 2 3

c)) ( )2 is the ggeneratingg function for the sequence

1/(1-x) q 1,, 2,, 3,,
4,… Q d 1 = d (1 − x ) −1 = ( −1)(1 − x ) −2 ( −1)
dx 1− x dx

= 1
(1− x ) 2
= d
dx (1 + x + x 2 + x 3 + ⋅ ⋅ ⋅) = 1 + 2 x + 3 x 2 + 4 x 3 + ⋅ ⋅ ⋅

d) x/(1-x)2 is the generating function for the sequence 0,1,2,3,….

Q (1−xx ) 2 = 0 + 1x + 2 x 2 + 3x 3 + 4 x 4 + ⋅ ⋅ ⋅

2009 Spring Discrete Mathematics – CH9 8

 Definition and Examples:
p Calculational
Techniques
z Ex 9.5 :
e) (x+1)/(1-x)3 is the generating function for the sequence
12, 22, 32, 42,… d
Q dx x
(1− x ) 2
Q dx (1− x ) = dx (0 + x + 2 x + 3 x + ⋅ ⋅ ⋅)
d x d
2
2 3

= d
d
dx
x(1 − x) −2
x +1
= 1 + 2 2 x + 32 x 2 + 4 2 x 3 + ⋅ ⋅ ⋅
(1− x ) 3 = (1 − x) −2 + x(−2)(1 − x) −3 (−1)
(1− x ) + 2 x x +1
= =
(1− x ) 3
(1− x )3

f) x(x+1)/(1-x)3 is the generating function for the sequence

02, 12, 22, 32, 42,…
Q (x1(−xx+)13) = 0 + 1x + 2 2 x 2 + 32 x 3 + ⋅ ⋅ ⋅

2009 Spring Discrete Mathematics – CH9 9

 Definition and Examples:
p Calculational
Techniques
z Ex 9.5 :
g) Further extensions:

2009 Spring Discrete Mathematics – CH9 10

 Definition and Examples:
p Calculational
Techniques

z Ex 9.6 :
a)) 1/(1
( - ax)) is the generating
g g function for the sequence
q a0, a1, a2,
a3,…
b) f(x) = 1/(1- x) is the generating function for the sequence 1, 1,
1, 1,… Then
z g(x) = f(x) - x2 is the generating function for the
sequence 1, 1 11, 00, 1,
1 11, 11,…
z h(x) = f(x) + 2x3 is the generating function for the
sequence 1, 1, 1, 3, 1, 1,…
c) Can we find a generating function for the sequence 0, 2, 6, 12,
20, 30, 42,…?

2009 Spring Discrete Mathematics – CH9 11

 Definition and Examples:
p Calculational
Techniques

z Ex 9.6 :
c) Observe 0,, 2,, 6,, 12,, 20,...
,
a0 = 0 = 0 2 + 0, a1 = 2 = 12 + 1,
a2 = 6 = 2 2 + 2, a3 = 12 = 32 + 3,
a4 = 20 = 4 2 + 4, ⋅ ⋅ ⋅
∴ an = n 2 + n
x ( x + 1) x x ( x + 1) + x (1 − x )
+ = = 2x
(1 − x )3 (1 − x ) 2 (1 − x )3 (1 − x )3
is the generating function.

2009 Spring Discrete Mathematics – CH9 12

 Extension of Binomial Theorem

z Binomial theorem: (1 + x ) n = ( )+ ( )x + ( )x
n
0
n
1
n
2
2
+ ⋅⋅⋅ + ( )x
n
n
n

⎛n⎞ n! n( n − 1)( n − 2)...( n − r + 1)

z When n∈Z+, we have ⎜⎜ ⎟⎟ = =
⎝ r ⎠ r! ( n − r )! r!

z If n∈R, we define ⎛ n ⎞ n ( n − 1)( n − 2 )...( n − r + 1)

⎜⎜ ⎟⎟ =
⎝r⎠ r!

If n∈Z+, we have ⎛ − n ⎞ ( −n )( − n − 1)( −n − 2)...( −n − r + 1)

z ⎜⎜ ⎟⎟ =
⎝ r ⎠ r!
( −1) r ( n )( n + 1)...(
) ( n + r − 1)
=
r!
( −1) r ( n + r − 1)! ⎛ n + r − 1⎞
= = ( −1) r ⎜⎜
( n − 1)! ) r! ⎝ r ⎠

2009 Spring Discrete Mathematics – CH9 13

 Extension of Binomial Theorem

z Ex 9.7 :

(1-x)-n ?

2009 Spring Discrete Mathematics – CH9 14

 Extension of Binomial Theorem
z Ex 9.8 : Find the coefficient of x5 in (1-2x)-7.
z Solution
(1 − 2 x) −7
= ∑r =0
∞
( )(−2 x)
−7
r
r

The coefficient of x 5 :
( )(−2)
−7
5
5
= (−1) 5 ( )(−32) = (32)( )
7 + 5 −1
5
11
5

z Ex 9.9 : Find the coefficient of all xi in (1+3x)-1/3

2009 Spring Discrete Mathematics – CH9 15

 Definition and Examples:
p Calculational
Techniques

z Determine the coefficient of x15 in f(x) =

Ex 9.10 :
(x2+x3+x4+…)4.
z Solution
z (x2+x3+x4+…) = x2(1+x+x2+…) = x2/(1-x)
z f(x)=(x2/(1-x))4 = x8/(1-x)4
z Hence the solution is the coefficient of x7 in (1-x)-4:
C( 4 7)(
C(-4, 1)7 = (-1)
7)(-1) ( 1)7C(4+7-1,
C(4+7 1 7)( 1)7 = C(10,
7)(-1) C(10 7) = 120
120.

2009 Spring Discrete Mathematics – CH9 16

2009 Spring Discrete Mathematics – CH9 17
 check n=1

2009 Spring Discrete Mathematics – CH9 18

 Definition and Examples:
p Calculational
Techniques

z Ex 9.11 :In how many ways can we select, with

repetition allowed, r objects from n distinct objects?
z Solution
z For each object (with repetitions), 1+x+x2+… represents the possible
choices
h i for
f th
thatt object
bj t (namely
( l none, one, two,…)
t )
z Consider all of the n distinct objects, the generating function is f(x) =
((1+x+x2+…))n n ∞
⎛ n + i − 1⎞
⎛ 1 ⎞
(1 + x + x 2 + ⋅ ⋅ ⋅) n = ⎜ ⎟ = 1 = ∑ ⎜⎜ ⎟ .
x i

⎝1− x ⎠ (1 − x ) n i =0 ⎝ i ⎠

z The answer is the coefficient of xr in f(x), ( )

n + r −1
r
.

2009 Spring Discrete Mathematics – CH9 19

 Definition and Examples:
p Calculational
Techniques
z Ex 9.12 : Counting the compositions of a positive integer n.
z Solution
z E.g., n = 4
z One-summand: (x1+ x2+x3+x4+…) = [x/(1-x)], coefficient of x4 =1
z Two-summand: (x1+ x2+x3+x4+…)2 = [x/(1-x)]2, coefficient of x4 =3
z Th
Three-summand: ( 1+ x2+x
d (x + 3+x
+ 4+…)
+ )3 = [x/(1-x)]
[ /(1 )]3, coefficient
ffi i t off x4 =33
z Four-summand: (x1+ x2+x3+x4+…)4 = [x/(1-x)]4, coefficient of x4 =1
z The number of compositions of 4: coefficient of x4 in
∑
4
[ x /((1 − x )]i
i =11

How about n=5?

2009 Spring Discrete Mathematics – CH9 20

 Definition and Examples:
p Calculational
Techniques
z Ex 9.12 : Counting the compositions of a positive integer n.
z The number of ways to form an integer n is the coefficient of xn in the
g ggenerating
following g function.

∑i =1 ( x1 + x 2 + x 3 + ...)i = ∑i =1[ x /(1 − x)]i

∞ ∞

2009 Spring Discrete Mathematics – CH9 21

 Definition and Examples:
p Calculational
Techniques
z Ex 9.14 : In how many ways can a police captain distribute 24 rifle
shells to four police officers, so that each officer gets at least three
shells
h ll but
b t nott more than
th eight.
i ht
z Solution

z f(x)= (x3+x4+ x5+ x6+x7+x8)4

= x12(1+x+x2+x3+x4+x5)4
= x12[(1
[(1-xx6)/(1 x)]4
)/(1-x)]
z The answer is the coefficient of x12 in (1-x6)4(1-x)-4

= [1 − (14 )x 6 + (42)x12 − (34)x18 + x 24 ][(0−4)+ (1−4)(− x) + (−24)(− x) 2 + ⋅ ⋅ ⋅]

⎛ − 4⎞ ⎛ 4 ⎞⎛ − 4 ⎞ ⎛ 4 ⎞⎛ − 4 ⎞ ⎛15 ⎞ ⎛ 4 ⎞⎛ 9 ⎞ ⎛ 4 ⎞
[⎜⎜ ( −1) − ⎜⎜ ⎜⎜
12
( −1) + ⎜⎜ ⎜⎜
6
] = [⎜⎜ − ⎜⎜ ⎜⎜ + ⎜⎜ ] = 125
⎝ ⎠
12 ⎝ ⎠⎝ ⎠
1 6 ⎝ ⎠⎝ ⎠
2 0 ⎝ ⎠ ⎝ 1 ⎠⎝ 6 ⎠ ⎝ 2 ⎠
12

2009 Spring Discrete Mathematics – CH9 22

 Definition and Examples:
p Calculational
Techniques
1
z Ex 9.16 : Determine the coefficient of x8 in .
( x − 3)( x − 2) 2
z Solution

2009 Spring Discrete Mathematics – CH9 23

 Definition and Examples:
p Calculational
Techniques
z 9 17 :
E 9.17
Ex How many ffour-element
H l t subsets
b t off S = {1,
{1 2,…,
2
15} contains no consecutive integers?
Solution
z E.g., one subset {1, 3, 7, 10}, 1≤1<3<7<10 ≤15,
difference 0, 2, 4, 3, 5, difference sum = 14.
z These suggest the integer solutions to c1+c2+c3+c4+c5 =14
14
where 0 ≤ c1, c5 and 2 ≤ c2, c3, c4.
z The answer is the coefficient of x14 in
f(x) = (1+x+x2+x3+…)(x
+ )(x2+x3+x4+…) + )3(1+x+x2+x3+…)
+ )
= x6(1-x)-5
z The coefficient of x8 in (1-x)-5.
⎛ − 5⎞ ⎛ 5 + 8 − 1⎞ ⎛12 ⎞
⎜⎜ ⎟⎟(−1)8 = ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ = 495
⎝ ⎠
8 ⎝ 8 ⎠ ⎝8⎠

2009 Spring Discrete Mathematics – CH9 24

 Convolution of Sequences
z Ex 9.19 : Let
z f(x) = x/(1-x)2 = 0+1x+2x2+3x3+…, for the sequence ak= k
z g(x) = x(x+1)/(1
x(x+1)/(1-x)x)3 = 0+12x+22x2+32x3+ …, for the sequence bk= k2
z h(x) = f(x)g(x)
= a0b0 + (a0b1+a1b0)x + (a0b2+a1b1+a2b0)x2 + …, for the sequence ck =
a0bk+a1bk-1+a2bk-2+ …+ak-2b2+ak-1b1+akb0
z
ck = ∑ i = 0 i ( k − i ) 2 .
k
c0= 0×02
0 12 +1×0
c1= 0×1 +1 02 = 0
c2= 0×22 +1×12+2×02 = 1
c3= 6

z The sequence c0, c1, c2, … is the convolution of the sequences a0, a1,
a2, … and b0, b1, b2, …

2009 Spring Discrete Mathematics – CH9 25

 Convolution of Sequences
z Ex 9.20 : Let
z f(x) = 1/(1-x) = 1+x+x2+x3+ …
z g(x) = 1/(1+x) = 1-x+x2-x3+ …
z h(x) = f(x)g(x)
= 1/[(1-x)(1+x)] 1/(1 x2) = 1+x2+x4+x6+ …
1/[(1 x)(1+x)] = 1/(1-x
z The sequence 1, 0, 1, 0, … is the convolution of the
sequences 1,
1 1,
1 1,
1 1,
1 … and 1,1 -1,
1 1,
1 -1,
1 …

2009 Spring Discrete Mathematics – CH9 26

 9.3 Partition of Integers
z p(n):
( ) th
the number
b off partitioning
titi i a positive
iti integer
i t n

z The number of 1’s is 0 or 1 or 2 or 3…. The power series is

1
1+x+x 2+x3+x4+….

z The number of 2’s can be kept tracked by the power series

1+x2+x4+x6+x8+….
z For n, the number of 3’s can be kept tracked by the power series
1+x3+x6+x9+x12+….

2009 Spring Discrete Mathematics – CH9 27

 Partition of Integers
z Determine p(10)
z The coefficient of x10 in f(x)
=(1+x+x
( 2+x3+…)(1+x
…)( 2+x4+x6+…)(1+x
…)( 3+x6+x9+…)…
…)…
(1+x10+x20+…)
1 1 1 1 1
f ( x) = ⋅ ⋅ ⋅ = ∏10
i =1
(1 − x) (1 − x 2 ) (1 − x 3 ) (1 − x10 ) (1 − x i )

z By the coefficient of xn in P ( x ) = ∏ i∞=1 1 i , we get the sequence

(1− x )
p(0),
(0) p(1),
(1) p(2),
(2) p(3),
(3) …

2009 Spring Discrete Mathematics – CH9 28

 Partition of Integers
z Ex 9.21 : Find the generating function for the number of ways an
advertising agent can purchase n minutes of air time if the time
slots come in blocks of 30,30 60,
60 or 120 seconds.
seconds
Solution
z Let 30 seconds represent one time unit.
z Find integer solutions to a+2b+4c = 2n
z Generating function:
f(x)= (1+x+x2+x3+x4+…)(1+x2+x4+x6+x8+…)( 1+x4+x8+x12+…)
= 1 1 1
.
(1 − x ) (1 − x 2 ) (1 − x 4 )

z Answer: the coefficient of x2n is the number of partitions of 2n into

1’s, 2’s, and 4’s.

2009 Spring Discrete Mathematics – CH9 29

 Partition of Integers
z Ex 9.22 : Find the generating function for pd(n), the number of partitions of
a positive integer n into distinct summands. 6 = 1+5
z One time of occurrence per summand 6 = 1+2+3
z Pd(x) = (1+x)(1+x2)(1+x3)..… 6 = 2+4
z Ex 9.23 : Find the generating function for po(n), the number of partitions of
a positive
i i integer
i n into
i odd
dd summands.
d
z Po(x) = (1+x+x2+x3+…)(1+x3+x6+…)(1+x5+x10+…)…
z = 1/(1 x) × 1/(1
1/(1-x) 1/(1-xx3) × 1/(1
1/(1-xx5) × 1/(1
1/(1-xx7) × ...
z Pd(x) = Po(x) ?
6=1 1+1+1+3
1 1 3
6 = 1+5
6 = 3+3

2009 Spring Discrete Mathematics – CH9 30

 Partition of Integers

z Ex 9.24 :Find the generating function for the number of

partitions of a positive integer n into odd summands and
occurring an odd number of times.
Solution 6 = 1+1+1+3
6 = 1+5
f(x) = (1+x+x3+x5+ …)(1+x3+x9+x15+ …) 6 = 3+3
(1+x5+x15+x25+ …)…
⎛
∞ ∞
( 2 k +1)( 2 i +1) ⎞
=
∏ ⎜ ∑
1 + x ⎟.
k =0 ⎝ i =0 ⎠

2009 Spring Discrete Mathematics – CH9 31

 Partition of Integers

z Ferrers graph uses rows of dots to represent a partition

of an integer
z In fig. 9.2, two Ferrers graphs are transposed each other
for the partitions of 14. 4
z (a) 14 = 4+3+3+2+1+1
z (b) 14 = 6+4+3+1
4
The number of partitions of an integer n
into m summands is equalq to the number
of partitions of n into summands where
m is the largest summand.

http://mathworld.wolfram.com/FerrersDiagram.html

2009 Spring Discrete Mathematics – CH9 32

 9.4 The Exponential Generating
F
Function
ti

2009 Spring Discrete Mathematics – CH9 33

 The Exponential Generating Function

z Ex 9.25 :Examining the Maclaurin series expansion for

ex, we find 2 3 ∞ i
x x x
ex = 1+ x + + + ⋅⋅⋅ = ∑
2! 3! i = 0 i!

so ex is the exponential generating function for the

sequence 1, 1, 1,….

2009 Spring Discrete Mathematics – CH9 34

 The Exponential Generating Function
z Ex 9.26 : In how many ways can four of the letters in ENGINE be
arranged?
Solution

z Using exponential generating function: f(x) = [1+x+(x2/2!)]2[1+x]2

z E, N: [1+x+(x2/2!)]
z G, I: [1+x]
z The answer is the coefficient of x4/4!.
/4!

2009 Spring Discrete Mathematics – CH9 35

 The Exponential Generating Function

z Ex 9.27 : Consider the Maclaurin series expansion of ex

and e-x.

2009 Spring Discrete Mathematics – CH9 36

 The Exponential Generating Function
z Ex 9.28 : A ship carries 48 flags, 12 each of the colors red, white,
blue and black. Twelve flags are placed on a vertical pole to
communicate signal to other ships.
z How many of these signals use an even number of blue flags
and an odd number of black flags?

2009 Spring Discrete Mathematics – CH9 37

 The Exponential Generating Function

z how many of these use at least three white flags or no white

flag at all?

2009 Spring Discrete Mathematics – CH9 38

 The Exponential Generating Function

2009 Spring Discrete Mathematics – CH9 39

 The Exponential Generating Function

z Ex 9.29 : A company hires 11 new employees, and they will

be assigned to four different subdivisions. Each subdivision
has at least one new
ne emplo
employee.
ee In how
ho many
man waysa s can
these assignments be made?
z Solution

z Onto function: g: X → Y where |X| = 11, |Y| = 4.

2009 Spring Discrete Mathematics – CH9 40

 9.5 The Summation Operator

z Let f(x) = a0+a1x+a2x2+a3x3+…. Then f(x)/(1-x)

generate the sequence of a0, a0+a1, a0+a1+a2,
a0+a1+a2+a3,… So we refer to 1/(1-x) as the summation
operator.

2009 Spring Discrete Mathematics – CH9 41

 The Summation Operator
Summation
z Ex 9.30 : operator
z 1/(1-x) is the generating function for the sequence 1, 1, 1, 1,
1
1,…
z [1/(1-x)]× [1/(1-x)] is the generating function for the sequence
1, 1+1, 1+1+1,… ⇒ 1, 2, 3,…
z x+x+ 2 is
i the
th generating
ti function
f ti for f the
th sequence 0,0 1,
1 1,
1 0,
0 0,
0
0,…
z (x+x2) × [1/(1-x)] is the generating function for the sequence 0,
1 2,
1, 2 2,
2 2,
2 2,
2 …
z (x+x2)/(1-x)2 is the generating function for the sequence 0, 1, 3,
5, 7, 9, 11, …
z (x+x2)/(1-x)3 is the generating function for the sequence 0, 1, 4,
9, 16, 25, 36, …

2009 Spring Discrete Mathematics – CH9 42

 The Summation Operator
z Ex 9.31 : Find a formula to express 02+12+22+…+n2 as a function of
n.
Solution

2009 Spring Discrete Mathematics – CH9 43

 The Summation Operator

2009 Spring Discrete Mathematics – CH9 44

 Homework
z 9.1:
z 9 2:
9.2:
z 9.3:
z 9.4:
z 9 5:
9.5:

2009 Spring Discrete Mathematics – CH9 45