358
GENERATING
5
FUNCTIONS
Find a generating function S(z) such that
[z”l S(z) = x (;) ( , I , , ) . k
Basics 6
Show that the recurrence (7.32) can be solved by the repertoire method, without using generating functions.
7 Solve the recurrence 40
= 1;
gn = gn I
+29,-2+...+ng0,
for n > 0.
8
What is [z”] (ln(1 - z))z:‘(l - z)~+‘?
9
Use the result of the previous exercise to evaluate xE=, HkHnpk.
10
Set r = s = -l/2 in identity (7.61) and then remove all occurrences of l/2 by using tricks like (5.36). What amazing identity do you deduce?
11 This problem, whose three parts are independent, gives practice in the
manipulation of generating functions. We assume that A(z) = x:, anzn, B(z) = t, bnzn, C(z) = tncnzn, and that the coefficients are zero for negative n. a
If ‘TX = tj+,Zk
b
If nb, = LET0 2kak/(n - k)!, express A in terms of B.
C
If r is a real number and if a, = IL=, (‘+kk)bnpk, express A in terms of B; then use your formula to find coefficients fk(r) such that bn = x;=, fk(T)
ojbk, express C in terms of A and B.
an- k.
12 How many ways are there to put the numbers {l ,2,. . . ,2n} into a 2 x n array so that rows and columns are in increasing order from left to right and from top to bottom? For example, one solution when n = 5 is 1 3 (
2 4 5 8 6 7 910 > '
13 Prove Raney’s generalized lemma, which is stated just before (7.6~). 14 Solve the recurrence
go = 0,
91
=
1, gkgn-k,
by using an exponential generating function.
for n > 1,
I deduce that Clark Kent is really superman.
