Random Permutation Statistics - Expected Number of Transpositions of A Random Permutation | Expected Number Transpositions 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:

“For me chemistry represented an indefinite cloud of future potentialities which enveloped my life to come in black volutes torn by fiery flashes, like those which had hidden Mount Sinai. Like Moses, from that cloud I expected my law, the principle of order in me, around me, and in the world.... I would watch the buds swell in spring, the mica glint in the granite, my own hands, and I would say to myself: “I will understand this, too, I will understand everything.””
—Primo Levi (1919–1987)

“The Oregon [matter] and the annexation of Texas are now all- important to the security and future peace and prosperity of our union, and I hope there are a sufficient number of pure American democrats to carry into effect the annexation of Texas and [extension of] our laws over Oregon. No temporizing policy or all is lost.”
—Andrew Jackson (1767–1845)

“Novels as dull as dishwater, with the grease of random sentiments floating on top.”
—Italo Calvino (1923–1985)