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:

    “God ... created a number of possibilities in case some of his prototypes failed—that is the meaning of evolution.”
    —Graham Greene (1904–1991)

    “The said truth is that it is the greatest happiness of the greatest number that is the measure of right and wrong.”
    —Jeremy Bentham (1748–1832)

    “Motherhood in all its guises and permutations is more art than science.”
    —Melinda M. Marshall (20th century)

    “Look at this poet William Carlos Williams: he is primitive and native, and his roots are in raw forest and violent places; he is word-sick and place-crazy. He admires strength, but for what? Violence! This is the cult of the frontier mind.”
    —Edward Dahlberg (1900–1977)

    “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)