7
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.