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.

How to show the following;

Using

$1 + \sum_{ n \geq 1} \frac {u^{n}}{n!} \sum_{\pi \in S_n} \Pi_{i}x_{i}^{N_i(\pi)} = \Pi_{m\geq1} \exp(u^m x_m / m)$ where $N_i(\pi)$ is the number of length $i$ cycles of a permutation $\pi$ on $n$-symbols

compute the expected number of $j$ cycles of a random permutation $\pi$.

Thanks a lot!

share|improve this question
    
This is a rare case where hyphens can make a difference in meaning. I suspect that you mean the number of $j$-cycles, i.e. the number of cycles of length $j$? –  joriki Feb 18 '13 at 10:39
    
The question can't be answered in its present form because you haven't specified a distribution. Presumably the random permutation is to be chosen uniformly from among some set of permutations? If so, which set? All permutations on a certain number of symbols? –  joriki Feb 18 '13 at 10:44

1 Answer 1

up vote 2 down vote accepted

I'll assume that you're asking about the expected number of $j$-cycles in a permutation uniformly randomly selected among all permutations on $n$ symbols.

Your equation relates to expressions for a generating function in which the coefficient of the term $u^n\prod_ix_i^{k_i}/n!$ counts the number of permutations on $n$ symbols with $k_i$ cycles of length $i$. The expected number of $j$-cycles in a uniformly random permutation on $n$ symbols is the sum of the numbers of $j$-cycles in all such permutations divided by the number $n!$ of all such permutations, and we get that by summing over the coefficients times the number $k_j$ of $j$-cycles. Thus the desired expected number is

$$ \begin{align} [u^n]\left.\frac{\partial}{\partial x_j}\prod_{m\ge1}\mathrm e^{u^mx_m/m}\right|_{x_k=1} &= [u^n]\frac{u^j}j\left.\prod_{m\ge1}\mathrm e^{u^mx_m/m}\right|_{x_k=1} \\ &= [u^n]\frac{u^j}j\prod_{m\ge1}\mathrm e^{u^m/m} \\ &= [u^n]\frac{u^j}j\mathrm e^{\sum_{m\ge1}u^m/m} \\ &= [u^n]\frac{u^j}j\mathrm e^{-\log(1-u)} \\ &= [u^n]\frac{u^j}j\frac1{1-u} \\ &=\begin{cases} 1/j&j\le n\;,\\ 0&j\gt n\;. \end{cases} \\ \end{align} $$

Thus the expected number of $j$-cycles in a permutation on $n$ symbols is $1/j$, unless $j\gt n$, in which case it is of course zero.

Note that this result can be more easily obtained directly: There are $(j-1)!$ ways of arranging $j$ given symbols in a cycle, $(n-j)!$ permutations of the remaining symbols and $n!$ permutations in total, so the probability for $j$ given symbols to form a cycle in a permutation randomly uniformly chosen among all permutations of $n$ symbols is

$$ \frac{(j-1)!(n-j)!}{n!}\;. $$

There are $\displaystyle\binom nj$ selections of $j$ out of $n$ symbols, so the expected number of $j$-cycles is

$$ \binom nj\frac{(j-1)!(n-j)!}{n!}=\frac1j\;. $$

Since the result doesn't depend on $n$ as long as $n\ge j$, one could in a certain sense say that the expected number of $j$-cycles in any random permutation, of unspecified length, is $1/j$, namely in the sense that the expected number of $j$-cycles in a permutation uniformly randomly chosen among all permutations on at most $n$ symbols goes to $1/j$ as $n\to\infty$; since you didn't specify a distribution, perhaps this is the result you were aiming at?

share|improve this answer
    
joriki what is the $[u^n]$ notation what does it mean? Thank you.. –  Salih Ucan Feb 25 '13 at 10:25
    
@Salih: $[u^n]f(u)$ is the coefficient of $u^n$ in the power series for $f(u)$. –  joriki Feb 25 '13 at 10:37
    
Joriki what is the power series expansion of the last expression could you write it in open form? is u between 0 and 1 so that that fraction is an infinite sum? Thank you –  Salih Ucan Feb 25 '13 at 10:48
1  
@Salih: Generating functions are treated as formal power series; one doesn't usually worry about their radius of convergence or substitute values into them (though that's not always true). The series for $1/(1-u)$ is $\sum_{k=0}^\infty u^k$, so the entire series is $\sum_{k=0}^{\infty}u^{k+j}/j$. –  joriki Feb 25 '13 at 11:27

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.