7. Appendix 81

and

H(x, y) = qxyG(x, y) + qxH(x, y) + qxy .

One can solve these equations for G(x, y) and H(x, y), obtaining

G(x, y) =

pxy(1 − qx + qxy)

1 − x + pqx2(1 − y2)

and

H(x, y) =

qxy(1 − px + pxy)

1 − x + pqx2(1 − y2)

.

Finally, note that

r(n, k) = f(n, p, k, S) + f(n, p, k, F ) ,

so

r(x, y, p) = G(x, y) + H(x, y) =

xy(1 − 2pqx(1 − y))

1 − x + pqx2(1 − y2)

,

giving us the required expression for r(x, y, p).

The above expression for the generating function r(x, y, p) allows

one to write an exact expression for rn,k. The expression for r(x, y, p)

is of the form

xy

A + Bx

1 + Dx + Ex2

where the capital letters represent expressions that do not involve x.

Using the algebraic method of partial fractions (usually first learned

in calculus to help integrate rational functions), one can write this

expression as

xy

F

1 − Ix

+

J

1 − Kx

.

The two summands can be rewritten, using geometric series, to obtain

xy(F + FIx +

FI2x2

+ . . . + J + JKx +

JK2x2

+ . . .) .

We want the coeﬃcient of xnyk in this expression. The coeﬃcient of

xn is

y(FIn−1

+

JKn−1)

.

This is a series involving y but not x. We want the coeﬃcient of

yk

in this series. The answer, which is obtained after some gruesome