View Question
 Question
 Subject: Permutation/Combination Question Category: Science > Math Asked by: ask_mike-ga List Price: \$15.00 Posted: 13 Nov 2006 16:06 PST Expires: 04 Dec 2006 10:20 PST Question ID: 782501
 ```Suppose you have 24 pennies to put into 10 unique jars (A to J). Constraints: 6 of the 10 jars can hold between 0 and 6 pennies. 4 of the 10 jars can hold between 0 and 3 pennies. What are the possible combinations of pennies to jars.```
 There is no answer at this time.

 Subject: Re: Permutation/Combination Question From: whytzedotnet-ga on 14 Nov 2006 00:29 PST
 ```Not sure what your asking but I have two possible answers that could both be extended if you want. 1)a)There are 24 pennis for every 10 jars b)There are 2.4 pennis for every jar c)There are 12 pennies to 5 jars d)24:10, 2.4:1, 12:5 e)There are 100 pennies for every 41.666666(never ending) jars 2)6 of the 10 jars can hold between 0 and 6 pennies. (jar I) 4 of the 10 jars can hold between 0 and 3 pennies. (jar II) 24 pennis can fit in. a)4 full jar I (4x6=24) b)3 full jar I and 2 full jar II ([3x6]+[2x3]=24) etc...```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 20 Nov 2006 15:55 PST
 ```If I am understanding your question correctly (and did my arithmetic right), there are 9,613,520 ways to distribute the pennies into the jars. I am assuming the jars are distinguishable but the pennies are not. There are six jars each of which has a maximum capacity of 6 pennies?let's call these "S jars"; and four with a capacity of 3 pennies?call them "T jars." We can put: 0 pennies in T jars and 24 in S jars; or 1 penny in a T jar and 23 in S jars; or 2 pennies in T jars and 22 in S jars; . . . on up to. . . 12 pennies in T jars and 12 in S jars. (We can't put more than 12 in T jars because 12 fills them all to capacity.) So now we have to figure: (Ways to put 0 pennies in 4 T jars) x (Ways to put 24 pennies in 6 S jars) + (Ways to put 1 penny in 4 T jars) x (Ways to put 23 pennies in 6 S jars) + (Ways to put 2 pennies in 4 T jars) x (Ways to put 22 pennies in 6 S jars) + . . . + (Ways to put 12 pennies in 4 T jars) x (Ways to put 12 pennies in 6 S jars). Let's look at T jars first (much easier!): There's just 1 way to put 0 pennies in 4 T jars: 0 0 0 0 There are 4 ways to put 1 penny in 4 T jars: 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 There are 10 ways with 2 pennies: 2 0 0 0 (4 permutations) + 1 1 0 0 (6 permutations) 20 ways with 3 pennies: 3 0 0 0 (4 perm) 2 1 0 0 (12 perm) 1 1 1 0 (4 perm) and, by similar reasoning: 31 ways with 4 pennies; 40 ways with 5 pennies; 44 ways with 6 pennies; 40 ways with 7 pennies; 31 ways with 8 pennies; 20 ways with 9 pennies; 10 ways with 10 pennies; 4 ways with 11 pennies; and 1 way with 12 pennies. The S jars are harder!! With a lot of pencil-pushing and subsequent comparison to integer sequences listed online, it turned out that the number of ways to put n pennies in 6 jars such that no jar has more than 6 pennies (and jars can be empty) is exactly C(n+5,5). We get: There are 118,755 ways to put 24 pennies into six S jars; 98,280 to put 23; 80,730 to put 22; . . .and so on down to. . . 6188 ways to put 12 pennies into six S jars. It remains only to calculate (1x118755)+(4x98280)+(10x80730)+. . .+(1x6188), giving a final answer of 9,613,520. Hope this helped.```
 Subject: Re: Permutation/Combination Question From: berkeleychocolate-ga on 22 Nov 2006 15:03 PST
 ```I have to disagree with emoll on his key claim that the number of ways to put n pennies into 6 jars such that each jar has at most 6 pennies is C(n+5,5). This combination is by a well-known formula of combinatorics the number of ways to put n pennies into 6 jars such that each jar contains at least one penny. So I doubt very much that it is also the ways with the condition that each is at most 6. It is not hard to get the number of ways with no conditions on how many pennies go into each jar. Then one must subtract the ways in which the condition is false: Some jar contains more than 6 pennies. I believe this number is C(n-6+5,5) - C(6,1)*C(n-7+6,5). The first term represents how many ways to put n objects into 6 jars with no restrictions. C(6,1) represents which jar has more than 6. C(n-7+6,5) is the number of ways to put n objects into 6 jars with a specific one of them containing at least 7 objects.```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 23 Nov 2006 06:40 PST
 ```Well, I must respectfully disagree with berkeleychocolate. Let me emphasize that I did not use a preconceived notion that C(n+5,5) would be the appropriate formula and then try to make the data fit in some Procrustean way. Rather, I calculated by hand, not knowing what formula (if any) would apply. Even though the present problem requires only integer values of n between 12 and 24, inclusive (for number of pennies to go in S jars), I first hand-calculated the permutations for n = 0, 1, 2, 3, 4, 5, and 6. For example, here's how I handled n = 5: All 5 pennies could go in one of the six S jars: 5 0 0 0 0 0. (Each position from left to right represents a distinct jar.) But there are 6 permutations: (5 0 0 0 0 0, 0 5 0 0 0 0, 0 0 5 0 0 0, 0 0 0 5 0 0, 0 0 0 0 5 0, 0 0 0 0 0 5). Or 4 could go in one jar and 1 in another: 4 1 0 0 0 0. There are 30 permutations. That's 6!/4! : permutations of 6 items (here the numbers 4, 1, 0, 0, 0, 0) with one item (the 0) repeated 4 times. 3 in one and 2 in another: 3 2 0 0 0 0. That's 30 more permutations. 3 1 1 0 0 0 has 60 permutations (6!/2!3!) 2 2 1 0 0 0 has 60 permutations. 2 1 1 1 0 0 has 60 permutations. And 1 1 1 1 1 0, with 6 permutations. Please note that I am not at all requiring that at least 1 penny be in each jar. In fact, in the above case (n = 5), there is never a time when there is at least 1 penny in each jar. Anyway, add up the permutations above to get 6+30+30+60+60+60+6. Answer: 252. Calculating in such a fashion, I found the following values: n = 0 => 1 way. n = 1 => 6 ways. n = 2 => 21 ways. n = 3 => 56 ways. n = 4 => 126 ways. n = 5 => 252 ways (as illustrated above). n = 6 => 462 ways. It wasn't until this point that I googled "1 6 21 56 126 252 462". One of the hits was at the integer sequences website, and not until then did I have any inkling of the formula C(n+5, 5). (Go ahead: try it with n = 5: C(10, 5) = 10!/5!5! = 252.) But was I satisfied? NOOOOOO. I then proceeded to evaluate n = 12 *by hand* (in the manner I described above with n = 5; for n = 12 it took up a whole cramped page in my notebook) and got 6188. Only then did I try the formula C(17,5). And it was 6188. You suggested my formula would apply (as is "well known"?) only if each jar contains at least 1 penny. I've worked problems with such constraints: they can be solved using Stirling Numbers of the Second Kind. You gave a formula that you thought should work. Did you test it? I did. Would you agree that it is possible to put 5 pennies into six S jars? (This precise situation does not apply directly to the original pennies-in-jars problem, but I showed above just how it could be done [and in fact used the result, 252, to help solve the actual problem at hand].) Your formula, if 5 is substituted for n, gives: C(4, 5)-C(6,1)*C(4,5). This has no solution because C(4,5) does not exist. So try it with n = 12: C(11,5)-C(6,1)*C(11,5). This has an answer, but unfortunately it's -2310. (Note that it's no coincidence that the first term and the second factor of the second term are the same: n-6+5 will always equal n-7+6. [Which is bad news here: for n>0 your formula always results in subtracting from one number a larger multiple of itself!]) Having said all that: my compliments to you, berkeleychocolate, on your fine work on *many* previous GA math problems!```
 Subject: Re: Permutation/Combination Question From: berkeleychocolate-ga on 24 Nov 2006 22:34 PST
 ```Hi, Emoll, Actually both of us are somewhat wrong. My formula isn?t quite sophisticated enough. One has to use the inclusion-exclusion principle and find the total nbr of ways minus the nbr of ways one box contains more than 6 plus the nbr of ways 2 boxes contain more than 6 minus the nbr of ways 3 boxes contain more than 6, etc. I?m pretty sure that will be correct, but the nbr of terms to add and subtract varies with n. But let?s just look at one situation: n=12. You claim that C(17,5) = 6188 is the nbr of ways to put 12 pennies into 6 boxes with no more than 6 pennies in a box. I claim it is 4676. There is a theorem of combinatorics that the nbr of ways to put n objects into b boxes such that each box contains at least one object is C(n-1,b-1). [Proof: Imagine n 1?s all lined up. We must choose b-1 of the n-1 spaces where we put the +?s.] The argument can be varied. For example, suppose we want the nbr of ways to put n objects into b boxes with no restrictions. Say the nbrs are n_1, ?, n_b. They all add to n. Let m_i = n_i + 1. Then the m_i?s add to n+b and each m_i is at least 1. So by the first formula the answer is C(n+b-1,b-1). Similarly the nbr of ways n objects can be put into b boxes where the first box has at least 7 can be found as follows: Let the nbrs be n_1,?, n_b. Let m_1 = n_1 - 6 and m_i = n_i +1 for i>=2. So the restrictions on the m_i?s are that each is at least 1 and they sum to n-6+b-1. So by the first formula the nbr of ways to do this is C(n-6+b-1-1,b-1) = C(n+b-8, b-1). Letting n=12 and b=6 we get that C(12+6-1,6-1) = C(17,5) = 6188 is the nbr of ways for 12 pennies to be put into 6 jars with no restrictions. Also C(12+6-8, 6-1) = C(10,5) = 252 = the nbr of ways with the first jar containing at least 7 pennies and no restrictions on the other jars. So 6188 ? 6*252 = 4676 is the nbr of total ways minus the nbr of ways that one of the 6 jars contains 7 or more. [Note: It is impossible for 2 jars to contain 7 or more since 14>12. So the events ?jar i contains at least 7? are mututally exclusive.] This is the nbr of ways where all 6 of the jars contain 6 or less. Except for this step you have done an excellent job with this tricky problem.```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 25 Nov 2006 08:34 PST
 ```Please explain to me what is wrong with the following reasoning. We want to put 12 pennies in six jars. Each jar has a maximum capacity of 6 pennies, and any jar may be left empty. Let us call the jars A, B, C, D, E, and F. We can put 12 pennies in A (12 0 0 0 0 0). Or 12 in B (0 12 0 0 0 0). Or 12 in C (0 0 12 0 0 0). Or 12 in D (0 0 0 12 0 0). Or 12 in E (0 0 0 0 12 0). Or 12 in F (0 0 0 0 0 12). That's 6 ways so far. We can put 11 in A and 1 in B (11 1 0 0 0 0). Or 11 in A and 1 in C (11 0 1 0 0 0). Or . . . Listen--I'd love to type all of this out to make my argument detailed beyond reproach, but if I did the whole 12-penny argument this way there wouldn't be room, and I'd probably be typing for several days and require hospitalization for my hands. (24 pennies could take weeks!!) So will you allow this shortcut? The immediate concern at this point is how many ways can we arrange the numbers 11, 1, 0, 0, 0, 0. Will you allow that the number of ways to arrange the numbers 11, 1, 0, 0, 0, 0 is 6!/4!, because we have 6 items (the numbers 11, 1, 0, 0, 0, and 0), and one of them (the 0) is repeated 4 times, and P(6,4) (permutations of 6 items with one repeated 4 times) applies? If you don't believe it, go ahead and write out all the permutations of 11, 1, and four 0s: I'm all in favor of thoroughness! There are 30 ways. You get this answer whether you use 6!/4! or write the things out by hand. Next comes 10 2 0 0 0 0. But 6!/4! also applies here (permutations of a 10, a 2, and four 0s). That's 30 more ways. Now we have 10 1 1 0 0 0. We don't use 6!/4! here, but rather 6!/2!3!, because there are six items: the 10, two 1s, and three 0s, with one (the 1) appearing 2 times and another (the 0) appearing 3 times. If you'd rather write out all the arrangements (permutations) of 10 1 1 0 0 0, be my guest. If you get anything other than 60 ways (which is 6!/2!3!), please let me know. So that's 60 more. Unfortunately, at some point I have to begin summarizing. But if my logic is anything less than airtight at any point, please point out the *specific* flaw with it. Then comes 9 3 0 0 0 0 and its permutations. There are 6!/4! of them. That's 30 more. 9 2 1 0 0 0 gives 6!/3!, or 120, more. 9 1 1 1 0 0: 6!/3!2!, or 60, more. 8 4 0 0 0 0: 6!/4!: 30. 8 3 1 0 0 0: 6!/3!: 120. 8 2 2 0 0 0: 6!/2!3!: 60. 8 2 1 1 0 0: 6!/2!2!: 180. 8 1 1 1 1 0: 6!/4!: 30. 7 5 0 0 0 0: 6!/4!: 30. 7 4 1 0 0 0: 6!/3!: 120. 7 3 2 0 0 0: 6!/3!: 120. 7 3 1 1 0 0: 6!/2!2!: 180. 7 2 2 1 0 0: 6!/2!2!: 180. 7 2 1 1 1 0: 6!/3!: 120. 7 1 1 1 1 1: 6!/5!: 6. 6 6 0 0 0 0: 6!/2!4!: 15. 6 5 1 0 0 0: 6!/3!: 120. 6 4 2 0 0 0: 6!/3!: 120. 6 4 1 1 0 0: 6!/2!2!: 180. 6 3 3 0 0 0: 6!/2!3!: 60. 6 3 2 1 0 0: 6!/2!: 360. 6 3 1 1 1 0: 6!/3!: 120. 6 2 2 2 0 0: 6!/3!2!: 60. 6 2 2 1 1 0: 6!/2!2!: 180. 6 2 1 1 1 1: 6!/4!: 30. 5 5 2 0 0 0: 6!/2!3!: 60. 5 5 1 1 0 0: 6!/2!2!2!: 90. 5 4 3 0 0 0: 6!/3!: 120. 5 4 2 1 0 0: 6!/2!: 360. 5 4 1 1 1 0: 6!/3!: 120. 5 3 3 1 0 0: 6!/2!2!: 180. 5 3 2 2 0 0: 6!/2!2!: 180. 5 3 2 1 1 0: 6!/2!: 360. 5 3 1 1 1 1: 6!/4!: 30. 5 2 2 2 1 0: 6!/3!: 120. 5 2 2 1 1 1: 6!/2!3!: 60. 4 4 4 0 0 0: 6!/3!3!: 20. 4 4 3 1 0 0: 6!/2!2!: 180. 4 4 2 2 0 0: 6!/2!2!2!: 90. 4 4 2 1 1 0: 6!/2!2!: 180. 4 4 1 1 1 1: 6!/2!4!: 15. 4 3 3 2 0 0: 6!/2!2!: 180. 4 3 3 1 1 0: 6!/2!2!: 180. 4 3 2 2 1 0: 6!/2!: 360. 4 3 2 1 1 1: 6!/3!: 120. 4 2 2 2 2 0: 6!/4!: 30. 4 2 2 2 1 1: 6!/3!2!: 60. 3 3 3 3 0 0: 6!/4!2!: 15. 3 3 3 2 1 0: 6!/3!: 120. 3 3 3 1 1 1: 6!/3!3!: 20. 3 3 2 2 2 0: 6!/2!3!: 60. 3 3 2 2 1 1: 6!/2!2!2!: 90. 3 2 2 2 2 1: 6!/4!: 30. 2 2 2 2 2 2: 6!/6!: 1. Now all you have to do is add the number of permutations of (12 0 0 0 0 0), plus the number of permutations of (11 1 0 0 0 0), plus . . . all the way down to the number of permutations of (2 2 2 2 2 2). In other words (actually, symbols): 6+30+30+60+30+120+60+30+120+60+180+30+30+120+120+180+180+120+6+15+120+120+180+60+360+120+60+180+30+60+90+120+360+120+180+180+360+30+120+60+20+180+90+180+15+180+180+360+120+30+60+15+120+20+60+90+30+1. I did the addition by hand and got 6188. You can check my addition with a calculator, or a spreadsheet, or an abacus, or chisenbop (sp?)--whatever you like. Berkeleychocolate, you say the answer should be 4676. OK, I say: if the answer is really 4676, then 1512 of the ways I specified above shouldn't have counted. So I need you to tell me which 1512 shouldn't have counted. But if you can tell me even one that shouldn't have counted, I'll admit my method is faulty and my answer is wrong. I'm almost sorry I brought up the formula C(17,5). Not because it's wrong--in fact, it appears to be quite correct--but because you seem to think that I decided a priori that that formula should apply. I DID NOT, as I stated in a previous post. I worked the problem previously just the way I have worked it in this post: by examining all 6188 permutations of the 58 different sets each of which contains six nonnegative integers that sum to 12. I found the 6188 permutations *first*. The fact that I *later* found a nice combinatoric formula that fit was nice, but I wasn't then, nor am I now, depending on C(17,5) being 6188 to make my argument legitimate. Again: tell me which of the 6188 permutations I have described above do not correspond to a way of placing 12 indistinguishable pennies into six distinguishable jars such that each jar contains 0, 1, 2, 3, 4, 5, or 6 pennies--and I will withdraw my assertion.```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 25 Nov 2006 09:10 PST
 ```OK! I'm wrong! I'm wrong! I'm wrong! What was I thinking?? (12 0 0 0 0 0) doesn't count!! 12 is more than 6. DUHHHHHHHHHHHHHHH. I'm an idiot! This is a case of my getting so wrapped up in details that I missed the big picture! My basic approach was sound, but my execution stunk!!! This may qualify as the stupidest mistake I've ever made (quite a distinction). I apologize deeply for my blindness and for my suggestion that you, berkeleychocolate, were mistaken!! In terms of my last (embarrassing) post, the 58-addend sum (starting with 6+30+30+60+ . . .) needs to have its first 19 addends removed. Those 19 addends add up to (drum roll, please) 1512. Well, I hope you haven't already started on your refutation and that with this post I've saved you the trouble of castigating me further, but if you feel like it, go ahead: I deserve it!! In an effort to make amends I will attempt to work on ask_mike's original problem again and BE MORE CAREFUL. Again, I'm sorry, berkeleychocolate.```
 Subject: Re: Permutation/Combination Question From: berkeleychocolate-ga on 25 Nov 2006 16:52 PST
 ```Hi, emoll, I don't think that saying "you did an excellent job on this tricky problem" was castigating you. Keep up the good work!```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 26 Nov 2006 06:04 PST
 ```Thanks for the encouragement. And when I said "I hope . . . with this post I've saved you the trouble of castigating me further," I only meant castigating me further than I had already done myself! You were very kind, and I didn't mean to imply otherwise. Back to the topic at hand: I'm continuing to work on the original problem and hope to be able to post a real answer in a little while.```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 26 Nov 2006 09:01 PST
 ```Hi--my new and hopefully improved answer to the original query is: 2,173,573 ways. As in my original attempt, the scheme was to calculate: (Ways to put 0 pennies in 3-capacity jars)*(Ways to put 24 pennies in 6-capacity jars) +(Ways to put 1 penny in 3-capacity jars)*(Ways to put 23 pennies in 6-capacity jars) +(Ways to put 2 pennies in 3-capacity jars)*(Ways to put 22 pennies in 6-capacity jars) + . . . +(Ways to put 12 pennies in 3-capacity jars)*(Ways to put 12 pennies in 6-capacity jars). The corresponding terms I got were: (1*4676)+(4*5516)+(10*6306)+(20*7852)+(31*8372)+(40*9196)+(44*9331)+(40*9216)+(31*8637)+(20*7842)+(10*6771)+(4*5796)+(1*4676). I did all calculations by hand, so it's entirely possible some errors crept in. (I'm sure berkeleychocolate's combinatorial formulae are perfectly good, but I wasn't quite able to follow the explanations on how to use them.)```
 Subject: Re: Permutation/Combination Question From: emoll-ga on 26 Nov 2006 09:08 PST
 ```While I'm at it, let me correct a side remark I made in an earlier post: I said the situation where each container must contain at least one item can be handled with Stirling Numbers of the Second Kind. I later remembered that this is true only when the items themselves (not just the containers) are distinguishable.```