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:

    “... [woman suffrage] has made little difference beyond doubling the number of voters. There is no woman’s vote as such. They divide up just about as men do.”
    —Alice Roosevelt Longworth (1884–1980)

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