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 coefficient of xnyk in this expression. The coefficient of
xn is
y(FIn−1
+
JKn−1)
.
This is a series involving y but not x. We want the coefficient of
yk
in this series. The answer, which is obtained after some gruesome
Previous Page Next Page