Permutations of Identical Objects: Examples


This lesson will cover a few examples to illustrate what we learnt in the previous lesson.

Example 1 Find the number of arrangements (in a row) of the letters of the following words:

(i) TWITTER

(ii) GOOGLE

Solution (i) There are a total of 7 letters to be arranged in a row of which 3 T’s are identical (and the remaining different). The total number of permutations will be 7!/3! or 840.

(ii) In this case, there are a total of 6 letters which 2 G’s are identical and 2 O’s are identical. The number of arrangements will be 6!/2!2! or 180

Example 2 Consider the following grid

Grid

Here is the situation. You are at the bottom left corner of the grid (the red dot), and are supposed to reach the top right corner of the grid. But there is a condition – you are only allowed to travel along the grid lines, either one step rightward or one step upward. In how many different ways can you reach the top right corner? One such way is shown below.

Grid

Solution This is one example of problem where it isn’t very obvious whether it’s based on permutations or combinations. You’ll come across many such problems, which won’t involve direct application of any formula. In such problems, you need to establish a logic for counting first, and accordingly use the basic counting principles (or formulas, if applicable).

Let’s come back to the problem again. Notice that whatever be the path chosen, there will always be a total of 5 steps in the rightward direction and 4 in the upward direction. See for yourself.

DR4 DR3 Grid

So how does one path differ from another? Only in the order of these forward and upward steps taken.

Let’s denote each path by a series of U’s (upwards) and R’s (rightwards). Each series will consist of 5 R’s and 4 U’s in some order, and will correspond to a unique path.

For example, the first path above will be denoted by UUUURRRRR, the second by URUURRRUR, and the third by URRURURUR.

Now to count the number of paths, we’ll instead count the number of arrangements of these letters, as each arrangement corresponds to a unique path.

Now we have 9 letters, of which 4 U’s are identical, and 5 R’s are identical. The number of arrangements and therefore the number of paths will be 9!/4!5!

Neat!

To count the paths, we counted the number of arrangements of letter series, which was easier to think about and count. Many P & C problems will be about establishing such links between two countable things, which will make things much easier. I’ll cover some more examples of this kind later on.

As an exercise try the following variant of the above problem on your own:

Consider the same grid as in the previous problem. Starting again at the bottom left, how many different paths to the green dot are possible, if you must pass through the blue dot every time?

The next lesson will talk about combinations of identical objects. See you there!

Leave a comment