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 σ ∈ S_n:

$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 and/or permutations:

“How often should a woman be pregnant? Continually, or hardly ever? Or must there be a certain number of pregnancy anniversaries established by fashion? What do you, at the age of forty-three, have to say on the subject? Is it a fact that the laws of nature, or of the country, or of propriety, have ordained this time of life for sterility?”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

“The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
—Jean Baudrillard (b. 1929)