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:

    “I have known a number of Don Juans who were good studs and who cavorted between the sheets without a psychiatrist to guide them. But most of the busy love-makers I knew were looking for masculinity rather than practicing it. They were fellows of dubious lust.”
    —Ben Hecht (1893–1964)

    “In the U.S. for instance, the value of a homemaker’s productive work has been imputed mostly when she was maimed or killed and insurance companies and/or the courts had to calculate the amount to pay her family in damages. Even at that, the rates were mostly pink collar and the big number was attributed to the husband’s pain and suffering.”
    —Gloria Steinem (20th century)

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