# Identity of generating function of weights of multiset cycles.

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.

-

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.

-
This makes much more sense, thank you. – Vika Feb 8 '12 at 3:42