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.

It's been about nine years since I last undertook any formal mathematical training, and I am wrestling with generating probability curves in R.

What I want to know is, for a dicepool of an arbitrary number of d10s, how many combinations will result in a given value?

At the beginning and end of the range, this is easy to work out since with 5d10, there's only one combination which will result in 5: All 1s. For 6, once dice needs to be 2, so there are five combinations. That part, I'm not having issues with. But as you get into the midrange, the number of possible combinations which could result in a given total increases exponentially. There must be some formula which can let me calculate this. I've been attempting to work it out from wikipedia pages for most of the afternoon, but my grasp of mathematical jargon is now non-existent, so I am having some issues.

If someone has a formula I can plug numbers into, that would be fantastic.

share|improve this question
    
What does d10 mean? Does it mean dice? Also is this a standard die which produces values from $\{ 1, 2, \ldots, 6\}$? Or does the die have unrestricted range? (That is, can you throw any integer on a die?) –  Srivatsan Sep 30 '11 at 21:28
    
@SrivatsanNarayanan: A d10 is a die with 10 faces, numbers ranging from 0 to 9 or from 1 to 10. –  Raskolnikov Sep 30 '11 at 21:34
    
Ah. Sorry. A d10 is a ten sided dice. Values between 1 and 10. This is, technically, part of a coursework exercise. But I'm a game design student, and we don't get taught maths. I'm just trying to get some probability curves worked out, so I can put together the mechanics of a game's resolution system in an informed manner. Also, probability curves look great in reflective essays. –  user16949 Sep 30 '11 at 21:34
    
If you are using Excel, use the COMBIN function for doing the multinomial theorem. –  psr Sep 30 '11 at 23:51
add comment

3 Answers

up vote 6 down vote accepted

There's a trick to compute such numbers easily using polynomials. In the case of 5 d10 dice, take the following polynomial:

$$(x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10})^5 \; .$$

Working out this polynomial, the coefficient of $x^{20}$ for instance will give you how many different combinations of 5 d10 give a total sum of 20.

share|improve this answer
1  
In general: one needs the multinomial theorem. –  J. M. Sep 30 '11 at 22:01
    
I used to do this for combinations of various sided dice. e.g. for $1d4$ and $3d6$, you use the polynomial $x\frac{x^4-1}{x-1}\left(x\frac{x^6-1}{x-1}\right)^3$ –  robjohn Sep 30 '11 at 22:25
1  
@J.M. One can also use Faa-di-Bruno formula, specifically $\left(x+x^2+\ldots+x^{10}\right)^5 = \sum_{n=5}^{50} \frac{5!}{n!} B_{n,5}( 1!, 2!, \ldots, (n-5)! )$. Here is Mathematica code to attest to that Table[{5! BellY[n, 5, Range[10]!], D[Total[x^Range[10]]^5, {x, n}] /. x -> 0}, {n, 5, 10}]. –  Sasha Oct 1 '11 at 4:05
    
@Sasha: agreed, but methinks multinomial is slightly more familiar than the Bell polynomials... ;) –  J. M. Oct 1 '11 at 4:16
    
...and since $B_{n,i}(1!,2!,\dots)=\frac{n!}{i!}\binom{n-1}{i-1}=\left\lfloor n \atop i\right\rfloor$ where $\left\lfloor n \atop i\right\rfloor$ is a(n unsigned) Lah number, we can get even simpler expressions. –  J. M. Oct 1 '11 at 11:55
add comment

Suppose that you have $n$ $10$-sided dice whose faces are numbered $1$ through $10$, and you want the number of ways you can make a total of $t$. If each die were numbered from $1$ through $t$, this would be a straightforward stars and bars problem, and the answer would be $$\binom{(t-n)+(n-1)}{n-1}=\binom{t-1}{n-1}.$$

Unfortunately, each die can contribute at most $10$ to the total, so we have to subtract from this the ways that require a contribution greater than $10$ from some die. This will remove too much, since each way that requires a contribution greater than $10$ from two dice will be subtracted twice. This in turn will overcorrect, and we’ll need a further correction for the ways that are ‘bad’ on three dice. This process of correcting for overcorrection continues until we reach a stage at which we couldn’t have had that many ‘bad’ dice. What’s needed here is the inclusion-exclusion principle. After all of these corrections are made, we end up with

$$\sum_{k\ge 0} (-1)^k\binom{n}{k}\binom{t-1-11k}{n-1}$$

ways to make the total $t$. Since $\dbinom{n}{k}=0$ for $k>n$, this is actually a finite sum. Moreover, a little algebra shows that $$\binom{t-1-11k}{n-1}=0\text{ for }k>\frac{t-n}{11},$$ so the summation can be taken from $k=0$ to $k=\min\left\{n,\left\lfloor\dfrac{t-n}{11}\right\rfloor\right\}$.

You probably won’t want to calculate these values by hand, but it should be easy to write a little routine to do it.

share|improve this answer
add comment

The answer that Raskolnikov gave is the generating function of the number of ways to roll a given total. Multiplying polynomials convolves their coefficients as functions of their exponents. This is just what is needed for computing the number of ways to roll a given total. The polynomial for an $n$ sided die is $$ x\frac{x^n-1}{x-1} $$ Just multiply one such polynomial for each $n$-sided die.

share|improve this answer
add comment

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.