شمارش با آیتم های مشابه

Counting with identical items.

So far, we have discussed counting arrangements in which each of the n items is different, This is natural, when the individuals are human beings for example.

Sometimes though, we have to arrange sets in which some of the items are identical and this requires a special approach to calculation.

Consider this problem, pause the video think about this and then we’ll talk about it.

Okay, a librarian has 7 books to arrange, 4 different novels, and 3 identical copies of the same dictionary, how many different orders could these 7 books be put on the shelf?

Well think about it this way.

Suppose we temporarily treat the three dictionaries as three completely different books.

We’ll call them D1, D2 and D3.

Then we could put the 7 different books in 7 factorial different orders.

Now let’s think about those arrangements.

Here’s a typical order, and we’ll just say J, K, L and M are the four novels.

So we could put them in that order.

Now, consider the arrangements with the four novels in the same places and just the three dictionaries swapped around and exchanged with each other.

And we could get this.

So there are 3 factorial, that is, 6 ways, to re-arrange the 3 dictionaries.

That makes sense because if you’re re-arranging 3 things, there are 3 factorial ways to do so.

Now, we were temporarily treating the 3 dictionaries as if they were different, but really, they are the same, and all 6 of those arrangements on the previous slide would result in an identical arrangement of the books on the shelf.

Of the 7 factorial total arrangements, we could group them six-at-a-time into groups like this, and all 6 in the group would result in identical arrangements of books on the shelf.

So as long as the 4 novels are in the same 4 slots, then it doesn’t matter how we swap around the dictionaries.

It’s going to be the same arrangement on the shelf because the dictionaries are identical.

So the number 7 factorial, that is not the correct number.

That number is 3 factorial times too big.

In other words, 6 times too big.

Because for any arrangement of the dictionaries, the three dictionaries, we can rearrange the dictionaries in 3 factorial ways.

Well if that’s 3 factorial too big we’d have to divide by that.

So the correct answer is 7 factorial divided by 3 factorial.

Well, let’s write this out.

We can cancel a lot.

We get 7 times 6 times 5 times 4, 7 times 6 is 42 and 5 times 4 is 20.

42 times 20, well, 2 times 42 is 84, so 20 times 42=840, and that, in fact, is the correct answer.

That’s the number of combinations.

Notice that, in a set of n items, there were b identical items, then the total number of arrangements is N equals n factorial divided by b factorial.

That’s a really important formula.

Now suppose we are counting arrangements of a set of in total items that contain more than one set of identical items.

So for example, of the total of the n total items, there could be one group of b identical items, a different group of c identical items and yet another group of d identical items. Well then the total number of arrangements would be this, it’d be N factorial times the factorial of the size of each sub-group of identical items. So dived by b factorial, c factorial and d factorial.

For example, some sources call this the “Mississippi rule” because of its application to the question: how many different arrangements can we make of the 11 letters in the name of the U.S. State Mississippi?

Well that’s a name that has a lot of repetitions in it.

There’s only 1 M, but there are 4 I’s, 4 S’s and 2 P’s, and so if we arrange those 11 letters, all the possible arrangements we can make of those long letters would be 11 factorial divided by 4 factorial for the I’s, divided by 4 factorial for the S’s, dived by 2 factorial for the P’s.

And if we multiply all that out, that would be the number of different of different arrangements we could make, from all 11 letters in the name Mississippi.

Notice that the rule I have given here only works in a very specific case: we are rearranging an entire set of n items, including b repeated items and every item in the set will be included in the final result.

Okay, in other words, we’re taking the 11 letters of the word Mississippi, and we’re rearranging it and getting some new collection of 11 letters.

That’s what the formula is for.

For example, if we’re selecting some items from a larger pool, and the pool contains repetitions, this constitutes an entirely different scenario.

In general, there’s no formulaic approach to that, we often have to solve by listing or some other method.

So instead, if we had the question, take the letters in Mississippi, which of course, has a lot of repetitions in it.

Suppose we selected four letters at random and made a four letter word from those letters, how many different four letter words could we make from the letters in Mississippi?

Well, holy mackerel.

That is a much, much harder question, and there is absolutely no formula on Earth that is going to help you solve that question.

So, very important to appreciate the difference in these two scenarios.

Rearranging the whole set with some repetitions in it versus a pool with repetitions in it, and making selections from that set.

So here’s a practice problem.

Pause the video and then we’ll talk about this.

Okay, so this is a problem that falls in line of the formula that we discussed above.

So we can just use that formula.

We have 5 identical copies of 1 book, 2 identical copies of another book and then a single copy of a third book so we have 8 books altogether, we’re gonna put all 8 on the shelf.

And we want to know, how many distinct orders can we create.

Well, here we can just use the formula.

This is fantastic.

8 factorial, divided by 2 factorial, those are for the 2 copies of B divided by 5 factorial, those are the 5 copies of A.

We do a little canceling, then we cancel the 6 and the 2 to get 3.

Then we have 8 times 7 times 3, well one way to do is is, 7 times 3 is 21 well 8 times 20 is 160, so add another 8 to that, that would be 168, and that’s the answer.

Here’s another practice problem, pause the video and then we’ll talk about this.

Okay, notice that here, we’re in the other scenario I talked about.

There is no formula we can use here.

Because now we have 12 marbles.

But we’re not talking about orders of all 12.

We’re using that 12 as a pool.

And we’re picking only 3 marbles at random from the 12.

So here there’s no formula that will work.

Fortunately, it’s not that hard just to list here.

So here’s how I’d say we could list it.

How many can we have 3 of the same color?

So we could have 3 greens, or we could have 3 blues.

We can’t have 3 reds, because there aren’t 3 reds.

If we have 2 of one color and 1 of another color.

Well, we could have 2 greens with one of the other colors, 2 blues with one of the other colors, or 2 reds and one of the other colors.

Or we could have 3 different colors.

Those are all the possibilities right there.

And so that’s 9 possibilities.

If in a set of N items B are identical.

Then the total number of distinct arrangements are N factorial divided by B factorial.

If in the set of N items B are identical, different set C are identical, and different set D are identical.

Then we divide n factorial by all those individual subset factorials.

And of course, both of these rules are only for when we’re talking about arrangements of the entire set.

If we have some other thing, where we have a pool with arrangements in it and then we’re selecting from that pool, then we’re going to have to resort to listing and counting, because there’s no formula in that case.