[Discrete Mathematics] Permutation Practice
ฝัง
- เผยแพร่เมื่อ 7 ธ.ค. 2014
- In this video we take a look at permutation practice questions, including circular tables.
Visit our website: bit.ly/1zBPlvm
Subscribe on TH-cam: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVg
Like us on Facebook: on. 1vWwDRc
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.
For those of you with a discrete math test tomorrow...I salute you
Friday :( I gonna fail
I am having test 2 weeks later and most of what he teaches wont appear in it, but counting samples with some complex condition always trip me up
@@nitsuj1001 did u fail
@@xdman20005 Yes xD next year ^^
I have it tomorrow haha
For the male/female problem, it's easier to think of it as (6x3x2x2x1x1) / 6 = 12. The first person could be either male or female, so 6 possible. then person 2 is the opposite so 3 possible, third person is first gender again so 2, then so on.
Then you can just divide the order by 6.
you got talent, buddy
For the same question, I think you can think as having three pairs. we always have three distinct pairs sitting around the table. number of possible arrangement of pairs / number of pairs.
Yeah nice. I like to think of it as 3! * 3! / 6 . As in 3! ways to seat males, 3! factorial ways to seat females divided by 6 you get the same answer
@@Alex-wx8be except you don't... lol
@@Alex-wx8be That's what I thought at first, but this answer is not correct because 3! * 3! = 36, and 36 divided by 6 is 6, not 12.
How I understand 7:10 as a series of choices.
We have a table with positions 1 through 6.
Position 1 is the initial position.
1) First we have to make a choice, wether the person at position 1 is Male(M) or Female(F). [2] possible ways.
2) then we have to choose from 3 people of the choosen sex for position 1. [3] possible ways.
3) next we make a choice between 3 people of the opposite sex. [3]
4) then we choose from 2 different people with the same sex as position 1. [2] possible ways.
5) [2] possible ways
6) [1]
7)and for the final position we are left with one choice again [1].
So 2 x 3 x 3 x 2 x 2 x 1 x 1 = 72 "different ways".
If we take any arrangement of people and shift them by one position clockwise (or counter clockwise), we are left with a different arrangement which is basically the same as the initial. If we shift again clockwise we get another distinct arrangement which is again the same as the initial. That can be done for up to 6 times.
That means that the 72 "different ways" are made up of groups, and each group contains 6 different arrangements that are essentially the same thing.
The number of those groups of 6 is 72/6 = 12.
12 groups that each group contains 6 different representations of the same thing.
Therefore we can arrange 3 men and 3 women in a circular table where a man sits adjacent to 2 women and vice versa in 12 ways.
P.S. I don't know if I helped with that or actually made things even more complicated but this is how I intuitively understand it. Sorry for my bad English.
These videos are fantastic! keep up the splendid work.
Great explanation! I really enjoyed your video. Thanks!
this concept has not been easy for me since a long time but after seeing this video all my concepts are clear...thank you so much sir
My man, you flashed my brain out after the first question😮, but the second question didn't leave a single doubt in my brain.
In the last question we have 7 places out of which 1st place can be filled in 4 ways because we have 5, 5, 6, 7 which will give us a number greater than 5 million. Now, we are left with 6 places and 6 numbers which can be filled in 6! ways. So, the answer is (4*6!)/2!2! which is equivalent to 6! . This is just another way of doing it
How do i get better with the intuition part? Im learning mostly through textbooks and your discrete math videos but i still dont feel confident with these types of questions.
For the table with opposite sex thing, what I've did is:
1) Anchor position can be anybody (6 possibility)
2) I put all the other permutation together (6x3x2x2x1x1)
3) Then I divide by 6 to take the anchor position into account
I come to the right answer, and I think it just makes more sense that way
I did the same more or less, i wrote 2 x 3x3x2x2x1x1 /6
I think we can consider the circular arrangment as following:In Arrangment order is important. When we think of a round table , there is no order at the Beginning because let say there are 4 chairs and 4 people , First person can seat on any of these 4 . But no matter on which chair he seat , he will always see that , there is one chair on left , one on right and one infront. So we can say that order is not defined at this stage because if it's the case of a simple straight arrangements the first place is always at the left most unlike circular, so no matter on which chair he seat all options are same so 1 way. Now once he takes his place for the second person each seat will be different in order and so on for all remaining. Hence here we can apply factorial. Hope I'm right. Please correct me if I'm wrong. Thank you
You are best sir!
Thanks for making this video’s🙌👍✌️😊
do you know a book with examples and quizzes Counting, Permutations and Combinations
The text book hurt my head when they tried to writeup how to do this similar example. Thank you .
Great video! Kalid Azad from Better Explained may have other good ideas for illustrating the round-table problem
For the 3 men and 3 women example I came up with a way to find the same answer of 12 ways in which I said 3! x 3! /3 which gives 36/3 = 12 ways. My reasoning emanates from the first example where we used 6!/6 to get 5! which is equal to 120 ways. I did not test my reasoning with different problems but in this case it seems to work
For the 3 men and 3 women at the round table, you need to add a little more information to the question. If you consider which direction you go around the table to be important, CW and CCW versions of the same arrangement are different, but if you do not care who is setting left or right of who, only who is adjacent to who, you only have 6 unique arrangements.
Awesome videos
For the 3 men and 3 women sitting alternately around a circle. One intuition could be that one gender is a circular list and another a straight list. Then apply the rules of circular list followed by straight list.
You're actually really funny
3 men and 3 women could be explained with the same approached you did for the example 1 but instead, 5! you would have said 2! x 3!.
Thanks a lot for the awesome videos.
Any advice on how to determine when something is a permutation versus when it is a combination?
If order matters, then it is a permutation. If order doesn't matter, then it is a combination.
For the last problem I did (4 x 6!) / (2! x 2!). 4 possibilities for the first integer (5, 5, 6, 7) divided by factorials for every duplicate which is (4, 4, 5, 5). Got the same answer but I'm not sure if I got the right formula given different variables.
For the table example you could also put it as 3! for the men and 3! for the woman so you get 3!3! and then divide by 3 to set one as an anchor and you get 3!3!/3 = (3)2!3!/3, cancel out the 3's and you get 3!2! = (3)(2)(1)(2)(1) = 12
For man-woman problem, I think it is easier to think in the following way.
Consider M1 W1, M2 W2 and M3 W3 to be one pair each. How many ways can you arrange?
-> 3!
But since each pair has two people, they could also switch positions, so
-> 2!
Finally, 3! X 2! = 3X2X1X2X1 = 12.
Really enjoyed the comedy part around the 10 min mark..Would watch again:p
For the last question, since there are 2 5's do you not have to do an additional case for the second 5 as well?
+Omar Crosby No, because it doesn't matter which 5 comes first. They're both 5.
+TheTrevTutor Alright, I was just confused because I thought that you might index both of the 5's and then fix one of them to be the first digit and find how many ways you can rearrange the remaining 6 digits, and then do the same thing for the second 5.
@@Trevtutor I also have a doubt about the last question,
So what I did, was:
our number is going to be greater than 5,000,000, so
for first place we can choose 4 possible cases - 5, 5, 6, 7
for the rest of the places there is no difference
and also there are 2 times 5 and 2 times 4 so we have to divide it by 2! x 2!
so it looks like this:
(4 x 6 x 5 x 4 x 3 x 2 x 1) / 2! x 2!
it is cancelling out and the final result is:
6 x 5 x 4 x 3 x 2 x 1 = 6!
So the answer is the same, but I am not sure that my solution is correct
@@_JupiterThePlanet_ correct
Hi, quick question about the second problem. Why are we dividing by 2! for duplicates?
because some numbers are repeated twice.
THANK YOU HERO
for the last example i did (4x6!)/(2!2!). My reasoning was that there were four options to choose from for the first digit and then the rest was just adjusted accordingly for however many were remaining. was it lucky that it worked out to be the same answer or is this valid? i wasn't sure cause i didn't take into account the lack of repetition for 5 if it were selected first..
I did the same thing is this right or an error?
@@SARCASMOOO That's the way I did it!
It does, actually; the repetition of the 5 is expressed in the first 2! in the denominator, and the repetition of the 4 is the second 2!. Considering the total # of choices and dividing by the repetitions, what he had done for several other problems, is essentially what we did here.
The last one is confusing. Are the answers case specific? or 6! for all three cases?
I have a permutation problem
How many positive integer solutions does the equation a + b + c = 100 have if we require a < b < c?
This is a combination problem.
I suppose this method is only effective with two different factors (M,W), but the way I approached it was to think of two scenarios, one where the man sits first and the woman sits first. Both of those yields 3!^2 so 36 scenarios for man sitting first and 36 scenarios for woman sitting at anchor chair. Then I added them to get 72 and divided by 6 because it is a round table and it could have 6 different rotations.
great video, very helpful!!
in the last question how can we just assume that the firs number is 5? dont we need to do some sort of permutation like "2 choose 1" for the 5, before we move on to arranging the remaining 6 integers
If I told you to make a 10 letter word that starts with the letter 'a', it's the same as making a 9 letter word and then just sticking an 'a' on the front. We just grab one of the 5s, put it at the front, and then sort the remaining numbers afterwards.
got it, thank you!
Is this what you also meant with the circular table when you said "anker" for the first. We use it to fix the first and then take a look at the opposite sex and so on. (A=1)x3x2x2x1x1 Thanks
@@Trevtutor whats up with the anchor situation that went over my head like an airplane pls senpai help
You can even do it like this (F and M circle problem):
First we think in a row. We have six spaces:
____ ____ ____ ____ ____ ____
We take M in the first place so we have:
_ 3 _ _ 3 _ _ 2 _ _ 2 _ _ 1 _ _ 1 _ = 3*3*2*2*1*1 = 3!3! = 32
M F M F M F
Then we take F in the first place so we have:
_ 3 _ _ 3 _ _ 2 _ _ 2 _ _ 1 _ _ 1 _ = 3*3*2*2*1*1 = 3!3! = 32
F M F M F M
Now we use the rule of sum:
The way we can sit alternating F and M in a row of 6 chairs = The case where M first + The case were F first = (3*3*2*2*1*1) + (3*3*2*2*1*1) = 3!3! +3!3! = 2(3!3!)
Since we are in the circle we divide what we got in the row with 6 (because we have six chairs), so:
2(3!3!)/6 = (3!3!)/3 = 36/3 = 12
which is the desired answer.
In the problem of finding integers that exceed 5 million,wouldn't there be a way of choosing two 5's as well?
No because choosing any of the 5 will result the same and that would be redundant
@14:24 Why is the answer not 4*6!/(2!*2!) 4 because there are 4 integers you can have that will be greater than 5 million and then 6! for the rest of your choices divided by 4 to remove duplicates?
Professor Trev, excellent video, any thoughts on how I could understand the last question a little more?
We have 7 digits, 3445567, and we want to count the number of ways that the 7 digits are greater than 5,000,000. So, for example, 5,543,467.
To do this, we can either have the first digit be a 5, a 6, or a 7.
Case 1) It's a 5. Then we have 344567 remaining. And we can order them 6!/2! ways (because of repeating 4's).
Case 2). It's a 6. Then we have 344557 remaining. And we can order them 6!/(2!2!) ways (because of repeating 4's and 5's).
Case 3) It's a 7. Then we have 344556 remaining. 6!/(2!2!) ways.
So we add all the cases up, and simplify.
Thanks
Hey Trev, in Case 1, where you have a 5 to start the number, wouldn't the second 5 in the second position cause a duplicate between the two 5's (they'd be interchangeable). To account for that, would we subtract one permutation?
by designating a position A, or anchor position aren't you imposing an order on the distribution?
+Bradley Shepard Well, there is an order. It's a permutation so there should be some ordering of people around a table. If we used combinations, then order wouldn't matter and there would only be 1 way to choose 6 people to sit around a 6 person table.
Awesome stuff! Why do we divide by 6? (in the first example). How did we reach 6?
If all people seated around the table shifted by 1 seat, the order will still remain the same. Hence, since there are 6 people and 6 seats, they can shift 6 times but the order would still remain the same. So, we divided by 6 to make sure we get a different order each time.
i have barely gone to my discrete math lectures and I'm tryna learn this by tomorrow but I think the last one is wrong. if you want the number to exceed 5,000,000 then only 4 numbers can be in the first slot, and then 6 remaining for the 2nd slot, 5 remaining for the 3rd slot, and so on. So the equation to solve it would be 4 x 6 x 5 x 4 x 3 x 2 x 1.
I feel like this is something that you are either good at or you are either not good at
"... even though ... you could probably just google the answer, you happened to be there and ... Construct a situation in your head where that was a joke. Okay." haahaha!
I have a question about permutations: : Let n ≥ 4 be an integer. Determine the number of permutations of {1, 2, . . . , n},
in which
• 1 and 2 are next to each other, with 1 to the left of 2, or
• 4 and 3 are next to each other, with 4 to the left of 3.
How do I do this?
Treat (12) as a unit or (34) as a unit, then permute as normal.
Did I get lucky just assuming that the first position had four options, then 6! after for the rest, then dividing by 2! twice for the two repetitions? Because I got the same answer....
you a maths baller
at 4:58, why isn't it divide by 3! instead of 3? Are you suggesting that as long as the sexes alternates, individual is not of our concern??
in the table with opposite sex thing, why isn't the way for making it pair wise not multiplied by 2?? because it can be either as MFMFMF or FMFMFM
+Abhishek Tiwari We account for that by ignoring which is placed first (using an anchor) and use the notion of opposite/sameness to decide how many seats we can have.
You could separate it into those two cases if you want, but then you have two results you have to add together (which is slightly more complicated)
Yoo so iv been watching these videos and im wondering if discrete structures is the same thing. Like my classes will begin next semester and I thought id get a head start. So does anyone know if its relatively the same thing?
Usama Nadeem I’m in discrete structures at UCF and this is the stuff we’re doing. Unfortunately our prof likes to take these concepts and twist them so it’s not as straightforward as the examples Trev gives.
@@codyhenry1530 Yeh im taking it rn. My class is definitely easier than these discrete mathematics videos. This was very helpful as this made the class a lot easier. Good luck and thanks for the help :)
What is the answer for the table question, if rotations are ignored ?
Then you wouldn't divide by the amount of possible rotations.
For the last q. My soln. :
First: Calculate all possible event set=7!/2!/2!.
Second: Subtract the case where 3 is the first number= 6!/2!/2!
Third: Subtract the case where 4 is the first number= 6!/2!.
As a result=7!/2!/2! - 6!/2!/2! - 6!/2! = 4*6!/2!/2!.
For the numbers question, couldn't you simply account for the first value to be anything greater than 5 (so 4 possibilities) times 6! (for the rest of the numbers) divided by 2!*2! (for the 4 and the 5 repeating)? That still comes down to 6!.
(4*6!)/(2*2!) = 6!
+Mohna Zaidi As long as the numerical answer in the end is the same, the method probably (sometimes it's fluke!) works. I split it by cases to show a more intuitive approach. But if we were dealing with a lot more numbers, your approach would be more easily computed by hand.
How to figure out if the question is premutations or a combinatio or just i should use the sum rule or product rule 🤔
you'd work out permutations when the order matters and work out combinations when the order doesnt matter
Veronica thnx
I think of the circular table / man women problem like this: Pick an anchor, and they won't move (say the top man). Then the 3 women can be arranged in 3! ways in their spots relative to him, likewise the two men can be put in 2! of the other spots. Now combining the permutations of the two situations gives 3! * 2! = 12
Rule of Product:
Step 1: Determine which gender to seat first: 2! ways to do so
Step 2: Seat pairs: 3! ways to do so
Step 3: Multiply 3!2!=12
a shelf contains 7 books bound in red and 5 bound in blue and 3 in green. In how many different orders can they be arranged if all the books of the same color must be kept together? can someone help me?
+jhon jayson dexter barbosa How many ways can you arrange 7 red books? How many ways can you arrange 5 blue books? How many ways can you arrange 3 green books? How many ways can you arrange 3 colors?
Multiply those all together. It's the rule of product.
This is how I would do:
1) assume all the red books as 1unit, all blue books are 1 unit and all green books are 1 unit. so you have 3 units. 3 units , 3 places so they can be arranged in 3! ways.
2) 7 red books can be arranged within themselves in 7! ways.
3) 5 blue books can be arranged within themselves in 5! ways
4) 3 green books can be arranged within themselves in 3! ways
5) so the total arrangement would be 3!x7!x5!x3!
At 2:20, why isn't the number of ways 6 + 5! ? My reasoning is that there are 6 ways of choosing the person who goes in the anchor point.
7:10
My approach for alternate sexes
Make 3 pairs each containing a male and a female
Let them represent as
Binary
1 =male
0 =female
Then it should look like this..
where man and women alternates
10 10 10
01 01 01
Each pair is moved by 3!
And the total number of sitting position where each sex alternates is 2
(Described above)
So
3! x 2 =12
The pairs thing is ambiguously worded, so I disagree that it's necessarily different from the first problem.
An easier way to think of the man/woman problem is to first only consider the number of ways you can arrange 3 distinct women around the table, ignoring the men for now and assuming that they are fixed between the women. We should know that that is 3! . Now we do the same for the men, 3! . The result is then the sum of these two results: 3! + 3! = 12
Real MVP
how can we spot the difference between combinations and permutations
Depends on the wording of the question and how it's realized/implemented in real life. You generally have to figure that out for yourself.
Permutation questions are about arrangements(how many ways can a given number of objects be arranged) whereas combination questions are about selections(how many objects can be selected from a given number of objects).
It can save lives 😂
One way to explain this is ->
Lets fix one male as reference ->
then there are 2! ways of arranging other males and 3! ways of arranging females alternate to those males.
So total ways = 2! * 3! = 12 Ways
We can approach the alternate sexes on table step wise.
Step 1 - Sit the man. (3! = 6).
Step 2 - Sit the woman (3! = 6)
Step 3 - Sum both options (6+6 = 12).
A better way to see Circular permutation is by this formula: Cp (n) = (n - 1)!
Yes, but that doesn't give any insight on how to solve problems where people are sitting in a rectangle. Two sides can hold three people and the other two sides can only hold two people. With the "circular" formula, there's no way to solve that question. With the method in the video, it's not a hard task.
At around 2:20 when you say that shifting everyone around the table while preserving their order, results in the same arrangement; aren't you making the assumption that the seats are indistinguishable. Without that assumption, wouldn't the answer be 6!?
+Jay Smith We don't worry about the seats, we just care about the arrangement of the people.
Yup! that's the point of this tutorial though. Without that assumption, it'd be a combination problem, not a permutation.
circular permutation formula = (n-1)!
then u can choose 3 men or 3 women to place in the circle = (3-1)!
after just place the opposite sex = (3-1)! x 3!
"These are the ones that you would see on a final"
Me only in the first week of class with questions that are even more confusing than this.
12hrs to my discrete math exams and here for salvation 😂😂
At 9:20 why would it be 9! instead of 3! ?
3 spots with 12 possible elements ends up as being 12 x 11 x 10. This happens to be equivalent to 12!/9!. If it were 12!/3!, our answer would be 12x11x10x9x8x7x6x5x4 which is intuitively way too large.
trevor savior!(if ur name is trevor)
I really didnt get the Second Example...
What if an opposite sex couple were to be considered tied together. Then the number of ways of arranging the 3 tied couples would be 3! = 6. The the number of arrangements of each tied couple would be 2!=2. Thus, 6 x 2 = 12. I stand to be corrected.
this guy sounds like CGP Grey
9:52 🤣😂
That last one is wrong. Should be 3*6!.
for the male/female problem I added 3! with 3 ! and got 12. Is this right?
Timestamp: 13:26
Even though it is addition, why did you go from (6!/2!) +(6!/2!) to 2(6!/2!)
Thanks!
Let a=(6!/2!) so what we get is (6!/2!)+(6!/2!)=a+a=2a. Resubstitute (6!/2!) for a and we get 2a=2(6!/2!)
Waw
what if the men and women had names
Adam and eve
Dude, are you the casually explained guy??????
You have to be! I totally recognize your voice
nope. Didn't even know who he was until I checked after a couple people posted comments.
Nuts! Even your cadence is the same.
Anyways, good videos man! Thanks a lot
That moment when you accidentally discover casually explained while you are determined to learn counting and then you no longer are cause you bailed on trev
It's okay. I bailed on myself too.