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)
“Can a woman become a genius of the first class? Nobody can know unless women in general shall have equal opportunity with men in education, in vocational choice, and in social welcome of their best intellectual work for a number of generations.”
—Anna Garlin Spencer (1851–1931)
“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)
“He who sins easily, sins less. The very power
Renders less vigorous the roots of evil.”
—Ovid (Publius Ovidius Naso)
“The unity of effect or impression is a point of the greatest importance. It is clear, moreover, that this unity cannot be thoroughly preserved in productions whose perusal cannot be completed at one sitting.”
—Edgar Allan Poe (1809–1849)