Permutations and Combinations

  • Thread starter Crystal037
  • Start date
  • #1
Crystal037
161
5
Homework Statement:
In how many ways can 5 prizes be distributed among 4 boys when everybody can take any number of prizes.
Relevant Equations:
no. of prizes=5
no. of boys=4
the first boy has 6 ways,
either he wins 0 or 1 or 2 or 3 or 4 or 5 ways
According to the first boy, the second boy also has 0 or 1 or 2 or 3 or 4 or 5 chances
According to the first and second boy, the other boy also has 0 or 1 or 2 or 3 or 4 or 5 chances.
So, the answer should be 4(either of them gets all the prizes)+4C1*3C1(First gets 4 prizes and the second gets 1) +4C1*3C1(where First gets 3 prizes and the second gets 2)+4C2*2C1(2 of them gets 1 prize each and one gets only 3 prizes)+4C2*2C1(2 of them gets 2 prizes each and one gets only 1 prize)+4C1*3C3(where one gets 2 prizes and all the other get 1 each)
=4+12+12+12+12+4
=56
But the correct answer is 1024 ways.
 

Answers and Replies

  • #2
Stephen Tashi
Science Advisor
7,781
1,540
C1(First gets 4 prizes and the second gets 1)

Where do you account for the First boy getting 4 prizes and the third boy getting 1 prize?

It's simpler to think of each prize chosing a boy who gets it.
 
  • Like
Likes Delta2 and FactChecker
  • #3
Crystal037
161
5
Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth
 
  • #4
Stephen Tashi
Science Advisor
7,781
1,540
Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth

Yes, your are correct that it does, if you are not thinking of "the second" boy as being the name of one particular boy and thinking of all prizes as being identical.

Your calculation is treating the boys as being distinct, but treating the prizes as being indistinct.
For example , the partition of 5 into 3,1,1 can arise from:

Tom gets a car, a truck, and a boat, Ed gets a cat, Fred gets a dog
or
Tom gets a car, at truck, and a boat, Ed gets a dog and Fred gets a cat.

A factor 3C2 does not count those situations as being distinct. It only counts the selection of two distinct boys that receive 1 price each. It doesn't make a distinction in which prize they receive.
 
  • #5
FactChecker
Science Advisor
Homework Helper
Gold Member
7,596
3,320
It's simpler to think of each prize chosing a boy who gets it.
@Crystal037 , It's typical in these problems that the real trick is to find the approach that leads to the simplest counting of combinations. This hint is critical. Each prize can select between 4 people with no influence from the prior selections. Look at it that way and see what you get.
 
  • #6
Crystal037
161
5
Yes, your are correct that it does, if you are not thinking of "the second" boy as being the name of one particular boy and thinking of all prizes as being identical.

Your calculation is treating the boys as being distinct, but treating the prizes as being indistinct.
For example , the partition of 5 into 3,1,1 can arise from:

Tom gets a car, a truck, and a boat, Ed gets a cat, Fred gets a dog
or
Tom gets a car, at truck, and a boat, Ed gets a dog and Fred gets a cat.

A factor 3C2 does not count those situations as being distinct. It only counts the selection of two distinct boys that receive 1 price each. It doesn't make a distinction in which prize they receive.
But in the question it isn't written anywhere if the prizes are distinct or not
 
  • #7
Crystal037
161
5
@Crystal037 , It's typical in these problems that the real trick is to find the approach that leads to the simplest counting of combinations. This hint is critical. Each prize can select between 4 people with no influence from the prior selections. Look at it that way and see what you get.
I fif it that way and since each price have prize will have 4 ways so 5 prizes will have 4^5=1024 ways.
But can you please tell the faults or mistakes I made in the previous approach
 
  • #8
FactChecker
Science Advisor
Homework Helper
Gold Member
7,596
3,320
But in the question it isn't written anywhere if the prizes are distinct or not
That is true and a good reason to say that the problem statement is not very clear. If you make some reasonable assumptions, you can match their stated answer. That tells you what they really meant in the problem. Then you can make a better problem statement if you want.
 
  • #9
FactChecker
Science Advisor
Homework Helper
Gold Member
7,596
3,320
I fif it that way and since each price have prize will have 4 ways so 5 prizes will have 4^5=1024 ways.
But can you please tell the faults or mistakes I made in the previous approach
I looked at it initially and decided that your approach would be too complicated for me. I couldn't follow exactly what you were doing and I didn't see any mention at all of the 4th boy. I cannot comment on possible errors.

EDIT: I see that the 4'th boy is determined by the prior 3, so that is not an error in counting.
 
  • #10
Crystal037
161
5
Then if I take all the prizes not distinct then my answer would be correct? What changes then I would have to apply in the answer 4^5 to get the same for non-distinct prizes. Is it 4^5/5!
 
  • #11
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
Then if I take all the prizes not distinct then my answer would be correct? What changes then I would have to apply in the answer 4^5 to get the same for non-distinct prizes. Is it 4^5/5!
You can't just divide by 5! because if you permute the prizes you don't get different solutions. E.g.

If the first boy gets prizes A and B and the others one prize each, C, D and E, then that is one distinct solution. But, if you swap A and B you get the same distinct solution.

Your calculation assumes these are different distinct solutions.

There is, however, a neat general trick for dividing ##n## indistinguishable objects between ##k## people.

Hint: consider the n people as "boxes" into which any number of objects can be put. Imagine ##n -1## dividers between the boxes. Every solution is an arrangement of ##k## objects and ##n-1## dividers
 
  • #12
Crystal037
161
5
You can't just divide by 5! because if you permute the prizes you don't get different solutions. E.g.

If the first boy gets prizes A and B and the others one prize each, C, D and E, then that is one distinct solution. But, if you swap A and B you get the same distinct solution.

Your calculation assumes these are different distinct solutions.

There is, however, a neat general trick for dividing ##n## indistinguishable objects between ##k## people.

Hint: consider the n people as "boxes" into which any number of objects can be put. Imagine ##n -1## dividers between the boxes. Every solution is an arrangement of ##k## objects and ##n-1## dividers
But I am considering all the prizes to be same i.e A is same as B is same as C is same as D is same as E
 
  • #13
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
But I am considering all the prizes to be same i.e A is same as B is same as C is same as D is same as E

Yes, but you were dividing the number with distinct prizes by 5!. That's a mistake.
 
  • #14
Crystal037
161
5
Yes, but you were dividing the number with distinct prizes by 5!. That's a mistake.
So by what factor should I divide if I am not considering the prizes to be distinct
 
  • #15
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
So by what factor should I divide if I am not considering the prizes to be distinct

It doesn't work that way. The answers are 56 and 1024, which isn't a multiple of the fomer.

Your 56 is the correct answer and I think others have checked your working. But, I gave you more than a hint of a quick, general way to do these problems in post #11.
 
  • #16
Crystal037
161
5
How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11
 
  • #17
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11

Suppose you want to divide 5 objects into 3 boxes say. Then every solution looks something like:

XX | XX | X

That's two objects in the first box, two in the second and one in the third. There is a 1-1 correspondence therefore between solutions and arrangements of 5 X's and 3 |'s (dividers). And you may know how to count the numbver of such arrangements.
 
  • #18
Stephen Tashi
Science Advisor
7,781
1,540
I didn't understood what the word divider is supposed to mean in post 11

Imagine we have 5 blocks with the symbol "|" printed on them. We also have 5 blocks with the symbol "P" written on them. We arrange the blocks in a row with the condition that the first and last block in the row must have a "|" on it.

This produces patterns like:
|PPP|P||P|
That pattern can be matched to the situation:
First boy gets 3 prizes, Second boy gets 1 prize, Third boy gets zero prizes, Fourth boy gets 1 prize.

You can think of the symbol "|" as a physical wall or "divider". The dividers create 4 rooms.

Instead of thinking about dividing indistinguishable prizes among distinguishable boys, think about arranging the blocks in a row.

One way to think about arranging the blocks is to imagine starting with the arrangement
"| - - - - - - - -|" where the "-" represents a space that is to be filed by a single block.

An arrangement is determined by selecting 3 of the 8 places to put a block with a "|" and filling the rest of the spaces with blocks that have a "P". We can select 3 of the distinguishable 8 spaces in 8C3 = 56 ways.

You can finds lots of articles on the internet that discuss visualizing combinatorial problems in terms of "balls in cells" or "stars and bars". In my browsing today, I didn't find any that I liked as explanations! A typical summary of results is:
http://cns-web.bu.edu/~eric/EC500/attachments/ON(2d)LINE(20)READINGS/ballsinboxe.pdf
 
  • Like
Likes Crystal037 and PeroK
  • #19
Crystal037
161
5
So, the number of ways of distributing the prize
1) If the prizes are distinguishable:
no. of prizes, ways of choosing them WAYS OF ARRANGING THEM TOTAL
I II III IV
5 * 5C5 0 ------ 0 ----- 0 *4 4
4 * 5C4 1 *1C1 0 ----- 0 *4*3 60
3 * 5C3 1 *2C1 1 ------ 0 *4*3 240
3 * 5C3 2 ----- 0 ------ 0 *4*3 120
2 * 5C2 2 *3C2 1 ----- 0 *4*3 360
2 *5C2 1 *3C1 1 *2C1 1 *4 240
__________
1024
2) If the prizes were non-distinguishable:
then the combination factors will be divided, only arrangement factor will remain since the boys are still distinguishable.
4+ 12+12+12+12+4=56
 
  • #20
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
So, the number of ways of distributing the prize
1) If the prizes are distinguishable:
no. of prizes, ways of choosing them WAYS OF ARRANGING THEM TOTAL
I II III IV
5 * 5C5 0 ------ 0 ----- 0 *4 4
4 * 5C4 1 *1C1 0 ----- 0 *4*3 60
3 * 5C3 1 *2C1 1 ------ 0 *4*3 240
3 * 5C3 2 ----- 0 ------ 0 *4*3 120
2 * 5C2 2 *3C2 1 ----- 0 *4*3 360
2 *5C2 1 *3C1 1 *2C1 1 *4 240
__________
1024
2) If the prizes were non-distinguishable:
then the combination factors will be divided, only arrangement factor will remain since the boys are still distinguishable.
4+ 12+12+12+12+4=56

I would do:

For distinguishable prizes, each solution is defined by the boy who takes each prize. If we label the boys 1-4, then a typical solution is:

11431

Which means that the first, second and fifth prizes went to boy 1; the third prize to boy 4; and the fourth prize to boy 3.

This creates a 1-1 correspondence between solutions and five digit numbers composed of the digits 1-4.

And, there are ##4^5 = 1024## of those.

For the indistinguishable prizes I would do ##\binom{8}{3} = 56##, using the technique as described above.
 
  • #21
Crystal037
161
5
What do you mean a typical solution is 11431 and why did you take 8C3. There are no 8 prizes to choose 3 from. I did this to get 1024
IMG_20190916_191733.jpg
 
Last edited:
  • #22
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
What do you mean a typical solution is 11431?

11431

Which means that the first, second and fifth prizes went to boy 1; the third prize to boy 4; and the fourth prize to boy 3.
 
  • #23
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2022 Award
23,784
15,399
why did you take 8C3. There are no add prizes to choose 3 from

5 prizes, 4 boys, 3 dividers. Each solution is an arrangement of the prizes and dividers.
 

Suggested for: Permutations and Combinations

Replies
1
Views
272
Replies
1
Views
276
Replies
20
Views
854
Replies
3
Views
511
  • Last Post
Replies
1
Views
321
Replies
20
Views
3K
Replies
5
Views
946
Replies
1
Views
521
  • Last Post
Replies
9
Views
1K
Top