## Counting with Identical Items

### Transcript

So far, we have discussed counting arrangements in which you've been assuming that each of the n items is different. That we have n unique items, and this is certainly natural when the individuals are human beings. Each human being is different, and each human being is unique. Sometimes we have to arrange sets in which we're talking about objects.

And some of these objects are identical. And this requires a special approach to calculation. Consider this problem. We're gonna talk through this problem. A librarian has seven books to arrange. Four different novels, and three identical copies of the same dictionary.

How many different orders could these seven books be put on the shelf? All right, well lets think about how we're gonna approach this. Think about it this way. Suppose we temporarily treat the three dictionaries as if they were three different books. We'll call them D1, D2 and D3.

Then we could put all seven books in seven factorial different orders. All right, that much is clear. Now let's think about those arrangements. Here's one typical arrangement. Let's just say J, K, L and M, those are the four novels. And so I put them in this order.

That's just a random order with the three dictionaries, and the four novels spread in. Now consider all the arrangements with the four novels in the same place, and then just the three dictionaries rearranged. And so we'd have all these possibilities. Again, these are six sets.

In all of them, the four novels are in identical places, and the three dictionaries are arranged in different orders. And of course, there are 3 factorial, or 6 different ways to arrange those 3 dictionaries. That's why we have 6 cases here. Now we temporarily were treating those 3 dictionaries as if they were really different.

But they're really identical, and all 6 arrangements on the previous slide would look identical. In order words, for all six of them, we'd see 3 dictionaries in the same place. Because it doesn't matter what order we put the dictionaries in. Of the 7 factorial total arrangements, we could group them six at a time into groups like this.

And all six in the group would result in an identical arrangement of books on the shelf. So our number, 7 factorial, Is actually 3 factorial too big. In other words it's 6 times too big, and therefore we have to divide by 3 factorial. So 7 factorial divided by 3 factorial, we'll write out the factorial.

We can cancel some factors. We just get 7 times 6, times 5, times 4. 7 times 6 is 42, 5 times 4 is 20, 20 times 42 is 840. And so that would actually be the number of orders in which we could arrange the four novels, and the three identical dictionaries. Notice that in a set of n items there were b identical items.

And the total number of arrangements with those b identical items is n factorial over b factorial. That's an important rule. Suppose the collection of n items contains more than one set of identical items. For example, suppose of the n items, there could be one group of b identical items that are all the same as each other.

A different group of c identical items, all the same as each other. And yet another group of d identical items, all the same as each other. Then the total number of arrangements we would just divide by b factorial, c factorial, and d factorial. By the individual numbers of identical items. Some sources call this the Mississippi rule.

Because of its application to this question, how many different arrangements can we make of the 11 letters in the name of the US state Mississippi? And of course, it's tricky, because there are so many identical letters in the name of the state Mississippi. What we have, we have only one M, but we have four I's, we have four S's, and we have two P's.

And so, we'd have to take 11 factorial, divide it by the 4 factorial, for the 4 I's. Divide it by 4 factorial again for the 4 S's, and divided by 2 factorial for the 2 P's. So here's a practice problem of this sort. Pause the video, and see if you can do this on your own.

Okay, a librarian has 5 identical copies of book A, 2 identical copies of book B, and a single copy of book C. In how many distinct orders can he arrange these eight books on a shelf? Well, we know that we're gonna take the eight factorial, which is the total number of orders. Divide it by 5 factorial for the 5 identical copies of A, and divide it by 2 factorial for the 2 identical copies of book B.

So that's gonna be 8 factorial, divided by 2 factorial, times 5 factorial. We're gonna write all the factors. I can cancel all those factors in 5 factorial. I can also cancel the 2 with the 6 get a 3. So I get 8 times 7, times 3. 8 times 21, which is 168, and that's the answer.

In summary, if in a total set of n items, b are identical, then the total number of distinct arrangements is n factorial divided by b factorial. If in the set of n items, b are identical, a different group of c are identical, and a different group d are identical, then we divide n factorial by the product of all those individual factorials. Remember, listing and counting can also be helpful.

So if you start to list out some, then it might give you the idea of how to set this up. Often an important approach in counting problems.

Read full transcriptAnd some of these objects are identical. And this requires a special approach to calculation. Consider this problem. We're gonna talk through this problem. A librarian has seven books to arrange. Four different novels, and three identical copies of the same dictionary.

How many different orders could these seven books be put on the shelf? All right, well lets think about how we're gonna approach this. Think about it this way. Suppose we temporarily treat the three dictionaries as if they were three different books. We'll call them D1, D2 and D3.

Then we could put all seven books in seven factorial different orders. All right, that much is clear. Now let's think about those arrangements. Here's one typical arrangement. Let's just say J, K, L and M, those are the four novels. And so I put them in this order.

That's just a random order with the three dictionaries, and the four novels spread in. Now consider all the arrangements with the four novels in the same place, and then just the three dictionaries rearranged. And so we'd have all these possibilities. Again, these are six sets.

In all of them, the four novels are in identical places, and the three dictionaries are arranged in different orders. And of course, there are 3 factorial, or 6 different ways to arrange those 3 dictionaries. That's why we have 6 cases here. Now we temporarily were treating those 3 dictionaries as if they were really different.

But they're really identical, and all 6 arrangements on the previous slide would look identical. In order words, for all six of them, we'd see 3 dictionaries in the same place. Because it doesn't matter what order we put the dictionaries in. Of the 7 factorial total arrangements, we could group them six at a time into groups like this.

And all six in the group would result in an identical arrangement of books on the shelf. So our number, 7 factorial, Is actually 3 factorial too big. In other words it's 6 times too big, and therefore we have to divide by 3 factorial. So 7 factorial divided by 3 factorial, we'll write out the factorial.

We can cancel some factors. We just get 7 times 6, times 5, times 4. 7 times 6 is 42, 5 times 4 is 20, 20 times 42 is 840. And so that would actually be the number of orders in which we could arrange the four novels, and the three identical dictionaries. Notice that in a set of n items there were b identical items.

And the total number of arrangements with those b identical items is n factorial over b factorial. That's an important rule. Suppose the collection of n items contains more than one set of identical items. For example, suppose of the n items, there could be one group of b identical items that are all the same as each other.

A different group of c identical items, all the same as each other. And yet another group of d identical items, all the same as each other. Then the total number of arrangements we would just divide by b factorial, c factorial, and d factorial. By the individual numbers of identical items. Some sources call this the Mississippi rule.

Because of its application to this question, how many different arrangements can we make of the 11 letters in the name of the US state Mississippi? And of course, it's tricky, because there are so many identical letters in the name of the state Mississippi. What we have, we have only one M, but we have four I's, we have four S's, and we have two P's.

And so, we'd have to take 11 factorial, divide it by the 4 factorial, for the 4 I's. Divide it by 4 factorial again for the 4 S's, and divided by 2 factorial for the 2 P's. So here's a practice problem of this sort. Pause the video, and see if you can do this on your own.

Okay, a librarian has 5 identical copies of book A, 2 identical copies of book B, and a single copy of book C. In how many distinct orders can he arrange these eight books on a shelf? Well, we know that we're gonna take the eight factorial, which is the total number of orders. Divide it by 5 factorial for the 5 identical copies of A, and divide it by 2 factorial for the 2 identical copies of book B.

So that's gonna be 8 factorial, divided by 2 factorial, times 5 factorial. We're gonna write all the factors. I can cancel all those factors in 5 factorial. I can also cancel the 2 with the 6 get a 3. So I get 8 times 7, times 3. 8 times 21, which is 168, and that's the answer.

In summary, if in a total set of n items, b are identical, then the total number of distinct arrangements is n factorial divided by b factorial. If in the set of n items, b are identical, a different group of c are identical, and a different group d are identical, then we divide n factorial by the product of all those individual factorials. Remember, listing and counting can also be helpful.

So if you start to list out some, then it might give you the idea of how to set this up. Often an important approach in counting problems.