Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question stems from Probability of 3 of a kind with 7 dice as a means to check my understanding. I'm not sure whether this is general practice on this website, so I'm sorry if creating a new topic is frowned upon. I figured the question is large enough on its own to warrant a new topic. (Note: I intend to go back later to choose "best answer" on the previous one. It's a tough choice because I've used both extensively.)

Now without further ado:

With a set of three desired from 9 dice, there are

a) $ \binom{6}{1}\binom{9}{3}5^6 $

possible outcomes which contain one set of three.

These outcomes also contain other undesirables such as 111222222, 111222223, 111222333, etc. which must be accounted for.

Number of possibilities which contains a set of six in the remaining dice:

b) $ \binom{6}{2}\binom{9}{6}4^0 $

Number of possibilities which contains a set of five in the remaining dice:

c) $ \binom{6}{2}\binom{9}{5}4^1 $

Number of possibilities which contains a set of four in the remaining dice:

d) $ \binom{6}{2}\binom{9}{4}4^2 $

Number of possibilities which contains a set of three in the remaining dice:

e) $ \binom{6}{2}\binom{9}{3}\binom{6}{3}4^3 $

Number of possibilities which contain two sets of three in the remaining dice (three sets of three in the nine):

f) $ \binom{6}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}3^0 $

Now, this last set of three option (e) (ie. 111222345) may contain something that looks like 111222333 due to the randomness of the three remaining dice, so we need to subtract (f) from (e) in order to find the number of options which contain only 2 sets of three.

g) e - f: $ \binom{6}{2}\binom{9}{3}\binom{6}{3}4^3 - \binom{6}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}3^0$

Because (a) computes all combinations where there is one set of three, it will pull certain things twice, and certain other things even more. ex. 111222344 is the same as 222111344 AND 111222333 ~ 222111333 ~ 333222111: there are 3! different arrangements of this latter scenario.


I was initially planning to write out everything as I understood it, but as I try, I find myself going in circles and getting massively confused. To get the final solution of "how many ways to get exactly one set of 3 in 9 dice," there should be something like the following unless I'm mistaken:

$ a - b - c - d - ??? $

How many e's, f'g, and/or g's need to be taken out to account for both the initial duplicates counted in (a) (as described two paragraphs up) AND how many e's, f's, and/or g's need to be removed to ensure only one set of three remains confuses me.

Is what I have so far along the right path? If not, why?

If so, or even if just the overall idea is okay but the specifics are off, is there an easy/managable way to keep track of duplicates and items that need to be excluded in situations like this one?

I was also wondering if there's a good way to make use of the knowledge of that 111222333 ~ 333222111 is really just abc ~ cba; or 3! as opposed to working out more specifically what to include or exclude. Any ideas?

As always,

Many thanks.

PS

I got pulled away too many times while writing thanks to a dog who wanted to run around the house with a bloody toe, so I hope it all flows well.

Solution: I'm sad to say I basically gave up. I thought I had it, I can figure out specific scenarios, but in my chart the probabilities weren't adding up to 1 when all scenarios should have been accounted for. Therefore something someplace went horribly wrong. I took programmer approach and wrote a short script to count what I wanted out of a million rolls and filled in the chart that way (no, not exact, but close enough for what I want from it). I need a bath.

On the bright side all this grueling let me know why, when the program turned out unexpected results, it was right and could be explained.

share|improve this question
    
You are overcounting. 111222333 is counted in (a), in (e), and in (f), and it is counted three times in (a). –  Arturo Magidin Feb 25 '11 at 14:12
    
I don't understand how it would only be three times. 111222333 111333222 222111333 222333111 333111222 333222111 Wouldn't all of these be counted in (a)? –  emragins Feb 25 '11 at 17:29
    
@emragins: You misunderstand. Those 6 rolls are all counted, but they are each counted too many times. See how you are counting: first you select the rank of the triple, then you select where the triple goes, then you "fill out" the rest of the dice. So, say you select "1" as the rank for your triple, and "1-2-3" as the dice where they go; then one of the rolls you count is 111222333. But later, you select "2" as the rank for your triple, and you select "4-5-6" as the dice where they go, and one of the rolls you count is again 111222333. So you've counted the same roll twice. (cont) –  Arturo Magidin Feb 25 '11 at 17:51
    
@emragins. Then it gets counted again when you select "3" as the rank, and "7-8-9" as the dice where it goes, and when you fill out the remaining dice with 111222 (in that order). So $\binom{6}{1}\binom{9}{3}4^6$ counts this exact same roll three times, instead of just once. –  Arturo Magidin Feb 25 '11 at 17:52
2  
@emragins: Using my methods, I think there are 2520 ways of getting sets of 6 and 3; (b) gives 1260 but you should be using $6\times 5$ rather than $\binom{6}{2}$. I think there are 60480 ways of getting sets of 5, 3 and 1; (c) gives 7560. I think there are 151200+453600 = 604800 ways of getting sets of 4, 3 and 2 or 4, 3, 1 and 1; (d) gives 30240. I think there are 33600+907200+604800 = 1545600 of getting sets of 3, 3 and 3 or 3, 3, 2 and 1 or 3, 3, 1, 1 and 1; (e) gives 1612800 which is two (f)s too high. I think there are 33600 ways of getting sets of 3, 3 and 3; (f) agrees. –  Henry Feb 25 '11 at 18:37

2 Answers 2

up vote 1 down vote accepted

Henry's method is really superior here, because the number of things you need to keep track of by direct counting (both to account for inclusion/exclusion, and to get rid of "undesirables") gets more and more complicated as you increase the number of dice.

But let's discuss your counts, so you can see the errors.

One way to think about these counts is that you are giving instructions to someone on how to write down these rolls; the binomial coefficients just count how many ways that person can follow the instructions. So for example, when you want to count how many rolls have three 3-of-a-kinds, you can tell someone: "first pick what the 3-of-a-kinds will be; then to write them down, pick which dice the largest one shows up in, then which dice the smallest one shows up in; the middle one will be in the remaining dice". This explains how to write down any particular instance of three 3-of-a-kind. So you can say, "Okay, I'll pick 3, 5, and 2. Then I pick the dice for the 5s, which I will be 8-2-9; then from the remaining ones I'll pick the three dice for the 2s, which I choose to be 1-5-7. Then remaining dice, 3-4-6, that's where the 3s show up. That is, this roll is 253323255." Then the binomial coefficients just count the number of ways in which you can make each choice. But then you have to be careful with overcounting, not to count the same exact roll more than once by focusing on different parts of it (that's why here I said that your first choice of three dice would correspond to the largest of the ranks; if I had just said "the first rank you picked", then we could have ended up repeating this particular roll if we selected the ranks and the dice in a different order).

I will use $n$-oak to mean "$n$ of a kind"...

  1. As I mentioned, your count for the total numbers is off because you are overcounting. First we select the rank for the 3-oak. Then we select which dice it shows up in. Finally, we assign the remaining 6 dice to any of the remaining 5 ranks. However, this will overcount any roll that has several 3-oaks, because we will count it once for each 3-oak. So 111222345 will be counted once when we select 1 for the 3-oak and positions 1-2-3; and will be counted again when we select 2 for the 3-oak in positions 4-5-6. Likewise, rolls with three 3-oaks will be counted several times, once for each choice.

    How many times? Rolls with exactly two 3-oaks will be counted twice; rolls with three 3-oaks will be counted 3 times. So we want to count the number of rolls with two 3-oaks and subtract them from the previous total; and the number of rolls with three 3-oaks and subract them twice from the previous count.

    Okay, so let's count the number of rolls with two 3-oaks. We first select the two ranks; then we select where the higher rank shows up; then where the lower rank shows up; then we assign the remaining three dice to any of the remaining 4 ranks.

    However, this also counts rolls with three 3-oaks. In fact, it will count each one of them three times, because there are three ways in which we can specify two of the three 3-oaks. So if just subtract the total above, we will be subtracting three times the number of rolls with three 3-oaks, but we only wanted to subtract it twice. So we will need to count the rolls with three 3-oaks and add them back in.

    To count the number of rolls with three 3-oaks, select the three ranks, then decide where the highest rank goes, then where the lowest rank goes, the rest is now forced.

    (The process above is called "inclusion/exclusion"; first we included too much, then we subtract but we subtract too much, so then we include back in what need to; as the number of dice increases, you would then probably have to take out some stuff that you added back extra, then add back in some of them, etc. Complicated).

    So: "pick a rank for the 3-oak, pick the dice it shows up in, remaining six dice can be anything except the rank of the 3-oak" is $$\binom{6}{1}\binom{9}{3}5^6=7875000.$$ Then "select two ranks for two 3-oaks, select where the highest rank goes, select where the lowest rank goes, and the remaining three dice can be anything other than the ranks of these two" is $$\binom{6}{2}\binom{9}{3}\binom{6}{3}4^3=1612800.$$ And then "select the three ranks for the three 3-oaks; select where the highest rank goes, select where the lowest rank goes" is $$\binom{6}{3}\binom{9}{3}\binom{6}{3}=33600.$$ So you $A$ should have been $$A = 7875000-1612800+33600 = 6295800.$$

  2. A 3-oak and a 6-oak: first select the rank for the 3-oak, then the rank for the 6-oak, then select where the 3-oak is. Note that the order of choice matters, because the first choice is the 3-oak. So we get $$\binom{6}{1}\binom{5}{1}\binom{9}{3} = 2520.$$ You got fewer, because instead of selecting the rank for the 3-oak and the rank for the 6-oak, you just selected two ranks without specifying which one would be the 3-oak and which one would be the 6-oak. So here, you counted 111222222 the same as 222111111, which is incorrect.

  3. A 3-oak and a 5-oak. First select the rank for the 3-oak, then the rank for the 5-oak. Then decide where the 3-oak goes, then where the 5-oak goes. Finally, choose what the remaining die is, from the other four ranks: $$\binom{6}{1}\binom{5}{1}\binom{9}{3}\binom{6}{5}4=60480.$$ Again, your error was not to distinguish between which rank will be the 3-oak and which one will be the 5-oak. Selecting them with $\binom{6}{2}$ does not distinguish which one you pick first and which one you pick second.

  4. A 3-oak and a 4-oak. Here we have two possibilities: a 3-oak, a 4-oak, and a 2-oak; or a 3-oak, a 4-oak, and nothing else.

    For the first kind: select the rank for the 3-oak; then the rank for the 4-oak; then the rank for the 2-oak. Then select where the 3-oak goes; then select where the 4-oak goes. The pair is then forced into the remaining dice. This is $$\binom{6}{1}\binom{5}{1}\binom{4}{1}\binom{9}{3}\binom{6}{4} = 151200.$$ For the second kind: select rank for the $3$-oak, the rank for the $4$-oak; then select where the 3-oak goes, then where the 4-oak goes from among the remaining 6 positions. Finally, pick two ranks from the remaining 4, and select which dice will have the larger one of the two (this allows us to count them exactly); the remaining dice shows the smaller one. This is $$\binom{6}{1}\binom{5}{1}\binom{9}{3}\binom{6}{4}\binom{4}{2}\binom{2}{1} = 453600.$$ So we get a total of $151200+453600 = 604800$ rolls with a 3-oak and a 4-oak (accounting for both 3-oak, 4-oak, and 2-oak; and 3-oak, 4-oak, and two singletons).

  5. Two 3-oaks but not three. We counted them above: first select the two ranks; then the dice where the larger one goes; then select the dice for the lower rank. Then anything from the remaining 4 ranks to the other three dice. However, this will overcount, because we are including the rolls with 3-oaks, counting each of them three times. So we need to subtract the rolls with three 3-oaks three times. The number of ways of rolling three 3-oaks: select the three ranks, select where the highest ranking one goes, select where the lowest ranking one goes.

    So the first count is given by $$\binom{6}{4}\binom{9}{3}\binom{6}{3}4^3 = 1612800;$$ and then the ones we overcounted are given by $$\binom{6}{3}\binom{9}{3}\binom{6}{3} = 33600.$$ So we get $1612800 - 3(33600) = 1512000$.

    You tried to to take into account those three 3-oak rolls, but you did not compensate quite right, because you only subtracted the three 3-oak rolls once; you needed to subtract it more times, because you overcounted each of them more than once.

  6. Finally, three 3-oaks, which we figured out to be $33600$ above.

The totals above match up with Henry's in the comments.

So the total you would get from this would $$6295800 - (2520+60480 + 604800+1512000+33600) = 4082400,$$ same as Henry's answer, but after a lot more computations and having to keep track of a lot more things (and compensating for overcounts, then overcompensating for undercounts, etc.)

share|improve this answer
    
Wow, that's one heck of a post. Need... more... time.... I swear I'll get around to it. –  emragins Feb 25 '11 at 22:52

What was wrong with my previous method? 9 can be partitioned into up to 6 parts with one 3 and other parts smaller, in three ways, namely $3+2+2+2(+0+0)$, $3+2+2+1+1(+0)$, and $3+2+1+1+1+1$. So I think the answer is

$$ \frac{6!}{1!\;3!\;2!} \times \frac{9!}{3!\;2!\;2!\;2!} + \frac{6!}{1!\;2!\;2!\;1!} \times \frac{9!}{3!\;2!\;2!\;1!\;1!} + \frac{6!}{1!\;1!\;4!} \times \frac{9!}{3!\;2!\;1!\;1!\;1!\;1!} = 4082400 $$

i.e. just over 4 million.

share|improve this answer
    
Nothing was wrong with the method itself. I'm trying to create a chart that will compute hundreds of different probabilities similar to this question and the one before it. Unfortunately this method is more by-rote and doesn't lend itself to a variety of variables floating around. That said, I've found the method very helpful in checking my answers, but I am trying to understand it at perhaps a deeper level. –  emragins Feb 25 '11 at 17:28
    
Your choice, but I do feel my approach is more systematic and managable. –  Henry Feb 25 '11 at 17:46
    
@emragins: I think you are incorrect. This method does manage itself to a variety of variables floating around, even more so than the method you are trying (which needs you to keep track of inclusion-exclusion issues which are hard to program). Try to understand how this counting method works, you'll see that you can program it fairly easily. –  Arturo Magidin Feb 25 '11 at 18:11
    
Huh. I was starting to consider that for rolls which may yield three or more possible sets (as 3 dice from 9 does,) it would be faster to work out those manually with this method due to the expanding nature of the other method. While I feel I understand this method, it doesn't strike me as easier with variables since I feel it would be easier for a human to keep track of the different ways to subdivide rather than teaching a spreadsheet that logic. Since it seems I'm in the minority, I'll spend some time on it and see if I can't work it out with variables. –  emragins Feb 25 '11 at 18:20
    
@emragins: Really, you are taking a sort of "inverse" viewpoint: instead of deciding what rank each dice will show, you are deciding which dice will show each rank. So, $3+2+2+2+(0+0)$ says that one rank will be shown by $3$ dice; and three ranks will be shown each by two dice (so this will correspond to a 3-of-a-kind and three 2-of-a-kinds). Then you just count the number of ways to select the ranks and the dice assignment, which is what the multinomial coefficient does. –  Arturo Magidin Feb 25 '11 at 18:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.