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.

Let $\sigma\in S_n$ be given. Let us write $\sigma$ in its disjoint cycle decomposition. Define by $w(\sigma)$ the number of cycles (for instance if we have the permutation $1\mapsto 2, 2\mapsto 4, 3\mapsto 3, 4\mapsto 1, 5\mapsto 5$ we write it as $(124)(3)(5)$ so $w(\sigma)=3$).

I was asked to find $$A_n=\sum_{\sigma\in S_n}w(\sigma)$$I found the recursive formula $$A_n=n!+(n-1)!\left[\frac{A_{n-1}}{(n-1)!}+\frac{A_{n-2}}{(n-2)!}+\ldots+\frac{A_{1}}{1!}\right]$$

I was trying to tinker around with it to see if I could get a formula that does not rely on recursion, but failed at it. Any help or hint that would lead me towards making my solution for $A_n$ "better".

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

Let $b_n=\dfrac{A_n}{n!}$; then your recurrence can be rewritten

$$b_n=1+\frac1n\sum_{k=1}^{n-1}b_k\;,\tag{1}$$

with $b_1=1$. Calculate a few values:

$$\begin{align*} &b_1=1\\ &b_2=1+\frac12\cdot1=\frac32\\ &b_3=1+\frac13\left(1+\frac32\right)=\frac{11}6\\ &b_4=1+\frac14\left(1+\frac32+\frac{11}6\right)=\frac{25}{12} \end{align*}$$

I recognize those as the first four harmonic numbers: $$b_n=H_n=\sum_{k=1}^n\frac1k\;.$$

And sure enough, the harmonic numbers do satisfy $(1)$:

$$\begin{align*} 1+\frac1n\sum_{k=1}^{n-1}H_k&=1+\frac1n\sum_{k=1}^{n-1}\sum_{i=1}^k\frac1i\\ &=1+\frac1n\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}\frac1i\\ &=1+\frac1n\sum_{i=1}^{n-1}\frac{n-i}i\\ &=1+\frac1n\sum_{i=1}^{n-1}\left(\frac{n}i-1\right)\\ &=1+\sum_{i=1}^{n-1}\frac1i-\frac{n-1}n\\ &=1+H_{n-1}-1+\frac1n\\ &=H_n\;. \end{align*}$$

Thus, $A_n=n!H_n$.

Added: Here’s another approach to the problem. It’s not too hard to prove that the number of $\pi\in S_n$ with $k$ cycles is $\left[n\atop k\right]$, a Stirling number of the first kind. These have the generating function $$\sum_{k\ge 0}\left[n\atop k\right]x^k=x^{\overline{n}}=x(x+1)(x+2)\dots(x+n-1)\;.$$ Differentiating yields

$$\begin{align*} \sum_{k\ge 1}k\left[n\atop k\right]x^{k-1}&=\frac{d}{dx}\Big(x(x+1)(x+2)\dots(x+n-1)\Big)\\ &=\sum_{k=0}^{n-1}\frac{\prod_{i=0}^{n-1}(x+i)}{x+k}\;, \end{align*}$$

and evaluating at $x=1$ yields $$\sum_{k\ge 1}k\left[n\atop k\right]=\sum_{k=0}^{n-1}\frac{n!}{k+1}=n!H_n\;.$$

share|improve this answer
    
So $A_n$ is asymptotic to $n!\log n$. –  Gerry Myerson Oct 6 '12 at 5:48
    
@Gerry: Yep. $A_n=n!\ln n+O(n!)$, or, better, $n!\ln n+\gamma n!+O((n-1)!)$. –  Brian M. Scott Oct 6 '12 at 6:16
    
Thanks!${}{}{}{}$ –  Daniel Montealegre Oct 6 '12 at 19:08
    
@Daniel: My pleasure. –  Brian M. Scott Oct 6 '12 at 19:09
add comment

You can get an easier recurrence by considering the last element $n$ in the permutation.

Either $n$ occurs in a cycle of length at least $2$, or it forms a "cycle" on its own. In the former case taking it out of its cycle leaves a permutation of $n-1$ with the same number of cycles, and given a permutation of $n-1$ we can insert $n$ in $n-1$ places into an existing cycle, for a total contribution of $(n-1)A_{n-1}$ to $A_n$. In the latter case removing $n$ just leaves a permutation of $n-1$, which here arises in only one way; however the number of cycles is one more for the permutation of $n$ than it was for the permutation of $n-1$, so in all this contributes $A_{n-1}+(n-1)!$ to $A_n$ (the second term is for the extra cycle in $(n-1)!$ permutations). Since we have now accounted for every contribution once, we get $$ A_n=(n-1)A_{n-1}+A_{n-1}+(n-1)! = nA_{n-1} + (n-1)! $$ One can simplify this by dividing by $n!$, giving $$ \frac{A_n}{n!}= \frac{A_{n-1}}{(n-1)!} + \frac1n, $$ which together with $A_0=0$ obviously gives $\frac{A_n}{n!}=\sum_{i=1}^n\frac1i=H_n$ and $A_n=n!H_n$.

share|improve this answer
    
Very good answer too, but I cannot accept both. I got my recursion by adding the cases $n$ is in a $1$ cycle, in a $2$ cycle,..., in an $n$ cycle, but your solution is neater. –  Daniel Montealegre Oct 6 '12 at 19:17
add comment

This question is best addressed using the symbolic method.

Permutations are sets of cycles, having combinatorial class specification $\mathfrak P(\mathfrak C(\mathfrak Z))$. Hence the corresponding exponential generating function (EGF) is $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ where $$ \log \frac{1}{1-z} $$ is the EGF of labelled cycles. (These two are easily verified as there are $n!$ permutations and $n!/n$ cycles.)

If we want to count the number of cycles we need to mark each cycle with a new variable, $u$, which gives the mixed generating function $$G(z, u) = \exp \left( u \log \frac{1}{1-z} \right).$$

Now a term $u^k z^n / n!$ in $G(z, u)$ represents a permutation of $n$ elements having $k$ cycles. To count these, we need to differentiate with respect to $u$ and set $u=1$, obtaining $$ \left. \frac{d}{du} G(z, u) \right|_{u=1} = \left. \exp \left( u \log \frac{1}{1-z} \right) \log \frac{1}{1-z} \right|_{u=1} = \frac{1}{1-z} \log \frac{1}{1-z} .$$

But $$ [z^n] \frac{1}{1-z} \log \frac{1}{1-z} = H_n $$ by a trivial calculation and we are done.

There is much more on this method at Wikipedia.

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.