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:

    “After a certain number of years our faces become our biographies. We get to be responsible for our faces.”
    —Cynthia Ozick (b. 1928)

    “The growing good of the world is partly dependent on unhistoric acts; and that things are not so ill with you and me as they might have been, is half owing to the number who lived faithfully a hidden life, and rest in unvisited tombs.”
    —George Eliot [Mary Ann (or Marian)

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

    “Our roots are in the dark; the earth is our country. Why did we look up for blessing—instead of around, and down? What hope we have lies there. Not in the sky full of orbiting spy-eyes and weaponry, but in the earth we have looked down upon. Not from above, but from below. Not in the light that blinds, but in the dark that nourishes, where human beings grow human souls.”
    —Ursula K. Le Guin (b. 1929)

    “I therefore, the prisoner in the Lord, beg you to lead a life worthy of the calling to which you have been called, with all humility and gentleness, with patience, bearing with one another in love, making every effort to maintain the unity of the Spirit in the bond of peace.”
    —Bible: New Testament, Ephesians 4:1-3.