Maneras a suma de $n$ $m$ enteros que son $\le k$

Question

Dados tres números naturales $n$, $m$ y $k$, ¿cuántas maneras hay para escribir $n$ como la suma de $m$ números naturales en el conjunto de $\{0, 1, \ldots, k\}$, donde el orden no importa?

He visto la de los "Modos de suma $n$ $k$ números", pero nunca donde los números están restringidas por una cota superior.

Ni siquiera estoy seguro de cómo proceder con esta pregunta. Tengo una secuencia de comandos de python para el cálculo de este (en esencia, se trata de la $(k+1)^m$ sumas posibles, calcula, y devuelve el número de sumas cuyo resultado es $n$). Tengo algunas ecuaciones en recurrencia, pero estoy casi 100% seguro que no ayuda mucho. Mediante la fijación del primer número de la suma a ser $0, 1, \ldots, k$, y la escritura $P(n, m, k)$ como la solución del problema:

P(n, m, k) = P(n,     m - 1, k) + # If the first number is 0
             P(n - 1, m - 1, k) + # If the first number is 1
             ...
             P(n - k, m - 1, k) + # If the first number is k

y

P(n, 1, k) = 0 if n > k
             1 if n <= k

Esto puede ser resuelto en una forma más elegante que la fuerza bruta?

Answer 1

No son muchas las fórmulas conocidas para el restringido número entero composición problema. El que le han dado,

$$p(n,m,k)=\sum_{i=0}^k p(n-i,m-1,k)$$

characterizes restricted integer compositions as extended binomial coefficients. If $k=1$, this is simply the formula for the binomial coefficients ($C(m,n)=C(m-1,n)+C(m-1,n-1)$). Así, el problema puede ser visto como una generalización natural de los coeficientes binomiales y sus números de generar un triángulo de Pascal como matriz.

Esta secuencia también puede ser de relevancia http://oeis.org/A008287

---

EDITAR Para calcular el número de $p(n,m,k)$ basado en la sobre la recurrencia, establecer una relación suficientemente grandes matriz $T(i,j)$, con todos los elementos inicializados a cero. Set $T(0,0)=1$. Entonces, para $i>0$, calcula el $T(i,j)=\sum_{i=0}^k T(i-1,j-i)$, hasta llegar a su fila $m$ y la columna $n$. Esto debería ser bastante rápido, no hay necesidad de que la enumeración exhaustiva. Por ejemplo, una secuencia de comandos de python para calcular $p(n,m,k)$ sería

  n=8; m=6; k=9
  T=[[0 for i in xrange(100)] for j in xrange(100)] # enough memory
  T[0][0]=1
  for j in xrange(1,m+1):
      for i in xrange(n+1):
          for r in xrange(k+1):
             if i-r>=0: T[j][i]+=T[j-1][i-r]
  print T[m][n]

El tiempo de ejecución es $O(mnk)$.

Answer 2

Hay una función de generación de la secuencia:

\begin{align} G(x,y) &= \frac{1}{1-y\left(1+x+x^2+\cdots+x^k\right)} \ &= \frac{1-x}{1-(x+y)+y\, x^{k+1}} \end{align}

donde $P(n,m,k)$ está dada por el coeficiente $\left[x^n\, y^m\right]$

Por ejemplo, $$P(8,6,9) = [x^8\, y^6] \frac{1-x}{1-(x+y)+y\, x^{10}} = 1287$ $

Answer 3

No es exactamente lo que quieres, pero al menos relacionados con:

OEIS A048887: Matriz de T leer por antidiagonals, donde T(m,n) = número de composiciones de n en partes <= m

Lo que falta es la condición de que sólo esas composiciones se cuentan, que consisten exactamente $m$ números de la anterior cuenta a todos. Por lo que al menos podría servir como un límite superior.

Por CIERTO, me preguntaba cómo la Enciclopedia en Línea de Entero de la Serie maneja multidimensional de la serie, que es una respuesta: una serie en dos dimensiones se da en la (anti-) diagonal de la enumeración.