Combinatorics of Permutations, 2nd Edition

In Many Circles. Permutations as Products of Cycles. 145

If r = 0, then the proof is very similar, but instead of simply

adding the m equations obtained by setting x = z

t

in (3.3), we

multiply each such equation by z

−rt

, and then sum them over t =

0, 1, ···,m− 1. The only change is that on the left-hand side, all

summands c(n, k)(z

t

)

k

will cancel, except for those in which k is

congruent to r modulo m.

22. (a) See On a balanced property of derangements [52]. They key idea

is that the polynomial G

n,r

(x)/n! (as defined in Problem Plus 10)

takes very small values for x = −1, −2, ···, −r if r is small com-

pared to n. Hence this polynomial must have a root close to such

negative integers.

(b) The probability that the number k of cycles of a randomly selected ...