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 number of, number, permutations, cycle, length and/or larger:

    “Love has its name borrowed by a great number of dealings and affairs that are attributed to it—in which it has no greater part than the Doge in what is done at Venice.”
    —François, Duc De La Rochefoucauld (1613–1680)

    “There is something tragic about the enormous number of young men there are in England at the present moment who start life with perfect profiles, and end by adopting some useful profession.”
    —Oscar Wilde (1854–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)

    “Men sometimes speak as if the study of the classics would at length make way for more modern and practical studies; but the adventurous student will always study classics, in whatever language they may be written and however ancient they may be. For what are the classics but the noblest recorded thoughts of man?... We might as well omit to study Nature because she is old.”
    —Henry David Thoreau (1817–1862)

    “What is art,
    But life upon the larger scale, the higher,
    When, graduating up in a spiral line
    Of still expanding and ascending gyres,
    It pushes toward the intense significance
    Of all things, hungry for the Infinite?
    Art’s life,—and where we live, we suffer and toil.”
    —Elizabeth Barrett Browning (1806–1861)