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:

    “Between us two it’s not a star at all.
    It’s a new patented electric light,
    Put up on trial by that Jerseyite
    So much is being now expected of....”
    —Robert Frost (1874–1963)

    “There is not to be found, in all history, any miracle attested by a sufficient number of men, of such unquestioned good sense, education, and learning, as to secure us against all delusion in themselves ... beyond all suspicion of any design to deceive others ... and at the same time attesting facts, performed in such a public manner, and in so celebrated a part of the world, as to render the detection unavoidable.”
    —David Hume (1711–1776)

    “And catch the gleaming of a random light,
    That tells me that the ship I seek is passing, passing.”
    —Paul Laurence Dunbar (1872–1906)