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:

“Accidents will occur in the best regulated families; and in families not regulated by that pervading influence which sanctifies while it enhances the—a—I would say, in short, by the influence of Woman, in the lofty character of Wife, they may be expected with confidence, and must be borne with philosophy.”
—Charles Dickens (1812–1870)

“This nightmare occupied some ten pages of manuscript and wound off with a sermon so destructive of all hope to non-Presbyterians that it took the first prize. This composition was considered to be the very finest effort of the evening.... It may be remarked, in passing, that the number of compositions in which the word “beauteous” was over-fondled, and human experience referred to as “life’s page,” was up to the usual average.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)

“There is a potential 4-6 percentage point net gain for the President [George Bush] by replacing Dan Quayle on the ticket with someone of neutral stature.”
—Mary Matalin, U.S. Republican political advisor, author, and James Carville b. 1946, U.S. Democratic political advisor, author. All’s Fair: Love, War, and Running for President, p. 205, Random House (1994)