Como estaba tratando de resolver un problema relacionado con algunas probabilidades discretas, tuve que evaluar $$ y(m) = \sum_{\substack {k_1 + ... + k_m = n \\ k_1 \geqslant 1, ..., k_m \geqslant 1}} \binom{n}{k_1, ..., k_m}, $$ aquí $n$ es una constante y $n \geqslant m$ . Esto me llevó a resolver la siguiente relación de recurrencia no trivial: $$ y(m) + \sum_{k = 1}^{m - 1} \binom{m}{k}y(m - k) = m^n, \\ y(1) = 1$$ . Me gustaría saber si es posible expresar $y(m)$ en una forma cerrada?
Respuesta
¿Demasiados anuncios?
Su $y(m)$ es el número de formas de poner $n$ bolas distinguibles en $m$ cajas distinguibles, con $\geq 1$ bola por caja. Esto es casi lo mismo que el Número de Stirling del segundo tipo $S(n,m)$ que es el número de formas de poner $n$ bolas distinguibles en $m$ cajas indistintas. La distinguibilidad de sus cajas significa que su $y(m)=m!S(n,m)$ ya que hay $m!$ formas de organizar las cajas.
No existe una solución de forma totalmente cerrada para $S(m,n)$ pero hay fórmulas explícitas, por ejemplo $$S(n,m) = \frac{1}{m!}\sum_k (-1)^{m-k} \binom{m}{k}k^n$$ De ahí que su $y(m)$ puede expresarse como $y(m) = \sum_k (-1)^{m-k} \binom{m}{k}k^n$ .
Se puede llegar a la misma fórmula mediante inclusión-exclusión : El número de formas de poner el $n$ bolas en $m$ cajas sin tener en cuenta el $\geq 1$ la condición de bola por caja es $m^n$ . El número de formas de poner las bolas en algunos $m-k$ cajas es $\binom{m}{k}(m-k)^n$ y aplicando la inclusión-exclusión para determinar el número de configuraciones que NO están contenidas en alguna $m-1$ cajas (lo que significa que cada caja tiene al menos una bola) da $$y(m) = m^n+\sum_k (-1)^k\binom{m}{k}(m-k)^n = \sum_k (-1)^{m-k} \binom{m}{k} k^n$$ como en el caso anterior.
