2010-08-31
Permutation Puzzle
Among the things I'm not good at are combinatorics and whatnot -- Let's say you have a fixed set of 18 numbers all in the range from 1 to 6 (so obviously a bunch of duplicates), and you need to put 3 of the numbers in each of 6 ordered bins. How many ways can the totals in all the bins come out?
Subscribe to:
Post Comments (Atom)
I'm not clear on what you're asking. Would you say that:
ReplyDelete"One possibility is that all 18 numbers have value 1, in which case there's only 1 way the totals could come out. Another possibility is that we have 17 values of 1 and 1 value of 2, in which case there are 6 ways the totals could come out (1 for each bin the 2 could be in). If we limited ourselves to these 2 possibilities, then there are 7 ways the totals could come out."
?
Exactly. Or in other words: Of 18 dice rolled, let n1 be the number of "1"s rolled, n2 the number of "2"s, and likewise for n3, n4, n5, and n6. What's the formula for the number of ways 6 sums of 3 dice each can be made?
ReplyDeleteThere are 21 ways 2 dice can come out when order doesn't matter (sum of 1 through 6.) Likewise, there are 56 ways 3 dice can come out when order doesn't matter (sum from p = 1 to 6 the sum of n = 1 to p.) [I can go into more detail if desired but for now I'll move on.]
ReplyDeleteIt sounds to me like your question is equivalent to asking how many ways we can have 6 jars of 3 dice each, observing order of the jars but not observing order of dice within each jar (jar A with 1, 2, 3 and jar B with 4, 5, 6 is the same as jar A with 2, 3, 1 and jar B with 6, 4, 5, but not the same as jar A with 4, 5, 6 and jar B with 1, 2, 3). If this is the case, then I think the answer is 56^6.
I'm thinking about "totals", not just permutations. That is, jar A is the same whether it has {1,2,6} or {3,3,3}. So the permutations are an upper bound on what I was thinking of.
ReplyDeleteArggh, upon re-reading, it sounds like you're interested only in the sums. My previous answer regarded jar A with 1, 2, 3 as different than if jar A had 1, 1, 4. But if these are considered the same, then I reason as follows:
ReplyDeleteThere are 16 ways the sum of 3d6 can come out (3 through 18). [If a reader thinks it's 18-3=15, ask yourself about the ways a single die can come out: is it 6-1=5? Why not?]
The number of ways the sums can come out with 6 such groupings would then be 16^6.
Right, except that I'm assuming a "fixed set of 18 numbers".
ReplyDeleteExample #1: Say you have all 1's (18 of them). Then in that case the number of ways to sum them in bins is just 1 -- they'll all have a total of 3.
Example #2: Say you have 17 1's and 1 2. Then in that case there are 6 possible sums-in-bins -- 1 of the 6 will have "4", while the others all have "3".
So the question is: Is there a general formula, granted count-of-each-possible-number {n1, n2, n3, n4, n5, n6} (sigma n(i) = 18) to determine how many possible sums-in-bins are possible?
f(18,0,0,0,0,0) = 1
f(17,1,0,0,0,0) = 6
f(n1, n2, n3, n4, n5, n6) = ?