Random Permutation Statistics - Number of Permutations With A Cycle of Length Larger Than

Number of Permutations With A Cycle of Length Larger Than

Once more, start with the exponential generating function, this time of the class of permutations according to size where cycles of length more than are marked with the variable :

g(z, u) = \exp\left(u \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} + \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k} \right).

There can only be one cycle of length more than, hence the answer to the question is given by

n! g(z, u) = n! \exp\left(\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k}

or

n! \exp\left(\log \frac{1}{1-z} - \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k}

which is

n! \frac{1}{1-z} \exp\left( - \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} = n! \frac{1}{1-z} \sum_{m=0}^\infty \frac{(-1)^m}{m!} \left( \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right)^{m+1}

The exponent of in the term being raised to the power is larger than and hence no value for can possibly contribute to

It follows that the answer is

n! \frac{1}{1-z}\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k} = n! \sum_{k=\lfloor\frac{n}{2}\rfloor +1}^n \frac{1}{k}.

The sum has an alternate representation that one encounters e.g. in the OEIS (A024167).

\sum_{k=1}^n \frac{1}{k} - \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{k} = \sum_{k=1}^n \frac{1}{k} - 2\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{2k} = \sum_{k=1\atop k\; \text{even}}^n (1-2) \frac{1}{k} + \sum_{k=1\atop k \;\text{odd}}^n \frac{1}{k}

finally giving

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words larger than, number of, number, permutations, cycle, length and/or larger:

    “Reason is a faculty far larger than mere objective force. When either the political or the scientific discourse announces itself as the voice of reason, it is playing God, and should be spanked and stood in the corner.”
    —Ursula K. Le Guin (b. 1929)

    “I will not adopt that ungenerous and impolitic custom so common with novel writers, of degrading by their contemptuous censure the very performances, to the number of which they are themselves adding—joining with their greatest enemies in bestowing the harshest epithets on such works, and scarcely ever permitting them to be read by their own heroine, who, if she accidentally take up a novel, is sure to turn over its insipid leaves with disgust.”
    —Jane Austen (1775–1817)

    “That country is the richest which nourishes the greatest number of noble and happy human beings.”
    —John Ruskin (1819–1900)

    “The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
    —Jean Baudrillard (b. 1929)

    “Oh, life is a glorious cycle of song,
    A medley of extemporanea;
    And love is a thing that can never go wrong;
    And I am Marie of Roumania.”
    —Dorothy Parker (1893–1967)

    “When one man has reduced a fact of the imagination to be a fact to his understanding, I foresee that all men will at length establish their lives on that basis.”
    —Henry David Thoreau (1817–1862)

    “The passion of self-aggrandizement is persistent but plastic; it will never disappear from a vigorous mind, but may become morally higher by attaching itself to a larger conception of what constitutes the self.”
    —Charles Horton Cooley (1864–1929)