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:

    “He is the richest man who knows how to draw a benefit from the labors of the greatest number of men, of men in distant countries, and in past times.”
    —Ralph Waldo Emerson (1803–1882)

    “Even in ordinary speech we call a person unreasonable whose outlook is narrow, who is conscious of one thing only at a time, and who is consequently the prey of his own caprice, whilst we describe a person as reasonable whose outlook is comprehensive, who is capable of looking at more than one side of a question and of grasping a number of details as parts of a whole.”
    —G. Dawes Hicks (1862–1941)

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

    “The lifelong process of caregiving, is the ultimate link between caregivers of all ages. You and I are not just in a phase we will outgrow. This is life—birth, death, and everything in between.... The care continuum is the cycle of life turning full circle in each of our lives. And what we learn when we spoon-feed our babies will echo in our ears as we feed our parents. The point is not to be done. The point is to be ready to do again.”
    —Paula C. Lowe (20th century)

    “At length I heard a ragged noise and mirth
    Of thieves and murderers: there I him espied
    Who straight, Your suit is granted,said, and died.”
    —George Herbert (1593–1633)

    “The obese is ... in a total delirium. For he is not only large, of a size opposed to normal morphology: he is larger than large. He no longer makes sense in some distinctive opposition, but in his excess, his redundancy.”
    —Jean Baudrillard (b. 1929)