Probability of a Sum on Multiple Dice

Date: 03/26/2001 at 07:11:15
From: Regan
Subject: Probability of getting a sum s on n dice with x sides

Hi,

I want to be able to write a program for calculating the probability 
of getting a sum s on n dice with x sides.

I have seen the answer before and it uses binomial coefficients, but 
I can't find it again and I'm stuck.

Thanks.

Date: 03/26/2001 at 13:31:33
From: Doctor Rob
Subject: Re: Probability of getting a sum s on n dice with x sides

Thanks for writing to Ask Dr. Math, Regan.

You can figure this out by using generating functions.

The generating function for one die with x sides is

     f(z) = z + z^2 + z^3 + ... + z^x.

The coefficient of a term tells you how many ways you can roll the 
exponent of z in the term. In this case, for numbers from 1 to x, you 
can roll each in one way. For other numbers, like 0 and numbers 
greater than x, you can roll them in zero ways. Thus the above 
generating function is right for one die. For two dice, square the 
above function. For n dice, raise it to the nth power. Then you want 
the coefficient of z^s in that expression. When calculating this 
coefficient for some specific value of s, you can do the arithmetic 
and ignore all powers of z with exponents bigger than s. If you want 
all the probabilities, you can ignore all exponents bigger than 
(n*x+1)/2, because the number of ways of rolling s is the same as the 
number of ways of rolling n*x+1-s, and if one is larger than 
(n*x+1)/2, then the other is smaller.

To express this in binomial coefficients, you can write:

       f(z) = (z - z^[x+1]) / (1 - z)

     f(z)^n = [(z -z^[x+1]) / (1 - z)]^n

            = z^n * (1-z^x)^n * (1-z)^(-n)

                     n                               n
            = z^n * SUM (-1)^k * C(n,k) * z^(x*k) * SUM C(n+i-1,i) * z^i
                    k=0                             i=0

               n   n
            = SUM SUM (-1)^k * C(n,k) * C(n+i-1,n-1) * z^(n+x*k+i)
              k=0 i=0

Now the coefficient of z^s in this will be given by:

     (s-n)/x
       SUM  (-1)^k * C(n,k) * C(s-x*k-1,n-1)
       k=0

This is the formula you seek.

For example, if x = 6, n = 4, and s = 13, then the coefficient of z^13 
is:

     (13-4)/6
       SUM   (-1)^k * C(4,k) * C(12-4*k,3)
       k=0

     = (-1)^0 * C(4,0) * C(12,3)  +  (-1)^1 * C(4,1) * C(6,3)

     = 220 - 4*20
 
     = 140

This is the coefficient of z^13 in:

     z^4
   * (1 - 4*z^6 + ...)
   * (1 + 4*z   + 10*z^2 +  20*z^3 +  35*z^4 +  56*z^5 + 84*z^6 +
                         + 120*z^7 + 165*z^8 + 220*z^9 + ...)

Thus there are 140 ways to roll 13 with four 6-sided dice.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/