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:

    “A considerable percentage of the people we meet on the street are people who are empty inside, that is, they are actually already dead. It is fortunate for us that we do not see and do not know it. If we knew what a number of people are actually dead and what a number of these dead people govern our lives, we should go mad with horror.”
    —George Gurdjieff (c. 1877–1949)

    “Today, almost forty years later, I grow dizzy when I recall that the number of manufactured tanks seems to have been more important to me than the vanished victims of racism.”
    —Albert Speer (1905–1981)

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