Permutations with repeated objects

When objects look alike

In how many ways can the letters of the word ROOT be arranged?

If the two O's were different, say $\text{O}_1$ and $\text{O}_2$, there would be $4! = 24$ orders. But $\text{RO}_1\text{O}_2\text{T}$ and $\text{RO}_2\text{O}_1\text{T}$ both read ROOT. Every word is counted twice, once for each order of the O's.

So the number of different words is

Why we divide

Group the $24$ orders by the word they spell. Each group holds the $2!$ orders of the two O's. So $24$ orders make $24 \div 2! = 12$ groups, one for each word.

The same idea works for any number of repeats. If a letter appears $p$ times, each word appears $p!$ times among the orders. We divide by $p!$.

The formula

The number of permutations of $n$ objects, where $p$ are alike of one kind, $q$ are alike of a second kind and $s$ are alike of a third kind, is

The rest of the objects are all different. A letter that appears once adds $1! = 1$ to the bottom, so it changes nothing.

Two examples

COMMITTEE. It has $9$ letters: M twice, T twice, E twice, and C, O and I once each. The number of arrangements is

INSTITUTE. It has $9$ letters: I twice, T three times, and N, S, U and E once each. So there are

arrangements.

Tiles and colours

The letters can be anything that looks alike. Beads of one colour, flags of one kind and digits of one value all count as alike. Tiles of the same colour can swap places without changing the row.

Set B and C to $0$. With only A tiles, there is just one word, however many tiles you use.

Repeats together with a condition

Conditions work with repeats too. Take ALLAHABAD. It has $9$ letters: A four times, L twice, and H, B and D once each. In how many arrangements do all the A's stand together?

Step 1. Glue the A's. The four A's become one block, AAAA. Inside, they look alike, so the block has one order.

Step 2. Count the units. The block, L, L, H, B and D make $6$ units, with L twice.

Step 3. Arrange. $\dfrac{6!}{2!} = \dfrac{720}{2} = 360$.

Without the condition there are $\dfrac{9!}{4!\, 2!} = 7560$ arrangements. So $360$ of the $7560$ keep the A's together.

A worked example

How many different rows can be made with $4$ red, $3$ blue and $2$ green tiles, if tiles of one colour look alike?

Step 1. Count the tiles. $4 + 3 + 2 = 9$.

Step 2. Divide by the repeats. $\dfrac{9!}{4!\, 3!\, 2!} = \dfrac{362880}{24 \times 6 \times 2} = 1260$.

Answer: $1260$ rows.

Practise with new numbers

Try it in Python

The program forms every order of the tiles R, O, O and T. A Python set keeps each word only once, so its size is the number of different words.

Common mistakes

• Dividing by the wrong factorial. Divide by $p!$ for a letter that appears $p$ times, not by $p$.
• Adding the repeats. For two repeated letters, divide by $p!\, q!$, a product, not $(p + q)!$.
• Forgetting a repeated letter. COMMITTEE has three letters that repeat, not two.
• Gluing alike objects and multiplying by $k!$. A block of equal letters has only one order inside.

Remember these

• Swapping two alike objects gives no new arrangement.
• $n$ objects with groups of $p$, $q$, $s$ alike give $\dfrac{n!}{p!\, q!\, s!}$ arrangements.
• A letter that appears once divides by $1! = 1$.
• To keep alike objects together, glue them: the block has one order inside.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. How many arrangements does the word NOON have?

2. In how many ways can $3$ white and $2$ black beads be put in a row, if beads of one colour look alike?

3. Divya says the word BANANA has $\dfrac{6!}{3 \times 2}$ arrangements. Is she right?

4. Why does a letter that appears only once not change the bottom of the formula?

5. In how many arrangements of the letters of DEEDS do the two E's stand together?