8
$\begingroup$

I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.

I've spent quite a bit of time working on this (for a while my friend and I were using Figurate numbers, as the early items in the series match up) but at this point I'm tired and stumped, and would love some assistance.

So far we've got something to this effect (apologies for the feeble attempt at mathematical notation - I usually reside on StackOverflow):

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

The first line simplifies the problem to just the lower numbers - where the count is increasing. Then, if we're looking for the count of the minimum possible (which is also now the max because of the previous line) there is only one way to do that so it is 1, no matter the n or m.

  • 0
    @Oscar: I just noticed your comment! See my answer.2010-09-14

3 Answers 3

9

Since the order matters i.e 2+3+4 is different from 3+4+2, you can use generating functions.

The number of ways to get a sum $S$ by rolling $n$ dice (with numbers $1,2,\dots,m$) is the coefficient of $x^S$ in

$ (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)$

Thus the number of ways is

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

  • 0
    Thanks a lot! Very helpful.2010-09-15
2

The formula in the last answer (of Yuval Filmus) seems to be wrong: for m=4,n=9,S=6 one gets a nonzero result while it's impossible to have a sum of 6 with 9 dices!

The wanted formula i guess is the one corresponding to the coefficient "c" at http://mathworld.wolfram.com/Dice.html

  • 0
    Yu$v$al's dice take $v$alues from 0 to m, not from 1 to m. Granted, these are not standard dice!2015-08-12
1

Continuing Moron's answer, you can break the final sum as follows:

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

For example, for your example, $m=6$, $n=2$, $S=7$, and the formula gives

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

  • 0
    Then there is only one term in the sum, $\binom{4}{1} \binom{2}{0} = 4$, which probably corresponds to $(1,2),(2,1),(4,),(,4)$. See Oscar's comment to Moron's answer. This problem can be fixed.2011-02-21