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:

    “There were ghosts that returned to earth to hear his phrases,
    As he sat there reading, aloud, the great blue tabulae.
    They were those from the wilderness of stars that had expected more.
    There were those that returned to hear him read from the poem of life,
    Of the pans above the stove, the pots on the table, the tulips among them.
    They were those that would have wept to step barefoot into reality....”
    —Wallace Stevens (1879–1955)

    “... in every State there are more women who can read and write than the whole number of illiterate male voters; more white women who can read and write than all Negro voters; more American women who can read and write than all foreign voters.”
    —National Woman Suffrage Association. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)

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

    “The three main medieval points of view regarding universals are designated by historians as realism, conceptualism, and nominalism. Essentially these same three doctrines reappear in twentieth-century surveys of the philosophy of mathematics under the new names logicism, intuitionism, and formalism.”
    —Willard Van Orman Quine (b. 1908)

    “We should stop looking to law to provide the final answer.... Law cannot save us from ourselves.... We have to go out and try to accomplish our goals and resolve disagreements by doing what we think is right. That energy and resourcefulness, not millions of legal cubicles, is what was great about America. Let judgment and personal conviction be important again.”
    —Philip K. Howard, U.S. lawyer. The Death of Common Sense: How Law Is Suffocating America, pp. 186-87, Random House (1994)

    “He raised a sigh so piteous and profound
    That it did seem to shatter all his bulk
    And end his being.”
    —William Shakespeare (1564–1616)

    “‘Tis not such lines as almost crack the stage
    When Bajazet begins to rage;
    Nor a tall met’phor in the bombast way,
    Nor the dry chips of short-lunged Seneca.
    Nor upon all things to obtrude
    And force some odd similitude.
    What is it then, which like the power divine
    We only can by negatives define?”
    —Abraham Cowley (1618–1667)