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,
seem to "factor"
when it in fact they factor by definition do they not? Moreover, you sayI believe the decomposition is unique
: the only thing that really matters is that multiset permutations decompose uniquely as multisets of multiset cycles (this is an obvious fact). In fact, this generating function factorization is exactly analogous to the Euler product for the Riemann zeta function. The equality is certainly true as formal power series by what's been said so far, so this is all we need, no? $\endgroup$