Random Permutation Statistics - Derangements Containing An Even and An Odd Number of Cycles

Derangements Containing An Even and An Odd Number of Cycles

We can use the same construction as in the previous section to compute the number of derangements containing an even number of cycles and the number containing an odd number of cycles. To do this we need to mark all cycles and subtract fixed points, giving

g(z, u) = \exp\left( - u z + u \log \frac{1}{1-z} \right) = \exp(-uz) \left( \frac{1}{1-z} \right)^u.

Now some very basic reasoning shows that the EGF of is given by

q(z) = \frac{1}{2} \times g(z, -1) + \frac{1}{2} \times g(z, 1) = \frac{1}{2} \exp(-z) \frac{1}{1-z} +\frac{1}{2} \exp(z) (1-z).

We thus have

D_0(n) = n! q(z) = \frac{1}{2} n! \sum_{k=0}^n \frac{(-1)^k}{k!} + \frac{1}{2} n! \frac{1}{n!} - \frac{1}{2} n! \frac{1}{(n-1)!}

which is

\frac{1}{2} n! \sum_{k=0}^n \frac{(-1)^k}{k!} + \frac{1}{2} (1-n) \sim \frac{1}{2e} n! + \frac{1}{2} (1-n).

Subtracting from, we find

The difference of these two ( and ) is

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words odd, number and/or cycles:

    “His reversed body gracefully curved, his brown legs hoisted like a Tarentine sail, his joined ankles tacking, Van gripped with splayed hands the brow of gravity, and moved to and fro, veering and sidestepping, opening his mouth the wrong way, and blinking in the odd bilboquet fashion peculiar to eyelids in his abnormal position. Even more extraordinary than the variety and velocity of the movements he made in imitation of animal hind legs was the effortlessness of his stance.”
    —Vladimir Nabokov (1899–1977)

    “Among a hundred windows shining
    dully in the vast side
    of greater-than-palace number such-and-such
    one burns
    these several years, each night
    as if the room within were aflame.”
    —Denise Levertov (b. 1923)

    “The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
    —Linda Goodman (b. 1929)