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:

    “My idea is that the world outside—the so-called modern world—can only pervert and degrade the conceptions of the primitive instinct of art and feeling, and that our only chance is to accept the limited number of survivors—the one- in-a-thousand of born artists and poets—and to intensify the energy of feeling within that radiant centre.”
    —Henry Brooks Adams (1838–1918)

    “Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
    —Ralph Waldo Emerson (1803–1882)

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

    “Now fades the lasts long streak of snow,
    Now burgeons every maze of quick
    About the flowering squares, and thick
    By ashen roots the violets blow.”
    —Alfred Tennyson (1809–1892)

    “Hearing, seeing and understanding each other, humanity from one end of the earth to the other now lives simultaneously, omnipresent like a god thanks to its own creative ability. And, thanks to its victory over space and time, it would now be splendidly united for all time, if it were not confused again and again by that fatal delusion which causes humankind to keep on destroying this grandiose unity and to destroy itself with the same resources which gave it power over the elements.”
    —Stefan Zweig (18811942)