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 20 whose longest cycle is of length 11?

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

I take "permutations of length 20" to be a slightly nonstandard way to express "permutations of 20 elements".

If so, then 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 permutations that contain an 11-cycle. These all consist of (a) a cycle of length 11, (b) some permutation of the remaining 9 elements.

There are $\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 there are $9!$ ways the permutation can deal with the remaining 9 elements, so the total number of permutations that contain an 11-cycle is $$ \binom{20}{11} \cdot 10! \cdot 9! = \frac{20!}{11}$$

share|improve this answer
add comment

Clearly, $11 \neq 20$. Note also that $11 \nmid 20$. Denote the cycle of length $11$ by "a". So suppose such a permutation of length 20 consists of one or more additional cycles, $b, c, ...$, with the lengths of additional cycles $b, c...\leq 11$, and $\operatorname{lcm}(a, b, c, ...) = 20$. But since the longest cycle length in the permutation of length $11\;$, there is no permutation of length $20$ for which $\operatorname{lcm}(11, b, c, ...) = 20$, since $11 \nmid 20\;$ (i.e., $20$ is not a multiple of $11$).

Note: I'm using the fact that a permutation consisting of the product of disjoint cycles (every permutation can be written as the product of disjoint cycles) has length (order) equal to the least common multiple of the lengths of it cycles.

Hence, there are $\,0\,$ permutations of length $\,20\,$ whose longest cycle is of length $\,11$.

share|improve this answer
    
+1 nice amWhy. new day has come. –  B. S. Feb 4 '13 at 15:15
2  
That fact doesn't seem true to me. Take, for example (412)(53). This is a product of disjoint cycles of 5. The lcm of the of the lengths of the cycles is 6. –  tijme Feb 4 '13 at 15:19
    
It's order = length is 6, one cycle has length 2, the other length 3: the length of a permutation is not the "sum" of the lengths of its disjoint cycles. A cycle of length 11 looks like (1,2,3, 4, 5, 6, 7, 8, 9, 10, 11). –  amWhy Feb 4 '13 at 15:21
    
@amWhy A Google Scholar search for "permutations of length n" lends very little support for this antagonistic interpretation of "length" as "order", and overwhelming support for the one the OP clearly intended. –  Erick Wong Feb 4 '13 at 15:32
    
@amWhy Yes, you've "answered" it in the sense of formulating a new question which was never asked, then providing an incorrect answer to the invented question. Am I to assume there is an agenda here? –  Erick Wong Feb 4 '13 at 15:52
show 1 more comment

The combinatorial species $\mathcal{Q}$ that is being computed here has the specification $$ \mathcal{Q} = \mathfrak{P}(\mathfrak{C}_1(\mathcal{Z})+\cdots+\mathfrak{C}_{10}(\mathcal{Z})+\mathcal{U}\mathfrak{C}_{11}(\mathcal{Z})).$$

Solving this by exponential generating functions, the answer is $$ a_{20} = 20! [u z^{20}] \exp \left(\sum_{k=1}^{10} \frac{z^k}{k} + u \frac{z^{11}}{11}\right) = 20! [u z^{20}] \exp \left( \log \frac{1}{1-z} + u \frac{z^{11}}{11} - \sum_{k=11}^\infty \frac{z^k}{k} \right) = 20! [u z^{20}] \frac{1}{1-z} \exp \left(u \frac{z^{11}}{11} - \sum_{k=11}^\infty \frac{z^k}{k} \right) = 20! [z^{20}] \frac{1}{1-z} \frac{z^{11}}{11} \exp \left(- \sum_{k=11}^\infty \frac{z^k}{k} \right) .$$ Here we have made use of the fact that if there is a cycle of length $11$ in a permutation of size $20$, then there is exactly one such cycle. Simplifying, we find $$ a_{20} = \frac{20!}{11} [z^9] \frac{1}{1-z} \exp \left(- \sum_{k=11}^\infty \frac{z^k}{k} \right) = \frac{20!}{11} \sum_{q=0}^9 [z^q] \exp \left(- \sum_{k=11}^\infty \frac{z^k}{k} \right) = \frac{20!}{11},$$ confirming the result from above.

share|improve this answer
add comment

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.