Loading [MathJax]/extensions/TeX/mathchoice.js

7 votos

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

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 Ncomo sigue: f(σ)=ni=1mi donde mi=i si ith pelota en σ tiene el mismo color con su anterior pelota, de lo contrario vamos a mi=1.

Mi pregunta es:

¿La identidad de σSf(σ)=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 n1 bolas del mismo color pero con diferente color, tendremosσSf(σ)=n!(112++1i(i+1)++1n)=n!
  3. Si las dos bolas tengan el mismo color y el resto tienen todos los diferentes colores, podemos también obtener unσSf(σ)=(n2)!(2+3++n+n(n1)2n+1)=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?

1voto

Anmol Saraf Puntos 155

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 mi i+x si mi1(donde x es un indeterminado), por lo que el f(σ) puede ser considerado como un polinomio con coeficientes enteros. Ahora podemos probar a σSf(σ)=(n+x)!r!(x+r)! donde (k+x)!=ki=1(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 n1,n2,,nr ser los números de las bolas con el color de la 1,2,,r respectivamente, y n1++nr=n. Tenga en cuenta que para cada permutación σS, tenemos una secuencia de los colores c1,c2,,cr tal que ci aparece antes de lo cj si i<j, por lo que podemos dividir S a r! subconjuntos Sp en términos de la permutación de 1,2,,r. Pretendemos que σSpf(σ)=(n+x)!(r+x)!holds for all the permutation ps of 1,2,,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,,r}.

si n1=1, uno tiene que σSp debe tener la forma 12, por lo que de acuerdo a la hipótesis de inducción tenemos σSpf(σ)=((x+1)+n1)((x+1)+(r1))!=(n+x)!(x+r)! esto acaba de sustituir a x x+1 n1bolas con r1 colores(la razón de hacerlo es que se trata de una ecuación polinómica).

si n12, se sabe que la forma de σSp 11 o 12, para el primer caso tenemos aσSp and with form 1f(σ)=(x+2)((x+1)+n1)!((x+1)+r)! para el segundo caso, denotan la más grande de color antes de que el segundo1a, para cada una de las a tenemos una permutación p={2,3,,a,1,a+1,r}, ya que nuestra hipótesis es independiente de p tenemos queσSpwith form 2f(σ)=(r1)((x+1)+n1)!((x+1)+r)! donde el término " r1 proviene de que la a r1 valores 2,3,,r.

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X