Straight Dope Message Board > Main Dice Probability
 User Name Remember Me? Password
 Register FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
08-18-2012, 11:43 AM
 ricksummon Guest Join Date: Apr 2000
Dice Probability

On the MathWorld site, it gives a formula for calculating the probability of rolling a total of p on n dice with s sides each. It starts by saying the number of possible ways to roll this total is the coefficient of the x^p term in the multinomial:

(x + x^2 + ... + x^s)^n

The rest of the article is simply about how to calculate this multinomial coefficient using a number of binomial coefficients. But it doesn't elaborate on why the multinomial coefficient itself is the correct answer, treating it as self-evident. However, it doesn't seem obvious to me. How can we prove that this is the case?
__________________
"Look, if I argue with you, I must take up a contrary position."
"Yes, but that isn't just saying 'No, it isn't!'"
"Yes, it is!"
"No, it isn't!"
#2
08-18-2012, 01:06 PM
 Indistinguishable Guest Join Date: Apr 2007
Consider what happens when you distribute out the calculation of (some sum of powers of x) * (some sum of powers of x) * ... * (some sum of powers of x).

Each way of choosing one term (i.e., one power of x) from each factor contributes 1 to the coefficient of xr, where r is the sum of the powers you chose.

Thus, the overall coefficient of xr is the total number of ways to choose one term from each factor with powers that add up to r.

In your particular case, each of the n factors corresponds to a particular die, with the s terms in each factor corresponding to the possible outcomes for that die.

Last edited by Indistinguishable; 08-18-2012 at 01:09 PM.
#3
08-18-2012, 04:05 PM
 ultrafilter Guest Join Date: May 2001
This is an application of what's known as generating functions, which are pretty slick. A good introductory combinatorics/discrete math book will have a section on generating functions, and there's a lot more out there.

Last edited by ultrafilter; 08-18-2012 at 04:06 PM.
#4
08-18-2012, 04:17 PM
 Lance Turbo Guest Join Date: Aug 1999
Quote:
 Originally Posted by ricksummon How can we prove that this is the case?
A fairly straightforward induction argument will do the trick. I can supply it upon request.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 12:06 PM.

 Contact Us - Straight Dope Homepage - Archive - Top

Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

Send questions for Cecil Adams to: cecil@chicagoreader.com