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 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)

“I think, for the rest of my life, I shall refrain from looking up things. It is the most ravenous time-snatcher I know. You pull one book from the shelf, which carries a hint or a reference that sends you posthaste to another book, and that to successive others. It is incredible, the number of books you hopefully open and disappointedly close, only to take down another with the same result.”
—Carolyn Wells (1862–1942)

“The foot of the heavenly ladder, which we have got to mount in order to reach the higher regions, has to be fixed firmly in every-day life, so that everybody may be able to climb up it along with us. When people then find that they have got climbed up higher and higher into a marvelous, magical world, they will feel that that realm, too, belongs to their ordinary, every-day life, and is, merely, the wonderful and most glorious part thereof.”
—E.T.A.W. (Ernst Theodor Amadeus Wilhelm)

“the
Decapitated exclamation points in that Other Woman’s eyes.”
—Gwendolyn Brooks (b. 1917)

“It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
—Hannah Arendt (1906–1975)

“Conditional love is love that is turned off and on....Some parents only show their love after a child has done something that pleases them. “I love you, honey, for cleaning your room!” Children who think they need to earn love become people pleasers, or perfectionists. Those who are raised on conditional love never really feel loved.”
—Louise Hart (20th century)

“To be inspired is to be moved in an extraordinary manner by the power or Spirit of God to act, speak, or think what is holy, just and true; [Enthusiasm is] A Full, but false persuasion in a man that he is inspired.”
—Henry More (1614–1687)