Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A few days ago I asked this question on a generating function of multiset cycles.

There is was shown that $\prod_C(1-w(C))^{-1}=\sum_{\pi}w(\pi)$ where $w(\pi)$ is the weight a a multiset permutation $\pi$ as defined in the previous question. There's something more I'm curious about.

Supposedly it's the case that if $p_k=x^k_1+x^k_2+\cdots$, then $$ \prod_C(1-w(C))^{-1}=\prod_{k\geq 1}(1-p_k)^{-1}. $$

The explanation is that one notes that $$p^n_k=\sum_{d\mid n}\sum_A d(w(A))^{nk/d}, \tag{*}$$ where $A$ ranges over all aperiodic cycles of length $d$, that is, cycles of length $d$ unequal to a proper cyclic shift themselves. Substituting this equality into the expansion of $\log\prod(1-p_k)^{-1}$ gives the desired result upon simplification.

I don't fully follow this terse explanation. Can someone further clarify how the identity $(*)$ is deduced, and why the substitution yields the result? Thank you graciously.

share|cite|improve this question
up vote 2 down vote accepted

Consider what kinds of terms you'll get when you multiply $p_1^n$ out. They will all be of the form

$$\large x_{i_1}\cdot x_{i_2}\cdot x_{i_3}\cdots x_{i_n}, $$

where each index $i_j$ is chosen from the $j$th copy of $p_k$ in the product $p_k\times p_k\times\cdots\times p_k$. From each of these terms we associate the cycle $C=(i_1,i_2,\cdots,i_n)$. If this cycle is the concatenation of copies of the cycle $A$ (of length $d$), we may write $w(C)=w(A)^{n/d}$. Note that each of cyclic shifts of $A$ will appear as runs of indices in these expansion terms but the cycles themselves are identified under shifts, so we must weight $w(A)^{n/d}$ by $d$ (the number of shifts possible), i.e. $dw(A)^{n/d}$. Next, there are some $C$s that decompose this way and others that don't, so we may simply split the sum into sums indexed by divisors $d|n$ of sums indexed by aperiodic cycles of length $d$. Finally, observe that replacing $p_1^n$ with $p_k^n$ merely makes us put an exponent of $k$ on all of the variables, which we may do by putting $d w(D)^{kn/d}$ as the summand. Now use the Taylor expansion to find

$$\log \prod_{k=1}^\infty (1-p_k)^{-1}=\sum_{k=1}^\infty \sum_{n=1}^\infty \frac{1}{n}p_k^n=\sum_{k,n=1}^\infty \frac{1}{n}\sum_{d|n}\sum_{\operatorname{len}A=d} d\,w(A)^{kn/d} $$

$$=\sum_{k=1}^\infty \sum_A \sum_{\ell=1}^\infty \frac{w(A)^{k\ell}}{\ell}=\sum_C \log(1-w(C))^{-1}=\log \prod_C (1-w(C))^{-1}.$$

We made the substitutions $n=d\ell$ and $C=A^k$ above.

share|cite|improve this answer
This makes much more sense, thank you. – Vika Feb 8 '12 at 3:42

Your Answer


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.