Google Answers Logo
View Question
 
Q: Permutation/Combination Question ( No Answer,   11 Comments )
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.
Answer  
There is no answer at this time.

Comments  
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.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy