文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-tzu Juan
Chapter 9 Generating Functions
§ The Exponential Generating
Function
Slides for a Course Based on the Text
Discrete & Combinatorial Mathematics (5th Edition)
by Ralph P. Grimaldi
(c) Spring 2007, Justie Su-tzu Juan 1
Def : Let a0, a1, a2, …, be a sequence of real numbers.
2  i
The function f(x) = a + a x + a x + …= i 0 a x
§ The Exponential Generating0 Function1 2 i
is called the generating function for the given sequence.
ordinary generating function  selection problem
?  arrangement problem
(1 + x)n = C(n, 0) + C(n, 1)x + C(n, 2)x2 + C(n, 3)x3 + …+ C(n, n)xn
x x2 x3 xn
P(n, 0) P(n,1) P(n, 2) P(n, 3) P(n, n)
1! 2! 3! n!
Def : For a sequence a0, a1, a2, … of real numbers,
x 2 x 3  x i
f (x) a0 a1 x a2 a3 ai
2! 3! i0 i!
is called the exponential generating function for the given
sequence. (與P-418 Def 比較)
(c) Spring 2007, Justie Su-tzu Juan 2
§ The Exponential Generating Function
Ex : Maclaurin series for ex:
x 2 x 3 x4  xi
e x 1x 
2! 3! 4! i0 i!
 ex is the exponential generating function for the sequence 1, 1, 1, ….
(ex is the generating function for the sequence 1, 1, 1/2!, 1/3!, 1/4!,…)
(c) Spring 2007, Justie Su-tzu Juan 3
§ The Exponential Generating Function
Ex : In how many ways can four of the letters in ENGINE be
arranged?
Sol. (2/1) E 2, N 2, G 1, I 1:
E E N N 4!/(2!2!) E G N N 4!/2!
E E G N 4!/2! E I N N 4!/2!
E E I N 4!/2! G I N N 4!/2!
E E G I 4!/2! E I G N 4!
E  1 + x + (x2/2!)
N  1 + x + (x2/2!)
G  1 + x
I  1 + x
 the exponential generating function is f(x) = [1 + x + (x2/2!)]2(1 + x)2
claim: the required answer = the coefficient of x4/4! in f(x)
(c) Spring 2007, Justie Su-tzu Juan 4
§ The Exponential Generating Function
Sol. (2/2)
claim: the required an