Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting dice outcomes: # of matches

  1. Apr 14, 2010 #1
    Say you roll a die n times. Is there an easy way to calculate the number of ways it can happen that the most frequent number comes up j times? Equivalently, you could roll n dice at once and ask how many ways it could happen that j of the dice (but no more) match.

    For example, if you wanted the number of ways to get exactly a matching pair (but no matching triples, quads, etc.) in a roll of 5 dice, there are just two alternatives:

    1) There's only one pair, and the other three dice are all different. This happens in

    6*(5 choose 2)*5*4*3 = 3600 ways

    2) There are two distinct pairs, and the remaining die is different. This happens in

    (6 choose 2)*(5 choose 2)*(3 choose 2)*4 = 1800 ways

    So you have a total of 3600 + 1800 = 5400 ways of getting a pair in a roll of five dice. But this way of counting doesn't seem to be easily generalized to larger numbers of n and j. I thought about using Inclusion/Exclusion, but you have to have a term for every possible combination of j-tuples as well as combinations of j-tuples and (j+1)-tuples and higher (which are to be excluded). That is a mess.


    EDIT:

    Okay, I see how to generalize the way I did it above to larger n and j, but it is neither elegant nor easy to explain. I'm hoping there's a way that is one or the other.

    To make the above calculation easier to extend, I'll rewrite it using "multichoose" notation:

    Number of ways to get a pair (at most) in a roll of five dice

    = (5 multichoose 2,2,1)*(6 multichoose 1,2) + (5 multichoose 2,1,1,1)*(6 multichoose 3,1)
    = 1800 + 3600 = 5400

    Basically, you find the partitions of n=5 into numbers no greater than j=2, and for each one calculate (n multichoose a,b,c,...)*(6 multichoose i,j,k...) where a+b+c+... is the partition and i, j, k, are the numbers of times each distinct number occurs in the partition. Then add them up. See what I mean about explaining it? I barely understand it myself.
     
    Last edited: Apr 14, 2010
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted