University of Michigan
Runs his own tutoring company
Carl taught upper-level math in several schools and currently runs his own tutoring company. He bets that no one can beat his love for intensive outdoor activities!
To unlock all 5,300 videos, start your free trial.
University of Michigan
Runs his own tutoring company
Carl taught upper-level math in several schools and currently runs his own tutoring company. He bets that no one can beat his love for intensive outdoor activities!
Two things are distinct when we can actually tell them apart and sometimes what we are going to talk about is distinct permutations which is basically when we have permutations rearrangements of things that are the same.
So the example we want to look at now are ways tat we can rearrange the letters in mom and if you notice, there is going to be two ms and how that comes up is we have three spots for our letters and what we could have is we could have one m, then the other m, let's do it with different colors so you can see the difference, or we could switch these two and then have one and then the other and in this case what I'm looking at is the 'o' is in the same spot.
So what we've really done is we have rearranged these two ms, there is one first and there is the other one and flip back forth, but these aren't distinct because if push comes to shove, if I hadn't color-coated these, they'd be the same exact word.
So what we have to do is take something into consideration. There are, if you remember three factorial ways to rearrange the letters in mom. There is three things that can go here, two things that can go here, and one thing that can go here. So what we have is three factorials if we didn't have those two ms so we also have to consider the number of ways to rearrange these two ms, we could have an m here, we could have an m here the same thing, so that's basically going to be divided by two factorial because there are two factorial ways of arranging those two ms.
This m and this m you switch them it's going to be the exact same word. So what we do id divide it by two factorial and what we actually end up in this case is the 2 and the 1 cancel and this is going to be equal to 3. One way you can think about this one is to prove it to yourself is you have three spots two letters are the same so basically the o can go first, second or third, there's only one word we can make with each of those situations.
So basically what we have is you will see frequently in your book is for distinct permutations, it's something that looks like this, you'll see n factorial over r1 factorial, r2 factorial, r3 factorial so on and so forth where basically n is the total number of letter we're looking at and r1, r2, r3 are just the number of duplicate letters for each unique letter. So this one what we're looking at is three letters n being our 1, there's only 1 letter that was repeated.
Let's do the same thing for a little bit more complicated word let's say Mississippi i-s-s-i-p-p-i, so what we need to do is first figure out how many total letters we have 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, so 11 factorial goes on the top.
We now need to figure out the letters that are duplicates, so we only have one m so that's perfectly fine, we have 1, 2, 3, 4 is, so we have to divide by 4 factorial for the is. We have four ss' so we have to divide by four factorial for the ss as well and we have two ps, so we have to divide by two factorial for the ps.
So whenever you see distinct permutations, usually what you have to keep in mind what makes a book different? So basically in this case if I spell one word and I switch any of these 4 ss' around, it's still going to be the same word and there's four factorial ways of rearranging those ss' same with the is and the ps.
So this is a general formula to remember but basically the main jist is just divide by the number of duplicates factorial to make a distinct permutation.
Unit
Topics in Discrete Math