Random Permutation Statistics - Number of Permutations That Are Involutions

Number of Permutations That Are Involutions

An involution is a permutation σ so that σ2 = 1 under permutation composition. It follows that σ may only contain cycles of length one or two, i.e. the EGF g(z) of these permutations is

This gives the explicit formula for the total number of involutions among the permutations σ ∈ Sn:

 I(n) = n! g(z) = n! \sum_{a+2b=n} \frac{1}{a! \; 2^b \; b!}
= n! \sum_{b=0}^{\lfloor n/2 \rfloor} \frac{1}{(n-2b)! \; 2^b \; b!}.

Dividing by n! yields the probability that a random permutation is an involution.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words number of, number and/or permutations:

    “My idea is that the world outside—the so-called modern world—can only pervert and degrade the conceptions of the primitive instinct of art and feeling, and that our only chance is to accept the limited number of survivors—the one- in-a-thousand of born artists and poets—and to intensify the energy of feeling within that radiant centre.”
    —Henry Brooks Adams (1838–1918)

    “But however the forms of family life have changed and the number expanded, the role of the family has remained constant and it continues to be the major institution through which children pass en route to adulthood.”
    —Bernice Weissbourd (20th century)

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