Counting with Identical Items

Transcript

So far we have discussed counting arrangements in which we'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, let's 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 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 three factorial or six different ways to arrange those three dictionaries, that's why we have six cases here. Now we temporarily were treating those three dictionaries as if they were really different, but they're really identical. And all six arrangements on the previous slide would look identical. In other words, for all six of them we'd see three dictionaries in the same place because it doesn't matter what order we put the dictionaries in.

Of the seven 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 seven factorial is actually three factorial too big. In other words, it's six times too big, and therefore we have to divide by three factorial.

So seven factorial divided by three 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 that the n items, there could be one group of b identical items, they're 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 numbers, 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 only have 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 divide it by 2 factorial for the 2 P's So here is a practice problem of this sort.

Pause the video and see if you can do this on your own. Okay, a librarian has five identical copies of book A, two 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 five factorial for the five identical copies of A, and divide it by two factorial for the two identical copies of book B.

So that's going to be eight factorial divided by two factorial times five factorial. Gonna write out all the factors. I can cancel all those factors in five factorial. I can also cancel the two with the six to get a three. 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.