Permutations with a cycle $>\frac{n}{2}$

I'm interested in the following question:

Let $S_n$ be the set of all permutations over $\{1,...,n\}$. We know that $|S_n|=n!$.

How many permutations of this set has a cycle larger than $\frac{n}{2}$?

Thanks

PS - not hw.

• What does it mean for a permutation to have a cycle of some length? You mean a cycle in its disjoint cycles decomposition? – Andrea Mori Dec 15 '12 at 16:36

All permutations can be written as a product of disjoint cycles. Let $\sigma$ be a permutation that has a cycle of length greater than $n/2$. Clearly, $\sigma$ has exactly one such cycle. Let the longest in cycle $\sigma$ be $(a_1,a_2,...,a_k$). Now think of $\sigma$ restricted to $\{1,2,...,n\}-\{a_1,a_2,...,a_k\}$. Restricting $\sigma$ to this set yields a permutation of the set $\{1,2,...,n\}-\{a_1,a_2,...,a_k\}$.

The number of ways to select the subset $\{a_1,a_2,...,a_k\}$ is: $$\binom{n}{k}$$

The number of ways to select distinct cycles $(a_1,a_2,...,a_k)$ is:$$(k-1)!$$ The number of ways to choose the restricted $\sigma$ is : $$(n-k)!$$ Thus the total number of ways is: $$\sum_{k>\frac{n}{2}}\binom{n}{k}(k-1)!(n-k)!$$ $$n!\sum_{k>\frac{n}{2}}\frac{1}{k}$$

• I don't understand. I'm looking at 1,...,4. I see 14 permutations with a cycle of length 3 or 4: – Amihai Zivan Dec 15 '12 at 17:21
• What are they ? – Amr Dec 15 '12 at 17:25
• Wait I made a mistake while counting – Amr Dec 15 '12 at 17:27
• I edited it now – Amr Dec 15 '12 at 18:05
• I guess yes. But I am a bit busy now. You can post this as another question (and maybe refer to this question) – Amr Dec 15 '12 at 19:59

This answer is to provide additional insight through the use of generating function techniques. As we shall see the result may be derived using some classic algebraic manipulations that are familiar to anyone working with permutations.

First, start with the exponential generating function $G(z, u)$ of the class $\mathcal{P}$ of permutations according to size where cycles of length more than $n/2$ are marked with the variable $u$: $$G(z, u) = \exp\left(u \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} + \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k} \right).$$ There can only be one cycle of length more than $\frac{n}{2}$, hence the answer to the question is given by $$n! [u z^n] G(z, u) = n! [z^n] \exp\left(\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k}$$ or $$n! [z^n] \exp\left(\log \frac{1}{1-z} - \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k}$$ which is $$n! [z^n] \frac{1}{1-z} \exp\left( - \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right) \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} = n! [z^n] \frac{1}{1-z} \sum_{m=0}^\infty \frac{(-1)^m}{m!} \left( \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right)^{m+1}$$ The exponent of $z$ in the term being raised to the power $m+1$ is larger than $\lfloor\frac{n}{2} \rfloor$ and hence no value for $m>0$ can possibly contribute to $[z^n].$ It follows that the answer is $$n![z^n] \frac{1}{1-z}\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k} = n! \sum_{k=\lfloor\frac{n}{2}\rfloor +1}^n \frac{1}{k}.$$ The sum has an alternate representation that one encounters e.g. in the OEIS. $$\sum_{k=1}^n \frac{1}{k} - \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{k} = \sum_{k=1}^n \frac{1}{k} - 2\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{2k} = \sum_{k=1\atop k\; \text{even}}^n (1-2) \frac{1}{k} + \sum_{k=1\atop k \;\text{odd}}^n \frac{1}{k}$$ finally giving $$n!\sum_{k=1}^n \frac{(-1)^{k+1}}{k} \sim n! \log 2.$$ While these ideas have been around for some time, the formalism used is essentially due to P. Flajolet. There is more at INRIA.

• Thanks - I'll need time to digest it, but the identity $$n!\sum_{k=1}^n \frac{(-1)^{k+1}}{k}=n!\sum_{k>n/2}^n \frac{1}{k}$$ is beautiful! – Amihai Zivan Dec 17 '12 at 6:24
• It looks fishy... – vonbrand Jan 23 '13 at 3:24
• Is this true? I know that the limits of both sides are equal but I am quite wondering if the finite sums are equal. – user42761 Mar 7 '13 at 0:02
• @ Marko: Is there some resource which explains things you do there ? I am quite interested in solving this by generating functions but can't understand your proof. – user42761 Mar 7 '13 at 11:57
• @Andre There is quite a lot of material at Wikipedia. Get started here. – Marko Riedel Mar 7 '13 at 19:28

Take all the $n!$ permutations of $n$ elements. If we take a cycle of length $r > \frac{n}{2}$, there are $\binom{n}{r}$ ways of selecting the elements of the cycle, and they can be arranged in $(r - 1)!$ different cycles (pick any element as first, the others get $(r - 1)!$ orders; now glue the first to the last for a cycle). The other $n - r$ elements can be arranged in $(n - r)!$ ways. Pulling everything together: $$\binom{n}{r} \cdot (r - 1)! \cdot (n - r)! = \frac{n!}{r}$$ Now we need to add over $r > \frac{n}{2}$: $$\sum_{\frac{n}{2} < r \le n} \frac{n!}{r} = n! \left( H_n - H_{\frac{n}{2}} \right)$$ (the $H_k$ are harmonic numbers, it is known that $H_k = \ln k + \gamma + O(1/n)$, so this turns out approximately $n! \ln 2$).