Random Permutation Statistics - Number of Permutations That Are mth Roots of Unity

Number of Permutations That Are mth Roots of Unity

This generalizes the concept of an involution. An mth root of unity is a permutation σ so that σm = 1 under permutation composition. Now every time we apply σ we move one step in parallel along all of its cycles. A cycle of length d applied d times produces the identity permutation on d elements (d fixed points) and d is the smallest value to do so. Hence m must be a multiple of all cycle sizes d, i.e. the only possible cycles are those whose length d is a divisor of m. It follows that the EGF g(x) of these permutations is

When m = p, where p is prime, this simplifies to

n! g(z) = n! \sum_{a+pb=n} \frac{1}{a! \; p^b \; b!} = n! \sum_{b=0}^{\lfloor n/p \rfloor} \frac{1}{(n-pb)! \; p^b \; b!}.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words number of, number, permutations, roots and/or unity:

    “It is always possible to bind together a considerable number of people in love, so long as there are other people left over to receive the manifestations of their aggression.”
    —Sigmund Freud (1856–1939)

    “It is not the number of years we have behind us, but the number we have before us, that makes us careful and responsible and determined to find out the truth about everything.”
    —George Bernard Shaw (1856–1950)

    “The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
    —Jean Baudrillard (b. 1929)

    “You know, honey, us colored folks is branches without roots and that makes things come round in queer ways.”
    —Zora Neale Hurston (1891–1960)

    “Jesus abolished the very concept of “guilt”Mhe denied any cleavage between God and man. He lived this unity of God and man as his “glad tidings” ... and not as a prerogative!”
    —Friedrich Nietzsche (1844–1900)