Estoy tratando de demostrar combinatoriamente que $$S(n+1, k) = \binom n0 S(0,k-1) + \binom n1 S(1,k-1) + \cdots + \binom nn S(n,k-1),$$ donde $S(n,k)$ representa el número de Stirling del segundo tipo. He recibido la indicación de que primero debería encontrar un argumento combinatorio para demostrar que $$\binom {n+1}k = \binom 0{k-1} + \binom 1{k-1} + \cdots + \binom n{k-1},$$ pero sólo puedo encontrar una prueba algebraica utilizando varias iteraciones de $$\binom {n+1}k = \binom nk + \binom n{k-1}.$$ ¿Podría alguien indicarme cómo debería pensar en estos problemas?
Respuesta
¿Demasiados anuncios?
Phicar
Puntos
937
Una pista: Escribiendo su identidad como una suma, usted tiene entonces $$S_{n+1,k}=\sum _{i=0}^n\binom{n}{i}S_{i,k-1}=S_{n+1,k}=\sum _{i=0}^n\binom{n}{n-i}S_{n-i,k-1}=\sum _{i=0}^n\binom{n}{i}S_{n-i,k-1}.$$ Donde los dos últimos pasos son sólo utilizando la simetría binomial y un cambio de variable. Ahora, S_{n,k} son el número de formas de partición $\{1,2,\cdots, n\}$ en $k$ bloques no vacíos disjuntos. Por lo tanto, ¿qué pasa si se eligen los elementos que van a estar en el bloque de $n+1$ y dividir el resto en $k-1$ ¿bloqueos?
