Random Permutation Statistics - Expected Number of Transpositions of A Random Permutation

Expected Number of Transpositions of A Random Permutation

We can use the disjoint cycle decomposition of a permutation to factorize it as a product of transpositions by replacing a cycle of length k by transpositions. E.g. the cycle factors as . The function for cycles is equal to and we obtain

g(z, u) = \left( \frac{1}{1-uz} \right)^{1/u}

and

\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge 1} (k-1) \frac{z^k}{k} = \frac{z}{(1-z)^2} - \frac{1}{1-z} \log \frac{1}{1-z}.

Hence the expected number of transpositions is

We could also have obtained this formula by noting that the number of transpositions is obtained by adding the lengths of all cycles (which gives n) and subtracting one for every cycle (which gives by the previous section).

Note that again generates the unsigned Stirling numbers of the first kind, but in reverse order. More precisely, we have

(-1)^m n! \; g(z, u) = \left

To see this, note that the above is equivalent to

(-1)^{n+m} n! \; g(z, u)|_{u=1/u} |_{z=uz} = \left

and that

g(z, u)|_{u=1/u} |_{z=uz} = \left( \frac{1}{1-z} \right)^u = \frac{1}{m!} \left( \log \frac{1}{1-z} \right)^m,

which we saw to be the EGF of the unsigned Stirling numbers of the first kind in the section on permutations consisting of precisely m cycles.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words expected, number and/or random:

    “I was not at all worried about finding my doctor boring; I expected from him, thanks to an art of which the laws escaped me, that he pronounce concerning my health an indisputable oracle by consulting my entrails.”
    —Marcel Proust (1871–1922)

    “It is always possible to bind together a considerable number of people in love, so long as there are other people left over to receive the manifestations of their aggression.”
    —Sigmund Freud (1856–1939)

    “We should stop looking to law to provide the final answer.... Law cannot save us from ourselves.... We have to go out and try to accomplish our goals and resolve disagreements by doing what we think is right. That energy and resourcefulness, not millions of legal cubicles, is what was great about America. Let judgment and personal conviction be important again.”
    —Philip K. Howard, U.S. lawyer. The Death of Common Sense: How Law Is Suffocating America, pp. 186-87, Random House (1994)