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:

    “The two great points of difference between a democracy and a republic are: first, the delegation of the government, in the latter, to a small number of citizens elected by the rest; secondly, the greater number of citizens and greater sphere of country over which the latter may be extended.”
    —James Madison (1751–1836)

    “In the end we beat them with Levi 501 jeans. Seventy-two years of Communist indoctrination and propaganda was drowned out by a three-ounce Sony Walkman. A huge totalitarian system ... has been brought to its knees because nobody wants to wear Bulgarian shoes.... Now they’re lunch, and we’re number one on the planet.”
    —P.J. (Patrick Jake)

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

    “There is nothing but is related to us, nothing that does not interest us,—kingdom, college, tree, horse, or iron show,—the roots of all things are in man.”
    —Ralph Waldo Emerson (1803–1882)

    “Civilization is a process in the service of Eros, whose purpose is to combine single human individuals, and after that families, then races, peoples and nations, into one great unity, the unity of mankind. Why this has to happen, we do not know; the work of Eros is precisely this.”
    —Sigmund Freud (1856–1939)