# A curious identity of weighted sums over multi-set permutations.

Suppose we have $n$ balls which are the same except colors, denote $S$ to be the set of all different permutations of the balls.(i.e. the swap of two balls with the same color will be the same permutation)

We now define a function from $S$ to $\mathbb{N}$ as follow: $$f(\sigma)=\prod_{i=1}^nm_i$$ where $m_i=i$ if the $i$th ball in $\sigma$ has the same color with its preceding ball, otherwise let $m_i=1$.

My question is:

Does the identity $$\sum_{\sigma\in S}f(\sigma)=n!$$ hold for all coloring of the balls?

Example:

1. We can verify that if all the balls have pairwise distinct colors, then the identity trivially holds.
2. If $n-1$ balls have the same color but one with different color, we will have$$\sum_{\sigma\in S}f(\sigma)=n!\left(\frac{1}{1*2}+\cdots+\frac{1}{i*(i+1)}+\cdots+\frac{1}{n}\right)=n!$$
3. If two balls have the same color and the rest have all the different colors, we well get$$\sum_{\sigma\in S}f(\sigma)=(n-2)!\left(2+3+\cdots+n+\frac{n(n-1)}{2}-n+1\right)=n!$$

I think the above evidence should not just be some kind of coincidence, but I can not find the combinatorial intuition behind it.

So, can anyone prove the above identity?or find an counterexample to disprove it?

I just find a proof from here(In Chinese).

Let us prove a stronger version:

We inherit the notations in the question but change the $m_i$ to be $i+x$ if $m_i\not =1$(where $x$ is an indeterminate), so the $\sum f(\sigma)$ can be regarded as a polynomial with integer coefficients. We now prove $$\sum_{\sigma\in S}f(\sigma)=\frac{(n+x)!r!}{(x+r)!}$$ where $(k+x)!=\prod_{i=1}^k(x+i)$ and $r$ is the number of colors.(One can easily note that the original question is just for $x=0$)

Proof: We prove the following proposition by induction on $n$

Let $n_1,n_2,\cdots,n_r$ be the numbers of balls with color $1,2,\cdots,r$ respectively, and $n_1+\cdots+n_r=n$. Note that for each permutation $\sigma\in S$, we have a sequence of the colors $c_1,c_2,\ldots,c_r$ such that $c_i$ appears earlier than $c_j$ if $i<j$, so we can divide $S$ into $r!$ subsets $S_{\text{p}}$ in terms of the permutation of $1,2,\ldots,r$. We claim that $$\sum_{\sigma\in S_p}f(\sigma)=\frac{(n+x)!}{(r+x)!}$$holds for all the permutation $p$s of $1,2,\ldots,r$.

1. $n=1$ trivially holds
2. If $n=k$ holds, we now prove the case for $k+1$.

Without loss of generality, we assume $p=\{1,2,\ldots,r\}$.

if $n_1=1$, one has that $\sigma\in S_{p}$ must have the form $12***$, so according to the induction hypothesis we have $$\sum_{\sigma\in S_p}f(\sigma)=\frac{((x+1)+n-1)}{((x+1)+(r-1))!}=\frac{(n+x)!}{(x+r)!}$$ this just substitute $x$ to $x+1$ for the $n-1$ balls with $r-1$ colors(the reason we can do so is that it is an polynomial equation).

if $n_1\ge 2$, one knows that the form of $\sigma\in S_p$ are $11***$ or $12***$, for the first case we have$$\sum_{\sigma\in S_p\text{ and with form 1}}f(\sigma)=\frac{(x+2)((x+1)+n-1)!}{((x+1)+r)!}$$ for the second case, denote the largest color before the second $1$ to be $a$, for each $a$ we have a permutation $p'=\{2,3,\ldots,a,1,a+1\ldots,r\}$, since our hypothesis is independent of $p$ we have that$$\sum_{\sigma\in S_p\text{with form 2}}f(\sigma)=\frac{(r-1)((x+1)+n-1)!}{((x+1)+r)!}$$ where the term $r-1$ comes from that $a$ has $r-1$ values $2,3,\ldots,r$.

Take sum of the two parts above, we will complete this proof.