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:

    “He is the greatest artist who has embodied, in the sum of his works, the greatest number of the greatest ideas.”
    —John Ruskin (1819–1900)

    “This nightmare occupied some ten pages of manuscript and wound off with a sermon so destructive of all hope to non-Presbyterians that it took the first prize. This composition was considered to be the very finest effort of the evening.... It may be remarked, in passing, that the number of compositions in which the word “beauteous” was over-fondled, and human experience referred to as “life’s page,” was up to the usual average.”
    —Mark Twain [Samuel Langhorne Clemens] (1835–1910)

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