• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






divisibilidad stirling del segundo tipo.

+1 voto
Hola, necesito probar que si $n-m$ es impar entonces ${n \brace m}$  es un múltiplo de $\binom{m+1}{2}$, una prueba combinatoria sería lo más guay. Muchas gracias por su ayuda de antemano colegas.
preguntado por gamamal (2,400 puntos) Dic 10, 2014 en Combinatoria
editado por gamamal Dic 18, 2014
¿Qué significa $\{_m^n\}$? ¿Quisiste decir $\binom{n}{m}$?
es el coeficiente de stirling del segundo tipo. Es el número de particiones de un conjunto de $n$ elementos en $m$ partes no-vacías.

1 Respuesta

+1 voto
 
Mejor respuesta
Se ha de poder hacer más fácil que esto, pero ahí va una prueba:

Para $m$ fija, tenemos la función generatriz $f(x) := \sum_{n \ge m} {n \brace m} x^{n-m} = \prod_{r=1}^m \frac{1}{1-rx}$. (Esto es algo clásico que se puede probar usando la relación de recurrencia.) De aquí obtenemos que \[ f(x) + f(-x) = 2 \sum_{\substack{n \ge m \\ n-m\text{ impar}}} {n \brace m} x^{n-m}. \]

Lo que quieres probar es entonces equivalente a probar que la serie de potencias $f(x)+f(-x)$ tiene coeficientes enteros divisibles por $m(m+1)$. Ahora, usando la fórmula de arriba para $f$, tenemos que \[ f(x) + f(-x) = \left( \frac{1}{1-r^2x^2} \right) \left( \prod_{r=1}^m(1+rx) - \prod_{r=1}^m(1-rx) \right), \] y como el primer factor tiene expansión con coeficientes enteros, basta probar que el segundo factor tiene una expansión con coeficientes enteros múltiplos de $m(m+1)$.

Ahora, el segundo factor es \[ \prod_{r=1}^m(1+rx) - \prod_{r=1}^m(1-rx) = 2 \sum_{\substack{1 \le s \le m\\s \text{ impar}}} e_s(1,2,\ldots,m) x^s, \] donde $e_s(x_1, \ldots, x_m)$ es el $s$-ésimo polinomio simétrico elemental, es decir, la suma de todos los productos de $s$ de las $x_i$.

Entonces sólo resta probar que $m(m+1)$ divide a $2e_s(1,2,\ldots,m)$ para $s$ impar.

Notemos que $j \equiv -(k+1-j) \pmod{m+1}$, así que $e_s(1,2,\ldots,m) \equiv e_s(-m, -(m-1), \ldots, -1) = (-1)^s e_s(1,2,\ldots,m) \pmod{m+1}$. Cuando $s$ es impar, esto prueba que $m+1$ divide a $2 e_s(1,2,\ldots,m)$.

Por el mismo argumento, $m$ divide a $2 e_s(1,2,\ldots,m-1)$ y como $e_s(1,2,\ldots,m-1) \equiv e_s(1,2,\ldots,m) \pmod{m}$ (todos los términos extra en la segunda suma tienen un factor de $m$), también divide a $e_s(1,2,\ldots,m)$.

Como $m$ y $m+1$ son primos relativos, concluímos que $m(m+1)$ divide a $e_s(1,2,\ldots,m)$ para $s$ impar, como queríamos.
respondido por Omar Antolín (32,660 puntos) Mar 18, 2015
editado por Omar Antolín Mar 19, 2015
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...