Generating function of multiset cycles?

Question

I've been tossing the idea of multiset cycles around in my head for the past day or two. In Stanley's Enumerative Combinatorics, he defines a multiset cycle to be a sequence $(i_1,i_2,\dots,i_k)$ of positive integers similar to cycles from algebra, but with repetitions allowed. For a cycle $C=(i_1,\dots,i_k)$, the weight of $C$ is defined as $w(C)=x_{i_1}\cdots x_{i_k}$, where $x_1,x_2,\dots$ are indeterminates. Then a multiset permuation is just a multiset of multiset cycles.

I'm curious as to why

$$\prod_C (1-w(C))^{-1}=\sum_\pi w(\pi)$$

($C$ ranges over all multiset cycles and $\pi$ over all multiset permutations). Why is this true?

My thoughts — I try to rewrite the left as $$ \prod_C\frac{1}{1-w(C)}=(1+w(C)+w(C)^2+\cdots)(1+w(C')+w(C')^2+\cdots)\cdots $$ for $C,C\,',\dots$ multiset cycles. Now the weight of a permutation $\pi=C_1C_2\cdots C_j$ is then defined by the product $w(\pi)=w(C_1)\cdots w(C_j)$. So the summands of $\sum_\pi w(\pi)$ seem to "factor" into multiset cycles decompositions. Is it fair to then say that the equality holds since for each factors of $w(\pi)$ for some $\pi$ is picked up as a term in the product on the left hand side? (I believe the decomposition is unique up to order of factors, much like in algebra.)

I'm not fully convinced myself. What is the correct and more rigorous way to justify this equality?

Thank you,

Answer 1

By definition, a multiset permutation is a multiset of multiset cycles (so not necessarily distinct)

$$\pi=\{C_1,C_2,\dots,C_m\}$$

and the associated weight is $w(\pi)=w(C_1)\cdots w(C_m)$. Suppose we have an enumeration of all of the multiset cycles $\{C_i\}_{i=1}^\infty$ and we consider the partial products given by

$$\ell_n=\prod_{i=1}^n\frac{1}{1-w(C_i)}=\prod_{i=1}^n\left(1+w(C_i)+w(C_i)^2+\cdots\right).$$

There is a formula

$$\left(\sum_{a\in A} a\right)\left(\sum_{b\in B}b\right)=\sum_{(a,b)\in A\times B}ab,$$

which holds true any time certain convergence requirements are met, which generalizes to $n$-ary products via induction, and all of this carries over to the formal power series setting. Hence we may use the notation $\Gamma_n$ to stand for all products of the form $w(C_1)^{a_1}\cdots w(C_n)^{a_n}$ with $a_i=0,1,2,3,\dots$, which of course will be equal to a corresponding $w(\pi)$ for the appropriate multiset permutation $\pi$; with this we see that every summand of the partial product expansions is of the form $w(\pi)$.

Now every multiset of multiset cycles decomposes uniquely into a union of those very multiset cycles, counted with multiplicity obviously, so our final task is to see that for every permutation $\pi$, there is an $n$ such that $w(\pi)\in\Gamma_m$ for all $m\ge n$, and hence $w(\pi)$ shows up in the expansion of the partial product of $\ell(x_1,x_2,\dots)$ at some point. We can see this by letting $n$ be the maximum subscript of all of the $C_i$'s present in the multiset cycle decomposition of $\pi$.

What we've shown then is that every term in the expansion of the partial products of $\ell$ corresponds to a $w(\pi)$, and every $w(\pi)$ is eventually in all of the partial products of $\ell$. Finally, if you're worried about non-uniqueness of the $w(\pi)$, what we can do is consider this argument first where all of the terms $w(C_i)$'s are unknown but distinct variables - in which case the line of reasoning obtains - and then specialize (plug in for) the $w(C_i)$ however we wish afterwards.

Finally, let me point out that this is exactly analogous to the Euler product for the Riemann zeta function (and there are many other generalizations and analogues of this product, in fact). Here the multiset cycles $C_i$ correspond to prime numbers and the $\pi$'s to all the natural numbers.