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.
Best Answer
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.