
In Many Circles. Permutations as Products of Cycles. 105
Sometimes an alternative form of f(x, u) is easier to use.
PROPOSITION 3.32
We have
f(x, u)=
n≥0
(x)
n
u
n
n!
.
PROOF Immediate from Corollary 3.29.
The nice, compact form of the double generating function f(x, u)results
in a plethora of recurrence relations on the numbers s(n, k). These recur-
sive formulae are sometimes classified into three sets, triangular, vertical,and
horizontal recurrences. These names are based on the arrays of the numbers
s(n, k)involved.
A triangular recurrence is readily obtained from Lemma 3.19. It is
s(n, k)=s(n − 1,k− 1) − (n − 1)s(n − 1,k), (3.4)
where n ≥ 1.
Now we are go