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:

    “Don’t be so ready to defy everybody. Act as if you expected to have your own way, not as if you expected to be ordered about. The way to get on as a lady is the same as the way to get on as a servant: you’ve got to know your place.”
    —George Bernard Shaw (1856–1950)

    “In the multitude of middle-aged men who go about their vocations in a daily course determined for them much in the same way as the tie of their cravats, there is always a good number who once meant to shape their own deeds and alter the world a little.”
    —George Eliot [Mary Ann (or Marian)

    “poor Felix Randal;
    How far from then forethought of, all thy more boisterous years,
    When thou at the random grim forge, powerful amidst peers,
    Didst fettle for the great gray drayhorse his bright and battering
    sandal!”
    —Gerard Manley Hopkins (1844–1889)