Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
For a more general problem see: math.stackexchange.com/questions/4643/… –  alext87 Sep 14 '10 at 13:10
    
I imagine this can be done with generating functions (but I can't be bothered to actually do it, sorry). –  Oscar Cunningham Sep 14 '10 at 13:49
    
@Oscar: I just noticed your comment! See my answer. –  Aryabhata Sep 14 '10 at 14:16

2 Answers 2

up vote 5 down vote accepted

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}$$

share|improve this answer
    
Beat me to it! There's a slight typo, 1/(1-x)^n = sum C(k+n-1,k) x^k (off by one). –  Yuval Filmus Sep 14 '10 at 14:20
    
@Yuval: Thanks. Corrected. –  Aryabhata Sep 14 '10 at 14:28
    
Shouldn't the first expression be (x+x^2+x^3...x^m)^n [i.e. without the one on the front]? Otherwise you're saying that an m-sided dice can take any of the m+1 values from 0 to m. –  Oscar Cunningham Sep 14 '10 at 14:47
    
@OScar: You are right. I will edit the answer. –  Aryabhata Sep 14 '10 at 15:04
2  
Fun fact in this context: en.wikipedia.org/wiki/Sicherman_dice –  Hans Lundmark Sep 14 '10 at 18:17

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

share|improve this answer
    
Can you just show the calculation for m=6, n =2, and S=3 for this formula? –  Manoj R Feb 21 '11 at 10:34
    
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. –  Yuval Filmus Feb 21 '11 at 15:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.