Permutations of Identical Objects (Part 1)

So far we’ve talked about permutations of objects which were distinct. Things change when some (or all) of the objects to be arranged are identical.

Suppose we have to arrange 5 balls in a row of which 3 are of the same color, and the other two are of different colors. How many different arrangements are possible?

Here’s one way to think about this problem.

Let’s designate five boxes, each of which is to be filled by one ball.

First, we’ll place the identical balls in any three of the five boxes. This can be done in ⁵C₃ ways. Here’s one of them.

Next, in the remaining two boxes, we’ll place the remaining two balls. This can be done in 2! ways.

or

Therefore the total number of arrangements will be ⁵C₃ x 2! = 5!/3! = 20.

Now let’s say 2 of the 5 balls are of the same color and the other 3 are of different colors. How many different arrangements are possible?

Similar to the method used above, we’ll first place the identical balls in any 2 of the 5 boxes, in ⁵C₂ ways. One of the arrangement is given below.

Now in the remaining three boxes, the remaining three balls can be placed in 3! ways.

Therefore the total number of arrangements will be ⁵C₂ x 3! = 5!/2! = 60.

We could also have placed the different colored balls first. This can be done by first selecting any three boxes, (in ⁵C₃ ways), and then placing the balls in the boxes (3! ways).

After we’ve placed these three balls, the remaining two balls will be filled with the two identical balls (which can be done in only one way).

The answer remains the same (⁵C₃ x 3!) x 1 = 5!/2! = 60

Do you see a pattern? Had the 5 balls been all of different colors, the total number of arrangements would have been 5!. When 3 of the balls were identical, the answer changed to 5!/3!, and when 2 of them were identical, the answer was 5!/2!. Can we arrive at a formula or a generalisation?

Suppose there are n objects, to be arranged in a row, of which p objects are identical, and the remaining are distinct. How many arrangements are possible?

In this case we have n boxes, each to be filled with one ball. We’ll first select any p boxes out of the n boxes, in ⁿC_p ways. Now we’ll place the identical balls in the selected boxes, one in each. We’re now left with n – p boxes and n – p balls, which can be placed in the boxes in (n – p)! ways.

Therefore the total number of ways is ⁿC_p (n – p)! or n!/p!

Lesson Summary

1. The number of ways to arrange n objects in a row, of which exactly p objects are identical, is n!/p!

I’ll pause here, and take a few more cases involving identical objects in the next part of the lesson. See you there.