• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Permutations and Combinations

  • Thread starter Crystal037
  • Start date
63
1
Homework Statement
In how many ways can 5 prizes be distributed among 4 boys when everybody can take any number of prizes.
Homework 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.
 

Stephen Tashi

Science Advisor
6,730
1,084
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.
 
63
1
Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth
 

Stephen Tashi

Science Advisor
6,730
1,084
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.
 

FactChecker

Science Advisor
Gold Member
2018 Award
5,086
1,790
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.
 
63
1
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
 
63
1
@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
 

FactChecker

Science Advisor
Gold Member
2018 Award
5,086
1,790
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.
 

FactChecker

Science Advisor
Gold Member
2018 Award
5,086
1,790
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.
 
63
1
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!
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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
 
63
1
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
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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.
 
63
1
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
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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.
 
63
1
How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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.
 

Stephen Tashi

Science Advisor
6,730
1,084
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:
 
63
1
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
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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.
 
63
1
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:

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,857
3,674
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.
 

Want to reply to this thread?

"Permutations and Combinations" You must log in or register to reply here.

Related Threads for: Permutations and Combinations

  • Posted
Replies
12
Views
2K
  • Posted
Replies
6
Views
2K
  • Posted
Replies
3
Views
1K
  • Posted
Replies
1
Views
2K
  • Posted
Replies
6
Views
1K
  • Posted
Replies
11
Views
2K
  • Posted
Replies
7
Views
2K
  • Posted
Replies
6
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top