Tell me more ×
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.
up vote 3 down vote favorite
1

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 at 21:01
3  
Here are some relevant sequences from the OEIS: m=2, m=3 and m=4. – Marko Riedel Feb 3 at 21:14

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.