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 tendency to nervousness in my younger days, in view of the fact of a number of near relatives on both my father’s and mother’s side of the house having become insane, gave some serious uneasiness. I made up my mind to overcome it.... In the cross-examination of witnesses before a crowded court-house ... I soon found I could control myself even in the worst of testing cases. Finally, in battle.”
    —Rutherford Birchard Hayes (1822–1893)

    “I believe if we introduced the Lord’s Prayer here, senators would propose a large number of amendments to it.”
    —Henry Wilson (1812–1875)

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