Permutations (1 Viewer)

[Ekman]

I know this question has been repeated a couple of times, but this one is somewhat different:

In how many ways can 10 identical coins be allocated to 4 different boxes if no box will be left empty.

I say there are 9!/6!=504 possible arrangements. Can anyone confirm this?

 

[VBN2470]

I know this question has been repeated a couple of times, but this one is somewhat different:

In how many ways can 10 identical coins be allocated to 4 different boxes if no box will be left empty.

I say there are 9!/6!=504 possible arrangements. Can anyone confirm this?

I think you forgot to divide your expression by 3!, since your separators are assumed to be identical, so the answer should just be .
Also, I got 286 number of ways you can arrange the coins such that there is NO restriction, so 504 which is double 286 wouldn't really make sense

 

[Ekman]

I know this question has been repeated a couple of times, but this one is somewhat different:

In how many ways can 10 identical coins be allocated to 4 different boxes if no box will be left empty.

I say there are 9!/6!=504 possible arrangements. Can anyone confirm this?

No need for assuming that they are identical when the question specifically says that they are different. I can understand as to why you would divide by 3! when the boxes are identical, however the question stated that the boxes are differentiable...

 

[braintic]

The answer is 9C3.
Not sure at the moment what it would be if the boxes were identical, but definitely not 9P3 - it has to be LESS than 9C3.

 

[Ekman]

The answer is 9C3.
Not sure at the moment what it would be if the boxes were identical, but definitely not 9P3 - it has to be LESS than 9C3.

Could you please explain the logic behind it?

 

[BLIT2014]

Could you please explain the logic behind it?

Its a combination question as we don't care about the order of the coins.

 

[Ekman]

Its a combination question as we don't care about the order of the coins.

Yes I understood that but whats the logic behind 9C3?

 

[photastic]

Yes I understood that but whats the logic behind 9C3?

There are 9 objects to choose from but you only pick 3 of them since there is only 1 way to choose the first coin, hence its not 10 objects and you choose 4.

 

[braintic]

Yes I understood that but whats the logic behind 9C3?

Toss a coin into each box, as each box must have at least one coin.
That leaves 6 coins to distribute amongst 4 boxes, where we are now free to place no coins in a box.

Place the 6 coins in a line, and place 3 dividers somewhere in the line. Possibilities are:

00|00|0|0 meaning the first 2 boxes get 2 coins each and the last 2 boxes get 1 coin each

||000000| meaning the first 2 boxes get no coins, the 3rd box gets 6 coins, and the last box gets no coins.

Provided you've decided beforehand which specific box is first, second, third and fourth, this accounts for distinct boxes.

There are 9 positions in the line, from which we need to choose three for the dividers, hence 9C3.
Alternatively, we are forming a 'word' from six 0's and three |'s, hence 9!/(6!3!) = 9C3 different words.

 

[VBN2470]

Yes I understood that but whats the logic behind 9C3?

Let me try to explain this a bit intuitively..

Since we have 10 identical coins, it doesn't matter how they are arranged as this will only give the same arrangement. So we only care about how they are distributed amongst the boxes. We can think of the coins being arranged in a row, and consequently insert so called separators (or dividers) between the coins, so that they are 'split' as they are arranged. For example, you may have C C C C | C C C | C C | C representing a line of coins with identical separators inserted in the 5th, 8th and 10th gap positions (where there exists 11 gaps between the coins from left to right). This arrangement is analogous to 4 coins in the first box, 3 in the second, 2 in the third and 1 in the last box respectively. However, since restriction is that no box must empty, we only consider the 9 'inner gaps', eliminating the two end ones -> since this can yield an arrangement | C C | C C C C C C | C C which represents coins being distributed amongst 3 boxes and not 4, something we don't want. Since we are only interested in 9 positions where the separators can be inserted, our total number of ways of selecting 3 of these gaps is 9C3 = 84.

 

[Drsoccerball]

what do you do if the coins are different

 

[photastic]

what do you do if the coins are different

Then the first choice will matter, hence 10C4, correct me if i'm wrong.

 

[Ekman]

How about if the boxes were identical?

 

[VBN2470]

what do you do if the coins are different

Then the first choice will matter, hence 10C4, correct me if i'm wrong.

If the coins are different then we will have to find all arrangements of the coins too, which would be 10!. Thus, the total number of ways would then be 9C3*10! = 304819200.

 

[Ekman]

One other question that im confused about is:
There are 4 trigonometry questions and 5 probability questions. A Teacher is to select 3 questions for the exam. How many possible set of questions can be made if at least 1 trigonometry and 1 probability question is used.

Why is doing 4C1 x 5C1 x 7C1 wrong?

 

[VBN2470]

Is it (1) AT LEAST one trigonometry question and STRICTLY ONE probability question or (2) AT LEAST one of each?

If it is the first case, then you would do 4C2 X 5C1 = 6 X 5 = 30.

If it was the second case, you would do (4C2 X 5C1) + (4C1 X 5C2) = 30 + 40 = 70.

 

[Ekman]

Its the second case. But I was wondering why my method didn't work out?

I did 4C1 x 5C1 x 7C1 = 140 different ways. My logic was that you choose 1 trigo and you choose 1 probability and with the remaining 7 questions you choose 1 more (Since you don't care if the 3rd question is trigo or probability) btw questions are differentiable and the question does ask for "different sets of questions"...

 

[VBN2470]

Its the second case. But I was wondering why my method didn't work out?

I did 4C1 x 5C1 x 7C1 = 140 different ways. My logic was that you choose 1 trigo and you choose 1 probability and with the remaining 7 questions you choose 1 more (Since you don't care if the 3rd question is trigo or probability) btw questions are differentiable and the question does ask for "different sets of questions"...

It is because you will start to double count the combinations i.e. there will exist pairs of combinations which are exactly the same. So for instance, you may have P1, T1, P2, then somewhere else you will have P2, T1, P1 which is just a permutation of the first set (try some examples for yourself with smaller numbers). Because of this double counting, you will find 70 pairs of the same combination, so you will actually have to halve your result to avoid the redundancy. If I pick P1 and T1 as my questions, then P2 is one option I can pick from the bag (to get P1, T1, P2) BUT if I pick P2 and T1 as my first questions, then P1 can also be picked from the 7 remaining questions (to get P2, T1, P2 which is the same as before), so the process kind of becomes 'cyclic' and repeats itself to get another arrangement of the same combination. However, with the way I did, you strictly consider the cases and this avoids the double count, so it works out much neatly than having to worry about repetitions.

That is my understanding of it, I probably didn't explain it too well and I'm sure someone else can explain it in a much simpler and mathematical way.

 

[braintic]

If the coins are different then we will have to find all arrangements of the coins too, which would be 10!. Thus, the total number of ways would then be 9C3*10! = 304819200.

Then the first choice will matter, hence 10C4, correct me if i'm wrong.

Nup, there are no factorials or perms/combs here. If the coins and the boxes are both distinguishable, then each coin has 4 possibilities, each leading to a different result. So the number of cases if we allow a box to be empty is 4¹⁰.

If we want at least one coin in each box, we have to subtract cases from this. I am getting 4¹⁰ - 4×3¹⁰ + 6×2¹⁰ - 8. But I'm not too sure about this and am prepared for a correction.

How about if the boxes were identical?

If the coins and the boxes are both indistinguishable, I get 9 cases by direct counting. I'm not sure what method to use for larger numbers - perhaps someone might like to offer a suggestion.


I have absolutely no idea what to do for distinguishable coins and indistinguishable boxes.

 

[InteGrand]

The problem of how to place balls into boxes under certain rules (e.g. boxes are indistinguishable, there must be at least one ball in each box, etc) and formulae form part of the 'twelvefold way': http://en.wikipedia.org/wiki/Twelvefold_way (it's actually not about balls and boxes, but can be visualised like that; see this part for that: http://en.wikipedia.org/wiki/Twelvefold_way#Balls_and_boxes ).