
202 Combinatorics of Permutations, Second Edition
for the vector space C[n]. In particular, P
i
(n) is a linear combination of
polynomials of the form (n + i)
j
. Therefore, using generating functions,
n≥0
P
i
(n)f(n + i)x
n
is a linear combination of generating functions of
the form
n≥0
(n + i)
j
f(n + i)x
n
(5.5)
with complex coefficients.
Compare formulae (5.4) and (5.5). We see that the left-hand side of
(5.5) almost agrees with x
j−i
u
(j)
, that is, they can only differ in finitely
many terms with all negative coefficients. Let the sum of these terms
be R
i
(x) ∈ x
−1
K[x
−1
], a Laurent-polynomial. If we multiply (5.1) by
x
n
and sum over all non-negative n,weget
0=
#
i
a
ij
x
j