Random Permutation Statistics - Expected Number of Fixed Points in Random Permutation Raised To Some 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:

    “She has been man’s slave. He has been educated at her expense. If he bought the ice cream, she was expected to pay for all his luxuries in reduced wages. She has done the drudgery and borne the insults of those who wronged her, assuming to be her protector.”
    —Caroline Nichols Churchill (1833–?)

    “There are crimes which become innocent and even glorious through their splendor, number and excess.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “Marriage is the clue to human life, but there is no marriage apart from the wheeling sun and the nodding earth, from the straying of the planets and the magnificence of the fixed stars.”
    —D.H. (David Herbert)

    “Wonderful “Force of Public Opinion!” We must act and walk in all points as it prescribes; follow the traffic it bids us, realise the sum of money, the degree of “influence” it expects of us, or we shall be lightly esteemed; certain mouthfuls of articulate wind will be blown at us, and this what mortal courage can front?”
    —Thomas Carlyle (1795–1881)

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

    “We raised a simple prayer
    Before we left the spot,
    That in the general mowing
    That place might be forgot;
    Or if not all so favored,
    Obtain such grace of hours
    That none should mow the grass there
    While so confused with flowers.”
    —Robert Frost (1874–1963)

    “What is important, then, is not that the critic should possess a correct abstract definition of beauty for the intellect, but a certain kind of temperament, the power of being deeply moved by the presence of beautiful objects.”
    —Walter Pater (1839–1894)