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:

    “We have ... dreamed so much and observed so little, that our imaginations have grown larger than the world we live in, and our judgments have dwindled down to a point.”
    —Frances Wright (1795–1852)

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

    “Civilization is maintained by a very few people in a small number of places and we need only some bombs and a few prisons to blot it out altogether.”
    —Cyril Connolly (1903–1974)

    “Motherhood in all its guises and permutations is more art than science.”
    —Melinda M. Marshall (20th century)

    “Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
    —Oscar Wilde (1854–1900)

    “With the ancient is wisdom; and in length of days understanding.”
    —Bible: Hebrew Job, 12:12.

    “We have ... dreamed so much and observed so little, that our imaginations have grown larger than the world we live in, and our judgments have dwindled down to a point.”
    —Frances Wright (1795–1852)