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
Read more about this topic: Random Permutation Statistics
Famous quotes containing the words number of, number, permutations, roots and/or unity:
“A great number of the disappointments and mishaps of the troubled world are the direct result of literature and the allied arts. It is our belief that no human being who devotes his life and energy to the manufacture of fantasies can be anything but fundamentally inadequate”
—Christopher Hampton (b. 1946)
“Hence, a generative grammar must be a system of rules that can iterate to generate an indefinitely large number of structures. This system of rules can be analyzed into the three major components of a generative grammar: the syntactic, phonological, and semantic components.”
—Noam Chomsky (b. 1928)
“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)
“Where the world ends
The mind is made unchanging, for it finds
Miracle, ecstasy, the impossible hope,
The flagstone under all, the fire of fires,
The roots of the world.”
—William Butler Yeats (1865–1939)
“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)