Page 563 - Discrete Mathematics and Its Applications

542 8 / Advanced Counting Techniques

TABLE 1 Useful Generating Functions.
G(x) a k
n
k
(1 + x) n = C(n, k)x C(n, k)
k = 0
2 n
= 1 + C(n, 1)x + C(n, 2)x + ··· + x
n

k k
(1 + ax) n = C(n, k)a x C(n, k)a k
k = 0
2 2
n n
= 1 + C(n, 1)ax + C(n, 2)a x + ··· + a x
n
rk
r n
(1 + x ) = C(n, k)x C(n, k/r) if r | k; 0 otherwise
k = 0
r
= 1 + C(n, 1)x + C(n, 2)x 2r + ··· + x rn
n
1 − x n+1 k 2 n
= x = 1 + x + x + ··· + x 1if k ≤ n; 0 otherwise
1 − x
k = 0
∞
1 k 2
= x = 1 + x + x + ··· 1
1 − x
k = 0
∞
1 k k 2 2
= a x = 1 + ax + a x + ··· a k
1 − ax
k = 0
∞
1 rk r 2r
= x = 1 + x + x + ··· 1if r | k; 0 otherwise
1 − x r
k = 0
∞
1 k 2
= (k + 1)x = 1 + 2x + 3x + ··· k + 1
(1 − x) 2
k = 0
∞
1 k
= C(n + k − 1,k)x C(n + k − 1,k) = C(n + k − 1,n − 1)
(1 − x) n
k = 0
2
= 1 + C(n, 1)x + C(n + 1, 2)x + ···
∞
1 k k k k
= C(n + k − 1,k)(−1) x (−1) C(n + k − 1,k) = (−1) C(n + k − 1,n − 1)
(1 + x) n
k = 0
2
= 1 − C(n, 1)x + C(n + 1, 2)x − ···
∞
1 k k k k
= C(n + k − 1,k)a x C(n + k − 1,k)a = C(n + k − 1,n − 1)a
(1 − ax) n
k = 0
2 2
= 1 + C(n, 1)ax + C(n + 1, 2)a x + ···
∞ k 2 3
x x x
x
e = = 1 + x + + + ··· 1/k!
k! 2! 3!
k = 0
∞ k+1 2 3 4
(−1) x x x
k k+1
ln(1 + x) = x = x − + − + ··· (−1) /k
k 2 3 4
k = 1
Note: The series for the last two generating functions can be found in most calculus books when power series are discussed.