文档介绍：Computer Science and Information Engineering
National Chi Nan University
Combinatorial Mathematics
Dr. Justie Su-tzu Juan
Chapter 9 Generating Functions
§ Definition and Examples:
Calculational Techniques (2)
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
§ Definition and Examples: Calculational Techniques
Table : (i) For all m, n Z+, a R
n n n n 2 n n
1) (1 + x) = ( 0) + ( 1)x + ( 2)x + …+ ( n)x
n n n n 2 2 n n n
2) (1 + ax) = ( 0) + ( 1)ax + ( 2)a x + …+ ( n)a x
m n n n m n 2m n nm
3) (1 + x ) = ( 0) + ( 1)x + ( 2)x + …+ ( n)x
4) (1 xn+1)/(1 x) = 1 + x + x2 + …+ xn
2  i
5) 1/(1 x) = 1 + x + x + …=i0 x
n n n n n 2
6) 1/(1 + x) = (1 + x) = ( 0) + ( 1)x + ( 2)x + …

n i i n+i1 i
=i 0 ( i)x =i 0 (1) ( i)x
n n n n n 2
7) 1/(1 x) = (1 x) = ( 0) + ( 1)(x) + ( 2)(x) + …

n i i n+i1 i
=i0 ( i)(x) =i 0 (1) ( i)(x)
 n+i1 i
=i 0 ( i)x
 i  i
(ii) If f(x) = i0 aix , g(x) = i 0 bix and h(x) = f(x)g(x),
 i
then h(x) =i 0cix , where k 0,
k
ck = a0bk + a1bk1 + …+ ak1b1 + akb0 =i 0 aibki
(c) Spring 2007, Justie Su-tzu Juan 2
§ Definition and Examples: Calculational Techniques
Ex : In how many ways can we select, with repetitions
allowed, r objects from n distinct objects?
Sol.
0 ~ r 0 ~ r … 0 ~ r
object 1 object 2 object n
 the . is f(x) = (1 + x + x2 + …)n
∴ the answer = the coefficient of xr in f(x) = ?
n
 1  1 
2 n  n+i1 i
∵(1 + x + x + …) ==n =i 0 ( i)x
1 x 1 x 
n+r1
∴? = ( r)
(Found in Chapter 1)
(c) Spring 2007, Justie Su-tzu Juan 3
§ Definition and Examples: Calculational Techniques
Ex : Use G. F. to solve the problem of counting the
compositions of n Z+.
Solve.
# of 1-summand = the coef. of xn in (x + x2 + …+ xn + …) = 1
# of 2-summands = the coef