Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the number of permutations of length n if no cycle can exceed a maximum length $m$, where $m \lt n$?

share|cite|improve this question
Using exponential generating functions we have that the generating function of these permutations is given by $$ G(z) = \exp\left( \sum_{k=1}^m \frac{z^k}{k} \right) = \exp\left( \log \frac{1}{1-z} -\sum_{k=m+1}^\infty \frac{z^k}{k} \right) = \frac{1}{1-z} \exp\left(-\sum_{k=m+1}^\infty \frac{z^k}{k} \right).$$ It follows that the value we are looking for is given by $$ n! [z^n] G(z) = n! \sum_{q=0}^n [z^q] \exp\left(-\sum_{k=m+1}^\infty \frac{z^k}{k} \right).$$ This expression can be simplified for $m$ fixed. – Marko Riedel Feb 3 '13 at 21:01
Here are some relevant sequences from the OEIS: m=2, m=3 and m=4. – Marko Riedel Feb 3 '13 at 21:14
@MarkoRiedel, please make this comment(s) into an answer. – vonbrand Feb 6 '14 at 15:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.