Simple Probability question's answer not matching given options...

[psi2lo]

Hi, the question I am stuck at is:

---

5 students are selected to participate in 3 different competitions such that at least one student participates in each competition. In how many different ways can all the students participate in the competitions, if no student participates in more than one competitions?

a. 90
b. 120
c. 150
d. 180

---

I think the answer should be 60 as 3 boxes to fill, and first can be filled in 5 ways, second in 4 ways and 3rd in 3 ways so 5*4*3 = 60 but that's not an option. What am I doing wrong?

 

[pka]

5 students are selected to participate in 3 different competitions such that at least one student participates in each competition. In how many different ways can all the students participate in the competitions, if no student participates in more than one competitions?
a. 90_____b. 120_____c. 150_____d. 180
I think the answer should be 60 as 3 boxes to fill, and first can be filled in 5 ways, second in 4 ways and 3rd in 3 ways so 5*4*3 = 60 but that's not an option. What am I doing wrong?

I don't know if that is a translation, but it is awkward English in any case.
The answer is listed. It is the number of surjections from a set of five to a set of three.
\(\displaystyle\sum\limits_{k = 0}^5 {{{( - 1)}^k}\dbinom{3}{k}{{(3 - k)}^3}}=~? \) SEE HERE

 

[Dr.Peterson]

Hi, the question I am stuck at is:

---

5 students are selected to participate in 3 different competitions such that at least one student participates in each competition. In how many different ways can all the students participate in the competitions, if no student participates in more than one competitions?

a. 90
b. 120
c. 150
d. 180

---

I think the answer should be 60 as 3 boxes to fill, and first can be filled in 5 ways, second in 4 ways and 3rd in 3 ways so 5*4*3 = 60 but that's not an option. What am I doing wrong?

You're finding the number of ways to assign one student to each competition, with none being in more than one. That is, you found the permutations of 5 taken 3 at a time. But each student has to participate in a competition (all are participating, none in more than one), and you have two not participating.

Rather than assigning a student to each competition, you might assign a competition to each student. Then you have to make sure that each is assigned to at least one student.

What specific techniques have you learned?

 

[Steven G]

Hi, the question I am stuck at is:

---

5 students are selected to participate in 3 different competitions such that at least one student participates in each competition. In how many different ways can all the students participate in the competitions, if no student participates in more than one competitions?

a. 90
b. 120
c. 150
d. 180

---

I think the answer should be 60 as 3 boxes to fill, and first can be filled in 5 ways, second in 4 ways and 3rd in 3 ways so 5*4*3 = 60 but that's not an option. What am I doing wrong?

at least one student participates in each competition
no student participates in more than one competitions
The two lines above when combined means that exactly one student participates in each competition. If there are 3 competition along with exactly one student per competition, there there is 0 ways for all five students to compete.

Please post the problem again.

 

[Dr.Peterson]

at least one student participates in each competition
no student participates in more than one competitions
The two lines above when combined means that exactly one student participates in each competition. If there are 3 competition along with exactly one student per competition, there there is 0 ways for all five students to compete.

Please post the problem again.

No, they imply that each student participates in exactly one competition. That's a different thing.

If A and B participate in competition 1, C and D in 2, and E in 3, then at least one student participates in each competition, and
no student participates in more than one competition. But there are two students in some competitions.

 

[Steven G]

No, they imply that each student participates in exactly one competition. That's a different thing.

If A and B participate in competition 1, C and D in 2, and E in 3, then at least one student participates in each competition, and
no student participates in more than one competition. But there are two students in some competitions.

OK, thank you. I see what you are saying.

 

[JeffM]

pka has given you a formula, and he is super in this field, but I cannot give a simple explanation for that formula (which contains a typo).

Here is a different way that may seem more intuitive to you.

There are three competitions.

How many ways can we allocate the five students to the three competitions so that each competition has at least 1 student.

3, 1, 1 or 2, 2, 1

In the first case, there are [MATH]\dbinom{3}{1}[/MATH] ways that we can select the competition with 3 students. For any of those ways, how many distinct ways can we assign students to the competition with three students?

[MATH]\dbinom{5}{3}[/MATH].

How many ways can we assign the remaining 2 students to the remaining 2 competitions?

Obviously [MATH]\dbinom{2}{1}.[/MATH].

So in the first case, we get [MATH]\dbinom{3}{1} * \dbinom{5}{3} * \dbinom{2}{1} = 3 * \dfrac{5!}{3! * 2!} * 2 = 60.[/MATH]
Can you figure out the second case?

EDIT: My method will get very tedious if there are many cases, and pka's formula is undoubtedly more computationally efficient than mine.

 

[pka]

Each student is assigned to one and only one of three competitions in such a way that none of the competitions is lacking at least on student. A surjection is a function that maps one set onto another. In this case we need surjection from a set of five (the students) to the set of three (the competitions) Counting the number of surjections we must employ the inclusion/exclusion principle.
The number of surjections from a set of \(m\) elements to a set of \(n\) elements is \(m>n~\displaystyle\text{Surj}(m,n)=\sum\limits_{k = 0}^n\ {{{( - 1)}^k}\binom{ n} { k} {{(n - k)}^m}} \)
Thus in this case \(\displaystyle\text{Surj}(5,3)=\sum\limits_{k = 0}^3\ {{{( - 1)}^k}\binom{ 3} { k} {{(3 - k)}^5}} \).

 

[Dr.Peterson]

Each student is assigned to one and only one of three competitions in such a way that none of the competitions is lacking at least one student. A surjection is a function that maps one set onto another. In this case we need surjection from a set of five (the students) to the set of three (the competitions) Counting the number of surjections we must employ the inclusion/exclusion principle.
The number of surjections from a set of \(m\) elements to a set of \(n\) elements is \(m>n~\displaystyle\text{Surj}(m,n)=\sum\limits_{k = 0}^n\ {{{( - 1)}^k}\binom{ n} { k} {{(n - k)}^m}} \)
Thus in this case \(\displaystyle\text{Surj}(5,3)=\sum\limits_{k = 0}^3\ {{{( - 1)}^k}\binom{ 3} { k} {{(3 - k)}^5}} \).

Let's think about what this means. It happens to be the same thing I suggested here, without mentioning inclusion-exclusion:

Rather than assigning a student to each competition, you might assign a competition to each student. Then you have to make sure that each is assigned to at least one student.

There are \(3^5\) ways to assign a competition to each student. But this includes those in which only two of the competitions are assigned; the number of ways to do this is \({3\choose 2}2^5\). So we subtract that; but that includes those in which only one competition is assigned, so we have to add that back on: \({3\choose 1}1^5\). So the correct count is \(3^5-{3\choose 2}2^5+{3\choose 1}1^5=243-96+3=150\). That, of course, is pka's formula.

 

[psi2lo]

I don't know if that is a translation, but it is awkward English in any case.
The answer is listed. It is the number of surjections from a set of five to a set of three.
\(\displaystyle\sum\limits_{k = 0}^5 {{{( - 1)}^k}\dbinom{3}{k}{{(3 - k)}^3}}=~? \) SEE HERE

Thank you @pka

The question isn't a translation, that's how questions are written here (please don't hate us for that).

I am doing my diploma and struggle with math, I can dedicate 4-5 hours daily, can you please suggest how I can get my math as lucid and strong as yours? I understand you are/were a professor, but I couldn't even think beyond P&C horizon, I know surjective and bijective function properties but I'd never have been able to think like you did - how can I train myself to think correctly?

 

[psi2lo]

Rather than assigning a student to each competition, you might assign a competition to each student. Then you have to make sure that each is assigned to at least one student.

@Dr.Peterson That's insightful, thanks; I understand said statement but I don't know how to apply it

I only know basic Permutation and Combination. After reading @pka's answer I also know function domain, range, and types (basic school math) but I can't see how those concepts found application here.

Also, what graph/scatter plot does your avatar image represent?

 

[psi2lo]

There are \(3^5\) ways to assign a competition to each student. But this includes those in which only two of the competitions are assigned; the number of ways to do this is \({3\choose 2}2^5\). So we subtract that; but that includes those in which only one competition is assigned, so we have to add that back on: \({3\choose 1}1^5\). So the correct count is \(3^5-{3\choose 2}2^5+{3\choose 1}1^5=243-96+3=150\). That, of course, is pka's formula.

Finally, I get it. I was stuck at 3^5 but I didn't know inclusion-exclusion principle.

 

[psi2lo]

Here is a different way that may seem more intuitive to you.

There are three competitions.

How many ways can we allocate the five students to the three competitions so that each competition has at least 1 student.

3, 1, 1 or 2, 2, 1

I'd like to explore this method also, but I don't understand 3,1,1 and 2,2,1 part

 

[Cubist]

I'd like to explore this method also, but I don't understand 3,1,1 and 2,2,1 part

3,1,1 means that three students are assigned to one competition, and one student to the other two competitions
2,2,1 means that two students are assigned to two competitions, and one student to the remaining competition (this is the case that @JeffM wanted you to consider)

 

[Dr.Peterson]

The question isn't a translation, that's how questions are written here (please don't hate us for that).

Combinatorics questions are often hard to state clearly. I wouldn't have said that yours looks like a translation, but it could have emphasized better what needs to be distinguished. On the other hand, part of the skill of combinatorics is to find the necessary information in a problem!

I am doing my diploma and struggle with math, I can dedicate 4-5 hours daily, can you please suggest how I can get my math as lucid and strong as yours? I understand you are/were a professor, but I couldn't even think beyond P&C horizon, I know surjective and bijective function properties but I'd never have been able to think like you did - how can I train myself to think correctly?

His ability comes from many years of experience, including both exposure to many techniques and formulas, and practice in applying them. Don't expect too much too fast, but do make the most of your time by thinking about each problem you do (unless they are repetitive), to see what you can learn from it before you move on to the next. Often, especially in combinatorics, you can try to find a second way (sometimes inspired by the result) in order to broaden your experience.

Finally, I get it. I was stuck at 3^5 but I didn't know inclusion-exclusion principle.

This is the "exposure" part! If you don't know it, then you don't know it ... yet! You'll get there.

On the other hand, this is exactly why, after giving a very general hint, I asked you:

What specific techniques have you learned?

The reason you were given answers you couldn't understand is that you hadn't told us at what level we should answer. Even now, I'm not sure what method you might be expected to use based on whatever you have learned.

This is also why, after pka gave a good answer that assumes you know a particular formula, and then another that assumes you know inclusion-exclusion, I followed up with a more basic explanation of the same thing without that assumption.

There are some relevant ideas here:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to help...

www.freemathhelp.com

EDIT:

Also, what graph/scatter plot does your avatar image represent?

That's a cardioid. Look it up.

 

[JeffM]

@Dr.Peterson That's insightful, thanks; I understand said statement but I don't know how to apply it

I only know basic Permutation and Combination. After reading @pka's answer I also know function domain, range, and types (basic school math) but I can't see how those concepts found application here.

This was ONE reason why I pointed out another method. We teach a very rapid introduction to combinatorics in high school, and solutions that go beyond the formulas stressed in that rapid introduction may seem like magic rather than math.

The OTHER reason why I pointed out another method is that what is truly important in math is orderly and systematic thinking rather than memorizing formulas. Never memorize a formula unless you know why it works, or else you will not know when using the formula is appropriate. In fact, I only memorize those fornulas that I use often and that I can recreate from first principles. This is exactly why pka talked about the inclusion-exclusion principle: he deeply understands the first principles of combinatorics and so knows what formulas to use under what circumstances.

So going back to the method I suggested, I first asked myself how many ways can I assign 5 students to 3 competitions such that at least 1 student is assigned to each competition. I answered that question this way. Assign three different students to three different competitions. That ensures each competition has at least one student. But that leaves two students not yet assigned. When I assign one of those two then one competition will have 2 students assigned. At this point, I have a choice. I can assign the two remaining students to the same competition or to different competitions. If I assign both to the same competition, that results in one competition having 3 students assigned, a second competition with 1 student assigned, and a third competition with 1 student assigned. Alternatively, if I assign the remaining two students, to different competition, that results in two competitions with two students assigned and one competition with a lone competitor.

I abbreviated that answer as 3-1-1 or 2-2-1. Those are the only possible tripletons of positive whole numbers that add up to five. I sincerely apologize if that logic was too abbreviated in my initial post. But it was simply disciplined common sense, which is 90% of math.

I have now broken the original problem down into two simpler problems, a very common trick in math (and life generally).

These simpler problems can be attacked with the tools provided in high school combinatorics.

I showed how to do one. Can you do the other?