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:

    “Love has its name borrowed by a great number of dealings and affairs that are attributed to it—in which it has no greater part than the Doge in what is done at Venice.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “Envy has blackened every page of his history.... The future, in its justice, will number him among those men whom passions and an excess of activity have condemned to unhappiness, through the gift of genius.”
    —Eugène Delacroix (1798–1863)

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