# Number of Permutations of a Cycle with no cycle greater than 11.

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.

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

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.

-

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.

-
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