Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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
3  
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 at 15:34

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.