Tip:
Highlight text to annotate it
X
This video is provided as supplementary material
for courses taught at Howard Community College and this is going to be the
second video
about permutations and combinations. So let's go on with permutations.
Let's say that I've got three letters,
B, O, B, like the name Bob,
and I want to find out how many permutations there are going to be.
Well, since I've got two B's that are the same, I'm going to distinguish them
by calling one of them B-sub-1 and the other one B-sub-2.
And then I could make a tree diagram
to figure out a how many permutations I would have.
I might start out with the letter B-sub-1
or O or B-sub-2. If I started out with B-sub-1,
then my second letter might be either O
or B-sub-2. And if my first letter is O,
my second letter might be B-sub-1 or B-sub-2.
and so on. Now what I've done to save some time
is I've filled out the tree diagram. So here's the completed tree diagram,
and I've also written down all different permutations that I came up with.
And I came up with six permutations, which would make sense -- there were 3
letters.
If I have 3 letters, then I should have 3-factorial permutations.
And 3-factorial is 3 times 2 times 1,
which is 6. But the only reason I can say I have 6 permutations
is because I added those subscripts. If I
disregard the subscripts, the sub-1 and sub-2,
then it turns out that I've got
2 permutations that are the same with B-O-B,
and 2 more permutations that are the same
which B-B-O, and 2 more permutations that are same with
O-B-B. So I've really only got 3 different permutations of
the letters B, O and B,once I disregard the subscripts.
So now what I want to do is figure out a way
to actually know how many permutations I'm going to have
without going through this whole tree diagram. In other words what I want to do
is figure out a way to get rid of the duplicates
that are caused when I have a letter or an element that's repeated.
So there's a way to do that. Here's how we're going to do it. I'm going to
make a fraction.
The numerator of the fraction is going to be
the number the number elements that I've got altogether.
So for the letters B O B, the numerator is going to be 3,
and I'm going to take the factorial version, so that's 3-factorial.
In other words, if all the letters were different, I would have 3-factorial permutations.
But they weren't different. I had
2 letters that were the same, and the number of ways
I could arrange 2 letters would be 2-factorial.
But the two letters were the same, so the arrangements wouldn't make any difference
So I want to divide out that 2-factorial.
So I'll make that the denominator of the fraction. And now it turns out I've got
3-factorial over 2-factorial,
which is the same as 3
times 2 times 1 over
2 times 1. The 2's will cancel out
and the 1's will cancel ou, and I'll get 3 permutations
for the letters B O B. Now in general,
we're going to have a formula that looks like this.
Once again I'll have a fraction. The numerator the fraction will be
n-factorial, in other words the number of elements in the set,
the factorial of that number.
And then, because I might have more than one
letter that's repeated -- I might have a number of different letters repeated --
I'm going to have a number of different elements
in the denominations of the fraction. I could have
what we'll call r-sub-1. r-sub-1 is going to be repeat number one,
and that's how many times that element repeats.
So we'll have r-sub-1 and I want the factorial version of that,
because that would tell me how many permutations of that repeat there are.
If I have another element that repeats, I'll call that
r-sub-2, that's the number of times it repeats,
and I'll have the factorial version of that.
If there's a third element that repeats,
the number of repeats it has is r-sub-3,
and I'll have the factorial. And I could continue this pattern.
So let's take a word with a number of repeats
and see if we can apply this formula and make sure it works.
So
let's take the word 'sentences',
S E N T E N C E S.
I've go 1, 2, 3, 4, 5, 6, 7,
8, 9 letters in it all together.
So n is going to be 9. Therefore n-factorial
will be 9-factorial. Now let's look at the repeats.
So I've got S
and S. That's 2 S's.
So we'll say that those 2 repeats are r-sub-1.
So we'll take the 9-factorial and divide it by
2-factorial.
I've also got E. E repeats
3 times.
So for my r-sub-2
I'll have 3, and I make that 3-factorial.
And I've also got N repeating. N repeats twice.
So I can put in r-sub-3. That will be 2 --
for the number of times that the letter N repeats --
factorial, and then if I
multiply all this out 9-factorial divided by 2-factorial times
3-factorial
times 2-factorial, or if I put into a calculator,
I'll be able to find out how many permutations I would get
from the word 'sentences'.
Now if I had a word with even more repeats --
maybe a fourth letter that repeated and a fifth letter that repeated --
I would just use this formula, but I would also have an r-sub-4
and an r-sub-5 and so on.
So once again, the general principle works like this.
Take the total number of elements you have in your set
regardless of whether they are repeated or not, and
use that number as your numerator followed by the factorial sign.
So that's going to your n-factorial. Then
you're going to have an r number for each of the elements that repeats.
The number, the r-sub-1 or the r-sub-2 and so one, will be how
many times the elements repeat.
So S repeated 2 times, and r-sub-1 became 2.
E repeated 3 times, so r-sub-2
became 3. N repeated 2 times,
so r-sub-3 became 2.
You'll use the factorial version of each one of those numbers.
If you have more elements repeating, just add r-sub-4 and r-sub-5
and so on. And that will give you
the total permutations you're going to have, taking into account
that some of the elements were repeated.
So that's how to deal with sets of elements
that have repeats within them. Okay, I'm going to stop this now.
I'll do one more video where I deal with
combinations. So stick around. I'll be right back with that.