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.

I'm looking for the number of permutations of a $20$ element set, with no cycle greater than length $11$. All of the attempts that I have tried are not working out. I'm not sure how to get started on this question. Any hints?

Also, I saw a similar question to this using generating functions. But I'm doing it without, if possible.

share|improve this question
2  
Cycles cannot be compared to numbers. When you write, "no cycle greater that [sic] $11$," do you mean, "no cycle of length greater than $11$"? –  Gerry Myerson Feb 5 '13 at 2:52
    
You need the number of partitions of 20 with no summand bigger than 11. There are 627 of the former so unless there is some slick trick this looks like a nasty exercise to find the number of the later... –  DonAntonio Feb 5 '13 at 2:53
1  
One can always solve this kind of problem by brute force. We count the complement, the permutations that have a cycle of length $k$, where $k=12, 13, \dots,20$ and add up. For each of these $k$, it is easy to write down the number of permutations with a $k$-cycle, since there cannot be more than one. –  André Nicolas Feb 5 '13 at 2:57

2 Answers 2

up vote 3 down vote accepted

We count the complement, the permutations that have a cycle of length $k$, where $k$ ranges from $12$ to $20$. Then we add up. For smallish $k$, like $5$, this could be unpleasant, since one can have several $5$-cycles. But for the $k$ in our range, a permutation has at most one $k$-cycle.

Let's do the calculation. The idea has already been covered by amWhy, so we do it quickly.

The $k$ objects in the $k$-cycle can be chosen in $\binom{20}{k}$ ways. There are $(k-1)!$ circular permutations of $k$ objects. And there are $(20-k)!$ ways to permute the rest, for a total of $$\binom{20}{k}(k-1)!(20-k)!.$$

This simplifies nicely to $\dfrac{20!}{k}$. So the complement of our set has size $$20!\left(\frac{1}{12}+\frac{1}{13}+\cdots+\frac{1}{20}\right).$$

Remark: The result may be numerically surprising. The probability that a permutation has a large cycle is quite big.

share|improve this answer

Whenever a permutation contains any cycle of length 11, that one has to be the longest cycle in the permutation, because there are not enough elements left over to form a longer one. So what we're looking for is simply all permutations containing an 11-cycle. These all consist of

  • a cycle of length 11,
  • some permutation of the remaining 9 elements.

There are $\,\displaystyle \binom{20}{11}\cdot 10!\,$ different $11$-cycles, because we can first choose which $11$ elements the cycle includes. For each such choice there are $11!$ different cycle notations, but every cycle is counted 11 times (with each of the 11 elements notated first), so there are actually $10!$ different cyclic permutations of 11 elements.

Once an $11$-cycle has been chosen, then there are $9!$ ways to permute the remaining $9$ elements, so the total number of permutations that contain an $11$-cycle is given by: $$ \binom{20}{11} \cdot 10! \cdot 9! = \frac{20!}{11}$$

If you also need to count permutations whose longest cycle is LESS THAN 11, then there is much more work involved, and indeed, I believe @André Nicolas's answer involves the least amount of work.

share|improve this answer
1  
I don't read the problem as asking for permutations with a cycle of length $11$, just no cycle of length greater than $11$. Perhaps OP will clarify. –  Gerry Myerson Feb 5 '13 at 2:54
    
you're right, @Gerry...this would be only one step in a very long series of computations...! –  amWhy Feb 5 '13 at 2:59

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.