¿Cómo puedo contar (algorítmicamente) el número de maneras en que n dados de m caras pueden sumar un número determinado?

Question

Estoy tratando de identificar el algoritmo del caso general para contar las diferentes formas en que los dados pueden sumar un número dado. Por ejemplo, hay seis maneras de sacar un siete con dos dados de 6.

He pasado bastante tiempo trabajando en esto (durante un tiempo mi amigo y yo estábamos usando los números de Figurate, ya que los primeros artículos de la serie coinciden) pero en este punto estoy cansado y perplejo, y me encantaría alguna ayuda.

Hasta ahora hemos conseguido algo así (disculpas por el débil intento de notación matemática - suelo residir en StackOverflow):

count(x):
   x = min(x,n*m-x+n)
   if x = n
      1
   else
      some sort of (recursive?) operation

La primera línea simplifica el problema a sólo los números más bajos - donde la cuenta es creciente. Entonces, si buscamos el recuento del mínimo posible (que ahora también es el máximo debido a la línea anterior) sólo hay una forma de hacerlo, por lo que es 1, sin importar n o m.

Answer 1

Como el orden es importante, es decir, 2+3+4 es diferente de 3+4+2, puedes utilizar funciones generadoras.

El número de formas de obtener una suma $S$ por el rodillo $n$ dados (con números $1,2,\dots,m$ ) es el coeficiente de $x^S$ en

$$ (x+x^2+\dots+x^m)^n = x^n(\frac{1-x^{m}}{1-x})^n$$

\= $$ x^n(1-x^{m})^{n}(\sum_{k=0}^{\infty} {n+k-1 \choose k} x^k)$$

Por lo tanto, el número de vías es

$$ \sum_{rm+k=S-n} {n \choose r} {n+k-1 \choose k} (-1)^{r}$$

Answer 2

La fórmula de la última respuesta (de Yuval Filmus) parece estar equivocada: para m=4,n=9,S=6 se obtiene un resultado distinto de cero, mientras que es imposible tener una suma de 6 con 9 dados.

La fórmula deseada supongo que es la correspondiente al coeficiente "c" en http://mathworld.wolfram.com/Dice.html

Answer 3

Continuando con la respuesta de Morón, se puede desglosar la suma final de la siguiente manera:

$$ \sum_{r=0}^{\lfloor S/(m+1) \rfloor} (-1)^r \binom{n-1+S-r(m+1)}{n-1} \binom{n}{r} $$

Por ejemplo, para su ejemplo, $m=6$ , $n=2$ , $S=7$ y la fórmula da

$$ \binom{8}{1} \binom{2}{0} - \binom{1}{1} \binom{2}{1} = 8 - 2 = 6 $$