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:

    “Can a woman become a genius of the first class? Nobody can know unless women in general shall have equal opportunity with men in education, in vocational choice, and in social welcome of their best intellectual work for a number of generations.”
    —Anna Garlin Spencer (1851–1931)

    “Envy has blackened every page of his history.... The future, in its justice, will number him among those men whom passions and an excess of activity have condemned to unhappiness, through the gift of genius.”
    —Eugène Delacroix (1798–1863)

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

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

    “At length to hospital
    This man was limited,
    Where screens leant on the wall
    And idle headphones hung.
    Since he would soon be dead
    They let his wife come along
    And pour out tea, each day.”
    —Philip Larkin (1922–1986)

    “A child is not a salmon mousse. A child is a temporarily disabled and stunted version of a larger person, whom you will someday know. Your job is to help them overcome the disabilities associated with their size and inexperience so that they get on with being that larger person.”
    —Barbara Ehrenreich (b. 1941)