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 happen to feel that the degree of a person’s intelligence is directly reflected by the number of conflicting attitudes she can bring to bear on the same topic.”
    —Lisa Alther (b. 1944)

    “The serial number of a human specimen is the face, that accidental and unrepeatable combination of features. It reflects neither character nor soul, nor what we call the self. The face is only the serial number of a specimen.”
    —Milan Kundera (b. 1929)

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