more of a general question.....
-
It often occurred to me that when tackling a combinatorics problem, I don't know if I am going to use multiplication or factorial. Could y'all give me some tips on how to know which method is the right one to choose? Thanks as always.
-
Professor Loh is the best mathematician and teacher
-
@aaronhma those are good links
@victorioussheep For me, the best way to think about it isn't about whether it's multiplication or a factorial, but rather just what you're counting.
For example, how many ways are there to seat 5 students in a row of 5 chairs?
Well, there's 5 chairs available for the first student to pick, 4 chairs left for the second student to pick, 3 for the third, and so on. The total amount of ways is going to be \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\). It just so happens that this is exactly \(5!\) (i mean \(5\) factorial, not a really enthusiastic 5)
What about if we wanted to seat 5 students in 7 chairs this time?
Well, there's 7 chairs for the first student to pick, 6 chairs left for the second student, 5 for the third, 4 for the fourth, and 3 for the last student to pick. Multiplying these together, that's \(7 \cdot 6 \cdot 5 \cdot 4 \cdot 3\), which ISN'T a factorial.
So, the best way of dealing with combo problems is to just keep in mind what you're trying to find out. Once you figure out what you need to multiply together, you will have the answer!Also, keep in mind that a factorial is just a way to express multiplying numbers together. It's not really multiplication OR factorial, because a factorial is already multiplication. \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\). Does that make sense?
One last example: let's say I have 2 red apple and 2 green apples, and you can't tell the red apples apart from each other. Same with the green. How many ways are there for me to arrange them in a line?
It might be tempting to do the same thing we have always done: there's 4 spots for the first apple, 3 for the second, 2 for the third, and 1 left for the last apple, so \(4 \cdot 3 \cdot 2 \cdot1\), right?
Well, it's a great start. The problem with doing that is, includes arrangements like these two:
R = red apple G = green apple
R R G G
R R G G
It might not look like it, but the green apples are swapped in the second one! That's exactly the problem: they are the exact same arrangement, but we counted them as two separate ones. And actually, every arrangement has this problem. We shouldn't count the second version of the same thing. So let's take the number we got earlier and divide by \(2\).So we have \(\frac{4 \cdot 3 \cdot 2 \cdot1}{2}\). But wait, the red apples have the same problem! We also double counted each red apple arrangement, so we need to divide by \(2\) again.
This finally gives us \(\frac{4 \cdot 3 \cdot 2 \cdot1}{2\cdot2}=6\) ways.
Counting is really just a bunch of multiplication and division. Notice how I could also express the same thing as \(\frac{4!}{2\cdot2}\). So, focus on figuring out what you need to count for the problem. Try not to think of the problems as multiplication vs factorial. Just count what you need to count, that's what combo is about! -
@quacker88
Thanks for the explanation and the examples! Although I still have a question to ask, take a look at this question:
(assume T= 2)In this question, I should use (4+3+2)! to count how many ways there are to arrange the fruits, however, I also need to divide the 9! with 234, right? because just like what you've said in the last examples, the oranges all look alike, and so do the apples and bananas.
-
@aaronhma thanks for the links, I will take a look at them right now!
-
@victorioussheep Yeah you're exactly right! But make sure you're dividing by \(2!, 3!,\) and \(4!\). If you need an explanation, try thinking about this:
To make the numbers easier let's say we have 3 bananas and 2 apples.
One valid arrangement would be B B B A A.
But, how many ways are there for me to arrange the bananas in the places they are right now? Technically \(3\cdot2\cdot1=3!=6\), but these \(6\) arrangements all look the exact same to us. So whenever we count, we have divide out the amount of times we overcounted. Here we would divide by \(6\).So for the problem you posted, the answer would be \(\frac{9!}{2!\cdot3!\cdot4!}\).
-
@quacker88 thanks again for taking your time to help answer my question! What I don't understand is how do you know it is 2! * 3! * 4!, and not 2* 3* 4?
Also, in the problem I posted above(assume T=2), do you think I can use the method "# choose #" to answer this question? (I am not exactly sure....)
-
@victorioussheep Think of each of them individually. This might make things more confusing, but let's take a look at the bananas. Also, let's number the bananas. We still can't tell the difference between each banana, but I'm numbering them so we can see what happens when we switch them around.
So one way to organize the fruits is A A O O O B1 B2 B3 B4.
Another way is A A O O O B2 B1 B3 B4. See how I swapped banana #1 and banana #2?But here's the thing-- those two arrangements look the exact same to us!
A A O O O B1 B2 B4 B3 also looks the exact same. They all look like A A O O O B B B B. When we use \(9!\), we're counting those arrangements as if they were completely separate arrangements, when we should only count them as one.So, how many ways are there to reorganize the bananas in the places they are right now? Well, \(4\cdot3\cdot2\cdot1=4!=24\).
Every arrangement that looks the same to us is actually counted 24 times. So, we have to divide \(9!\) by \(24\).That takes care of only the bananas. Let's do the same thing with the oranges. It also might be easier to visualize since the numbers are smaller. Again, let's look at the oranges on their own and give them numbers.
A A O1 O2 O3 B B B B is one possible arrangement. To us, it looks like A A O O O B B B B.
But wait, how many arrangements are there that look like that?A A O1 O2 O3 B B B B
A A O1 O3 O2 B B B B
A A O2 O1 O3 B B B B
A A O2 O3 O1 B B B B
A A O3 O1 O2 B B B B
A A O3 O2 O1 B B B BAll \(6\) of these look the exact same to us! Where did \(6\) come from? Well, we're basically rearranging the oranges in the places that they are right now. There's \(3\) places to put the first orange, \(2\) for the second, and \(1\) for the last one, so that's \(3\cdot2\cdot1=3!=6\) arrangements. Every arrangement has been counted \(6\) times, so we need to divide by \(6\) to only have them be counted once.
And doing the same thing with the apples, you'll get that every arrangement is counted \(2!=2\) times.
Dividing everything together will give us the expression that gives the answer.
I might've made things more confusing, but I hope this helps. Let me know if you have more questions
-
@quacker88
oh no your explanation is perfect! I now understand why the fruits need to divide the 9! with 2! * 3!* 4! now - b/c they are counted more than once! thank you quacker88 again for answering my question! -
@victorioussheep Glad that you understood everything
