1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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