¿Existe alguna fórmula cerrada para este problema de combinación?

S (n, k) son los números de Stirling sin signo del primer tipo .

La suma requerida es el coeficiente de x ^ (nk) en la expansión de (x + 1) (x + 2) … (x + n). Pero esto es igual al coeficiente de x ^ (n-k + 1) en la expansión de x (x + 1) … (x + n), que es una de las definiciones de los números de Stirling sin signo del primer tipo, c (n + 1, k). Es decir, S (n, k) = c (n + 1, n-k + 1).

Existen fórmulas para calcular los números de Stirling, pero quizás sea mejor evaluarlas con una recurrencia. S (n, k) es la suma de productos de todos los subconjuntos de elementos k de 1 … n. La suma de productos de subconjuntos que no incluyen n es claramente S (n-1, k), y la de aquellos que incluyen n es n S (n-1, k-1). Es decir, tenemos S (n, k) = n S (n-1, k-1) + S (n-1, k). Esta recurrencia se puede evaluar utilizando los casos base S (n, 0) = 1 para todo n, y S (0, n) = 0 para todo n> 0.