Una identidad curiosa de sumas ponderadas sobre permutaciones de un conjunto.

Question

Supongamos que tenemos $n$ bolas que son los mismos excepto en los colores, denotan $S$ a ser el conjunto de todas las permutaciones diferentes de las bolas.(es decir, el intercambio de dos bolas del mismo color será el mismo permutación)

Ahora podemos definir una función de $S$ $\mathbb{N}$como sigue: $$ f(\sigma)=\prod_{i=1}^nm_i $$ donde $m_i=i$ si $i$th pelota en $\sigma$ tiene el mismo color con su anterior pelota, de lo contrario vamos a $m_i=1$.

Mi pregunta es:

¿La identidad de $$\sum_{\sigma\in S}f(\sigma)=n!$$ mantenga durante todo el color de las bolas?

Ejemplo:

1. Podemos comprobar que, si todas las bolas tienen pares de colores distintos, entonces la identidad trivialmente sostiene.
2. Si $n-1$ bolas del mismo color pero con diferente color, tendremos$$\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. Si las dos bolas tengan el mismo color y el resto tienen todos los diferentes colores, podemos también obtener un$$\sum_{\sigma\in S}f(\sigma)=(n-2)!\left(2+3+\cdots+n+\frac{n(n-1)}{2}-n+1\right)=n!$$

Creo que la evidencia anterior no sólo debe de ser algún tipo de coincidencia, pero no puedo encontrar la combinatoria de la intuición detrás de él.

Así que, ¿alguien puede demostrar el por encima de identidad?o encontrar un contraejemplo para refutar?

Answer 1

Acabo de encontrar una prueba de que aquí(En Chino).

Vamos a demostrar una versión más fuerte:

Heredamos las notaciones de la pregunta, pero el cambio de la $m_i$ $i+x$ si $m_i\not =1$(donde $x$ es un indeterminado), por lo que el $\sum f(\sigma)$ puede ser considerado como un polinomio con coeficientes enteros. Ahora podemos probar a $$\sum_{\sigma\in S}f(\sigma)=\frac{(n+x)!r!}{(x+r)!}$$ donde $(k+x)!=\prod_{i=1}^k(x+i)$ $r$ es el número de colores.(Uno puede fácilmente notar que la pregunta original es solo para $x=0$)

Prueba: Podemos demostrar la siguiente proposición por inducción en $n$

Deje $n_1,n_2,\cdots,n_r$ ser los números de las bolas con el color de la $1,2,\cdots,r$ respectivamente, y $n_1+\cdots+n_r=n$. Tenga en cuenta que para cada permutación $\sigma\in S$, tenemos una secuencia de los colores $c_1,c_2,\ldots,c_r$ tal que $c_i$ aparece antes de lo $c_j$ si $i<j$, por lo que podemos dividir $S$ a $r!$ subconjuntos $S_{\text{p}}$ en términos de la permutación de $1,2,\ldots,r$. Pretendemos que $$\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$ trivialmente tiene
2. Si $n=k$ mantiene, ahora podemos probar el caso de $k+1$.

Sin pérdida de generalidad, suponemos $p=\{1,2,\ldots,r\}$.

si $n_1=1$, uno tiene que $\sigma\in S_{p}$ debe tener la forma $12***$, por lo que de acuerdo a la hipótesis de inducción tenemos $$\sum_{\sigma\in S_p}f(\sigma)=\frac{((x+1)+n-1)}{((x+1)+(r-1))!}=\frac{(n+x)!}{(x+r)!}$$ esto acaba de sustituir a $x$ $x+1$ $n-1$bolas con $r-1$ colores(la razón de hacerlo es que se trata de una ecuación polinómica).

si $n_1\ge 2$, se sabe que la forma de $\sigma\in S_p$ $11***$ o $12***$, para el primer caso tenemos a$$\sum_{\sigma\in S_p\text{ and with form 1}}f(\sigma)=\frac{(x+2)((x+1)+n-1)!}{((x+1)+r)!}$$ para el segundo caso, denotan la más grande de color antes de que el segundo$1$$a$, para cada una de las $a$ tenemos una permutación $p'=\{2,3,\ldots,a,1,a+1\ldots,r\}$, ya que nuestra hipótesis es independiente de $p$ tenemos que$$\sum_{\sigma\in S_p\text{with form 2}}f(\sigma)=\frac{(r-1)((x+1)+n-1)!}{((x+1)+r)!}$$ donde el término " $r-1$ proviene de que la $a$ $r-1$ valores $2,3,\ldots,r$.

Tomar la suma de las dos partes anteriores, vamos a completar esta prueba.