Random Permutation Statistics - Expected Number of Fixed Points in Random Permutation Raised To Some Power | Expected Number Fixed Points Random Permutation Raised Power

Expected Number of Fixed Points in Random Permutation Raised To Some Power

Suppose you pick a random permutation and raise it to some power, with a positive integer and ask about the expected number of fixed points in the result. Denote this value by .

For every divisor of a cycle of length splits into fixed points when raised to the power Hence we need to mark these cycles with To illustrate this consider

We get

$g(z, u) = \exp\left(uz - z + u^2 \frac{z^2}{2} - \frac{z^2}{2} + u^3 \frac{z^3}{3} - \frac{z^3}{3} + u^6 \frac{z^6}{6} - \frac{z^6}{6} + \log \frac{1}{1-z}\right)$

which is

$\frac{1}{1-z} \exp\left(uz - z + u^2 \frac{z^2}{2} - \frac{z^2}{2} + u^3 \frac{z^3}{3} - \frac{z^3}{3} + u^6 \frac{z^6}{6} - \frac{z^6}{6}\right).$

Once more continuing as described in the introduction, we find

$\left.\frac{\partial}{\partial u} g(z, u)\right|_{u=1} = \left. \frac{z+z^2+z^3+z^6}{1-z} \exp\left(uz - z + u^2 \frac{z^2}{2} - \frac{z^2}{2} + u^3 \frac{z^3}{3} - \frac{z^3}{3} + u^6 \frac{z^6}{6} - \frac{z^6}{6}\right) \right|_{u=1}$

which is

The conclusion is that for and there are four fixed points on average.

The general procedure is

$g(z, u) = \exp\left(\sum_{d\mid k} \left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right) + \log \frac{1}{1-z} \right)= \frac{1}{1-z} \exp\left(\sum_{d\mid k} \left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right)\right).$

Once more continuing as before, we find

$\left.\frac{\partial}{\partial u} g(z, u)\right|_{u=1} = \left. \frac{\sum_{d\mid k} z^d}{1-z} \exp\left(\sum_{d\mid k} \left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right)\right) \right|_{u=1} = \frac{\sum_{d\mid k} z^d}{1-z}.$

We have shown that the value of is equal to (the number of divisors of ) as soon as It starts out at for and increases by one every time hits a divisor of up to and including itself.

Read more about this topic: Random Permutation Statistics

Famous quotes containing the words expected, number, fixed, points, random, raised and/or power:

“For I had expected always
Some brightness to hold in trust,
Some final innocence
To save from dust;”
—Stephen Spender (1909–1995)

“The said truth is that it is the greatest happiness of the greatest number that is the measure of right and wrong.”
—Jeremy Bentham (1748–1832)

“The permanence of all books is fixed by no effort friendly or hostile, but by their own specific gravity, or the intrinsic importance of their contents to the constant mind of man.”
—Ralph Waldo Emerson (1803–1882)

“Type of the wise, who soar, but never roam—
True to the kindred points of Heaven and Home!”
—William Wordsworth (1770–1850)

“Man always made, and still makes, grotesque blunders in selecting and measuring forces, taken at random from the heap, but he never made a mistake in the value he set on the whole, which he symbolized as unity and worshipped as God. To this day, his attitude towards it has never changed, though science can no longer give to force a name.”
—Henry Brooks Adams (1838–1918)

“This is the Scroll of Thoth. Herein are set down the magic words by which Isis raised Osiris from the dead. Oh! Amon-Ra—Oh! God of Gods—Death is but the doorway to new life—We live today-we shall live again—In many forms shall we return-Oh, mighty one.”
—John L. Balderston (1899–1954)

“Success four flights Thursday morning all against twenty one mile wind started from Level with engine power alone speed through air thirty one miles longest 57 second inform Press home Christmas.”
—Orville Wright (1871–1948)