Counting with Identical Items
So far, we've 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, 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 7 factorial different orders, all right? That much is clear. Now, let's think about this arrangement. 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 an identical places and the three dictionaries are arranged in different order.
And of course, there are 3 factorial, or 6 different ways to arrange those 3 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 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 in 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 can 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 on d 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 Is, we have four Ss, and we have two Ps.
And so we'd have to take 11 factorial, divide it by the 4 factorial for the four Is. Divided by 4 factorial again for the 4 Ss, and divided by 2 factorial for the 2 Ps. 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 five 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 8 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. I'm gonna write out all the factors.
I can cancel all those factors and 5 factorial, I can also cancel the 2 with the 6 and get 3. So I get 8 x 7 x 3. 8 x 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 transcriptConsider 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, 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 7 factorial different orders, all right? That much is clear. Now, let's think about this arrangement. 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 an identical places and the three dictionaries are arranged in different order.
And of course, there are 3 factorial, or 6 different ways to arrange those 3 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 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 in 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 can 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 on d 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 Is, we have four Ss, and we have two Ps.
And so we'd have to take 11 factorial, divide it by the 4 factorial for the four Is. Divided by 4 factorial again for the 4 Ss, and divided by 2 factorial for the 2 Ps. 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 five 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 8 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. I'm gonna write out all the factors.
I can cancel all those factors and 5 factorial, I can also cancel the 2 with the 6 and get 3. So I get 8 x 7 x 3. 8 x 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.
