Let f[n,s](x) be the probability of rolling the total x on n fair s-sided dice.

probability/dice.totals New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Let f[n,s](x) be the probability of rolling the total x on n fair
s-sided dice.  (A fair s-sided die has faces labeled 1, 2, ..., s with
any of these numbers equally likely to come up.)

Describe a simple and efficient pencil-and-paper procedure for
computing f[n,s](x) for any n, s, and x.

Hint: Pascal's Triangle---which I judge to be a "simple and efficient"
paper-and-pencil procedure---gives you the exact answer for quite a few
values of n, s, and x, and it's easy to see which ones are correct.  A
very small modification gives you the rest.

-- David A. Karr <karr@cs.cornell.edu> (October 1994)

Show solution

In an earlier article, David showed that f[n,s](x)=C(x-1,n-1) if
x<n+s  ( C(a,b)=a!/(b!*(a-b)!)

This can be shown in a part of the Pascal triangle.  Let x be the row
and n the position in each row.  Only the s right most positions in
each row should be kept.

For the other positions, first observe that f[1,s](x) = 0 for x>s, so
the first position in each row is 0.

For x>=n+s use that f[n,s](x) = Sum (j=1..s) f[n-1,s](x-j)

(i.e. first roll a number j with the first dice, then count the number
of ways to roll the sum x-j with the remaining dices)

To find the numbers to add in the triangle, you first take the number
to the left and above the current position, and then go along the
diagonal up to the right and add the s-1 numbers found.  (This rule is
actually applicable also for the original triangle, but it is easier
to just add the two numbers above the current position for this part).

The triangle for s=4 looks like this:

x                     n=1 2
1                     1  /  3
2                   1   1  /  4
3                 1   2   1  /  5
4               1   3   3   1  /  6
5             0 \ 4   6   4   1  /  7
6           0   3 \10  10   5   1  /
7         0   2  12 \20  15   6   1
8       0   1  12  31 \35  21   7   1
9     0   0  10  40  65 \56  28   8   1

Right of \ is the original Pascal triangle.

Example:

Number of ways of rolling the sum 7 with 3 4-sided dices=12 (=3+4+3+2)

Check:   Dice 1  2  3
         ============
              4  2  1
              4  1  2
              1  4  2
              2  4  1
              1  2  4
              2  1  4
              3  3  1
              3  1  3
              1  3  3 [Editor: printed "3  3  1", a repeat of the
                       seventh line, in the original]
              3  2  2
              2  3  2
              2  2  3

OK.

-- Goran Wicklund <euagwd@eua.ericsson.se>

Easier is to add the two numbers above the current position and
subtract the number found if you start with the number above and go s
positions up along the up-right diagonal.

> Number of ways of rolling the sum 7 with 3 4-sided dices=12 (=3+4+3+2)

Easier: 12=3+10-1

-- Goran Wicklund <euagwd@eua.ericsson.se> (October 1994)

Thanks to David's hint, I recognize that row n of Karaji's (Pascal's)
Triangle, where the first row (1) is row 0, divided by 2^n gives the
successive probability for each x for 2 sided dice (coins.)

I would suspect that for 3 sided dice we would use Karaji's Pyramid,
etc. adding another dimension with each new side for the dice.  I
don't quite know the pencil-and-paper technique for these, only that
they are similar to the Triangle.

P.S.  It is Karaji's out of deference to my Combinatorics prof., who
insists, probably quite rightly, that Karaji discovered it 500 years
before Pascal, and that science is too Eurocentric.  |:3)

-- Scott Purdy <spurdy@pomona.claremont.edu>