Probability of a Sum on Multiple DiceDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/