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:

    “In a number of other cultures, fathers are not relegated to babysitter status, nor is their ability to be primary nurturers so readily dismissed.... We have evidence that in our own society men can rear and nurture their children competently and that men’s methods, although different from those of women, are imaginative and constructive.”
    —Kyle D. Pruett (20th century)

    “Black lady,
    what will I do
    without your two flowers?
    I have inhabited you, number by number.
    I have pushed you in and out like a needle.”
    —Anne Sexton (1928–1974)

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