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:

    “A good marriage ... is a sweet association in life: full of constancy, trust, and an infinite number of useful and solid services and mutual obligations.”
    —Michel de Montaigne (1533–1592)

    “Mining today is an affair of mathematics, of finance, of the latest in engineering skill. Cautious men behind polished desks in San Francisco figure out in advance the amount of metal to a cubic yard, the number of yards washed a day, the cost of each operation. They have no need of grubstakes.”
    —Merle Colby, U.S. public relief program (1935-1943)

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

    “The Plains are not forgiving. Anything that is shallow—the easy optimism of a homesteader; the false hope that denies geography, climate, history; the tree whose roots don’t reach ground water—will dry up and blow away.”
    —Kathleen Norris (b. 1947)

    “The Puritans, to keep the remembrance of their unity one with another, and of their peaceful compact with the Indians, named their forest settlement CONCORD.”
    —Ralph Waldo Emerson (1803–1882)