Un problema de Combinatoria de Brualdi sobre el cálculo de los Números de Stirling

Quizás desconozcas este enfoque, pero podemos resolver este problema usando funciones generatrices y la recurrencia fundamental para los números de Stirling del segundo tipo. De hecho, esto se hace como ejemplo en el fantástico libro de Herbert Wilf, Generatingfunctionology .

Dejar,$S(n, k) = {n \brace k}$Sea el número de Stirling de segunda clase.

tenemos, por$n, k \gt 0$eso,

$$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$$ con el valor inicial$S(0,0) = 1$.

Definir la función generadora$F_k(x) = \displaystyle \sum_{n \ge 0} S(n, k) x^n$

Entonces, de la relación de recurrencia, obtenemos después de sumar$n$,

$$F_k(x) = xF_{k-1}(x) + kxF_k(x)$$ de la que tenemos, $$F_k(x) = \dfrac{x}{1 - kx}F_{k-1}(x) = \displaystyle \prod_{r = 1}^k \dfrac{x}{1 - rx}$$ ya que el valor inicial es$F_0(x) = 1$.

Ahora, necesitamos hacer una expansión en fracciones parciales del denominador en el producto para obtener la fórmula explícita.

Dejar,$\displaystyle \prod_{r = 1}^k \dfrac{1}{1 - rx} = \displaystyle \sum_{j = 1}^k \dfrac{p_j}{1 - jx}$

Multiplica de forma cruzada un factor a la vez y establece ese factor en cero. Eso lo conseguimos fácilmente,

$$p_j = \displaystyle \prod_{r = 1}^{k; r \ne j} \dfrac{1}{1 - \frac{r}{j}} = (-1)^{k - j}\dfrac{j^k}{j! \cdot (k-j)!}$$

Por lo tanto, tenemos,

$$F_k(x) = \displaystyle \sum_{n \ge 0} S(n, k) x^n = x^k \displaystyle \prod_{r = 1}^k \dfrac{1}{1 - rx}$$ $$\implies F_k(x) = x^k \displaystyle \sum_{j = 1}^k \dfrac{p_j}{1 - jx}$$ $$\implies F_k(x) = x^k \displaystyle \sum_{j = 1}^k p_j(1 + jx + j^2 x^2 + \dots)$$ $$\implies F_k(x) = \displaystyle \sum_{j = 1}^k p_j(x^k + j x^{k+1} + \dots)$$

El coeficiente de$x^{k + r}$en el lado derecho no hay nada más que$\displaystyle \sum_{j = 1}^k p_j \cdot j^r$. Configuración$k + r = n$y usando la definición de la función generadora, tenemos,

$$S(n, k) = \displaystyle \sum_{j = 1}^k p_j \cdot j^{n - k}$$ Y usando la expresión para$p_j$, finalmente conseguimos, $$S(n, k) = \displaystyle \sum_{j = 1}^k (-1)^{k - j}\dfrac{j^n}{j! \cdot (k-j)!}$$

Aunque no se puede decir que calcular los números de Stirling usando esta fórmula sea muy eficiente, la ventaja es que esta fórmula soluciona todos los problemas como el de Brualdi a la vez. Espero eso ayude.

solo una pequeña notación$S(n,k)$lo denoto por${n\brace k}$Probablemente hayas aprendido que

$$x^n=\sum _{k=0}^n{n\brace k}x^{\underline{k}},$$ dónde$x^{\underline{k}}=x(x-1)\cdots (x-k+1)$Darse cuenta de$x^{\underline{x+1}}=\cdots =x^{\underline{n}}=0$si$x<n$es un número entero. Entonces $$x^n=\sum _{k=0}^x{n\brace k}x^{\underline{k}}=\sum _{k=0}^x{n\brace k}\frac{x!}{(x-k)!},$$ y entonces $$\frac{x^n}{x!}-\sum _{k=0}^{x-1}{n\brace k}\frac{1}{(x-k)!}={n\brace x}.$$

Entonces, si sabes$S(8,0),S(8,1),S(8,2)$entonces puedes conseguir$S(8,3)$desde allí.