Mathematics · Ch 6 — Permutations and Combinations

Permutations When All the Objects Are Not Distinct Objects

6.3.4

Permutations When All the Objects Are Not Distinct Objects

Permutations When Objects Are Not All Distinct

Until now, every permutation problem we solved assumed that all objects being arranged were different from one another. But what happens when some objects are identical? The word ROOT has four letters, but two of them are the same letter O. If we simply wrote $4! = 24$ , we would be counting arrangements that are actually identical — swapping the two O's doesn't create a new word.

The key insight is this: when objects are identical, swapping them produces the same arrangement, not a different one. So we must divide out the overcounting.

The Core Idea — Worked Out with ROOT

Take the word ROOT. Temporarily treat the two O's as if they were different — call them $O_1$ and $O_2$ . Now we have four distinct objects: R, $O_1$ , $O_2$ , T. The number of permutations of these four distinct letters taken all at a time is $4! = 24$ .

Consider one such permutation: $R\,O_1\,O_2\,T$ . If $O_1$ and $O_2$ are actually the same letter O, then the two permutations $R\,O_1\,O_2\,T$ and $R\,O_2\,O_1\,T$ are identical — both give the word ROOT. In fact, for every arrangement we counted in the $4!$ list, there is a corresponding arrangement where the two O's are swapped, and these two are the same when the O's are identical.

How many such swaps exist for each arrangement? The two O's can be arranged among themselves in $2!$ ways. So every distinct arrangement of the actual letters ROOT has been counted $2!$ times in the $4!$ total.

Therefore, the actual number of distinct permutations is:

\frac{4!}{2!} = \frac{24}{2} = 12

Note

The textbook shows this pairing explicitly in a large table. For each arrangement like $R\,O_1\,O_2\,T$ , the pair $R\,O_2\,O_1\,T$ is the same actual word. The 24 permutations of four distinct letters collapse into 12 distinct words when the two O's are identical.

Extending the Idea — INSTITUTE

Now consider the word INSTITUTE. It has 9 letters: I appears 2 times, T appears 3 times, and the remaining letters (N, S, U, E) are all different.

Temporarily treat the I's as $I_1$ , $I_2$ and the T's as $T_1$ , $T_2$ , $T_3$ . The number of permutations of 9 distinct objects is $9!$ .

Take one such permutation, say $I_1\,N\,T_1\,S\,I_2\,T_2\,U\,E\,T_3$ . If the I's are actually identical and the T's are actually identical, then:

The two I's can be rearranged among themselves in $2!$ ways without changing the word.
The three T's can be rearranged among themselves in $3!$ ways without changing the word.

These rearrangements are independent, so each distinct arrangement of the actual letters has been counted $2! \times 3!$ times in the $9!$ total.

Hence, the number of distinct permutations is:

\frac{9!}{2! \times 3!}

Theorem 3 — One Type of Repeated Object

\frac{n!}{p!}

The number of permutations of $n$ objects, where $p$ objects are of the same kind and the rest are all different, is $\frac{n!}{p!}$ .

Why this works: Treat the $p$ identical objects as distinct temporarily. This gives $n!$ permutations. But the $p$ identical objects can be arranged among themselves in $p!$ ways, and all these arrangements correspond to the same actual permutation. So we divide by $p!$ .

Theorem 4 — Multiple Types of Repeated Objects

\frac{n!}{p_1! \; p_2! \; \cdots \; p_k!}

The number of permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ are of a second kind, $\dots$ , $p_k$ are of a $k$ th kind, and the rest (if any) are all different, is:

\frac{n!}{p_1! \; p_2! \; \cdots \; p_k!}

Why this works: Treat all objects as distinct temporarily — this gives $n!$ permutations. The $p_1$ identical objects of the first kind can be rearranged in $p_1!$ ways without changing the arrangement, the $p_2$ identical objects of the second kind in $p_2!$ ways, and so on. Since these rearrangements are independent, each distinct arrangement has been counted $p_1! \times p_2! \times \cdots \times p_k!$ times. Dividing by this product gives the correct count.

Watch out

A common mistake is to forget that the "rest, if any" are all different — they contribute a factor of $1!$ each, which doesn't change the denominator. Only the repeated objects contribute factors to the denominator.

Example 9 — ALLAHABAD

The word ALLAHABAD has 9 letters: 4 A's, 2 L's, and the rest (H, B, D) are all different.

Using Theorem 4 with $n = 9$ , $p_1 = 4$ (for A), $p_2 = 2$ (for L):

\frac{9!}{4! \; 2!} = \frac{9 \times 8 \times 7 \times 6 \times 5 \times 4!}{4! \times 2} = \frac{9 \times 8 \times 7 \times 6 \times 5}{2} = 9 \times 8 \times 7 \times 3 \times 5 = 7560

Example 14 — DAUGHTER (Vowels Together / Never Together)

The word DAUGHTER has 8 distinct letters. The vowels are A, U, E (3 vowels). The consonants are D, G, H, T, R (5 consonants).

Part (i): All vowels occur together

Treat the three vowels as a single block (AUE). This block plus the 5 consonants gives 6 objects, all distinct. These 6 objects can be arranged in $6!$ ways.

Inside the block, the 3 vowels can be arranged among themselves in $3!$ ways.

By the multiplication principle: $6! \times 3! = 720 \times 6 = 4320$

Part (ii): All vowels do NOT occur together

Total arrangements without any restriction: $8! = 40320$

Subtract the arrangements where vowels are together (from part i): $40320 - 4320 = 36000$

Tip

"Never together" problems are almost always solved by subtraction: total arrangements minus arrangements where they ARE together. Direct counting of "never together" is usually much harder.

Example 15 — Coloured Discs

We have 4 red, 3 yellow, and 2 green discs, all indistinguishable within their own colour. Total discs = $4 + 3 + 2 = 9$ .

Using Theorem 4 with $n = 9$ , $p_1 = 4$ , $p_2 = 3$ , $p_3 = 2$ :

\frac{9!}{4! \; 3! \; 2!} = \frac{362880}{24 \times 6 \times 2} = \frac{362880}{288} = 1260

Example 16 — INDEPENDENCE

The word INDEPENDENCE has 12 letters: N appears 3 times, E appears 4 times, D appears 2 times, and the rest (I, P, C) are all different.

Total arrangements without restriction:

\frac{12!}{3! \; 4! \; 2!} = 1663200

Part (i): Words starting with P …

Theorem 3

Theorem 4: Permutations When Objects Are Not All Distinct

\frac{n!}{p_1! \; p_2! \; \cdots \; p_k!}

The number of permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ are of a second kind, ..., $p_k$ are of the $k$ th kind, and the rest (if any) are all different, is given by the formula above.

The hypothesis is that objects of the same kind are indistinguishable from each other. The $p_1, p_2, \ldots, p_k$ are positive integers whose sum is at most $n$ ; the remaining $n - (p_1 + p_2 + \cdots + p_k)$ objects are all distinct from each other and from the $k$ kinds.

When Do We Use This?

This formula applies whenever we arrange items where some are identical — rearranging letters of a word with repeated letters, arranging coloured discs where discs of the same colour look the same, or any situation where swapping two identical objects does not produce a new arrangement.

›Proof

Step 1: Treat identical objects as distinct temporarily.

Suppose we label the $p_1$ identical objects as $A_1, A_2, \ldots, A_{p_1}$ , the $p_2$ identical objects as $B_1, B_2, \ldots, B_{p_2}$ , and so on. If we treat every object as distinct (by these temporary labels), then we have $n$ distinct objects. The number of permutations of $n$ distinct objects taken all at a time is $n!$ .

Step 2: Count how many labelled permutations collapse into one actual arrangement.

Consider any one actual arrangement of the objects (where identical objects are not distinguished). In the labelled version, the $p_1$ objects of the first kind can be permuted among themselves in $p_1!$ ways without changing the actual arrangement — because swapping $A_1$ and $A_2$ leaves the same pattern of first-kind objects. Similarly, the $p_2$ objects of the second kind can be rearranged in $p_2!$ ways, and so on up to the $k$ th kind. By the multiplication principle, the total number of labelled permutations that correspond to this single actual arrangement is

$p_1! \times p_2! \times \cdots \times p_k!$

Step 3: Divide to remove the overcount.

Every actual arrangement is counted exactly $p_1! \, p_2! \, \cdots \, p_k!$ times in the $n!$ labelled permutations. Therefore, the number of distinct actual permutations is

$\frac{n!}{p_1! \; p_2! \; \cdots \; p_k!}$

This completes the proof. …

Theorem 4