0

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!

Salih Ucan
  • 2,236
  • 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 Answers1

2

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?

joriki
  • 238,052
  • 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