Permutations with repetition and identical objects

So far we have arranged distinct objects with no repetition. Two important variants change the count.

Case 1: Repetition allowed

If we want a sequence of length $r$ from $n$ distinct items, with each position chosen independently (repetition allowed), then by the multiplication principle: $\boxed{\text{Number of sequences} = n^r.}$

Example: $3$-digit codes from digits $0$–$9$ (repetition allowed): $10^3 = 1000$.

Case 2: Identical objects

If some of the $n$ objects are identical, then permutations that swap them are not really distinct. The corrected count is $\boxed{\dfrac{n!}{n_1!\,n_2!\,\cdots\,n_k!}}$ where $n_1, n_2, \dots, n_k$ are the multiplicities (how many of each kind), with $n_1 + n_2 + \dots + n_k = n$.

This is the multinomial coefficient $\binom{n}{n_1, n_2, \dots, n_k}$.

Derivation of the identical-objects formula

Suppose all $n$ objects were treated as distinct: total arrangements $= n!$. Now collapse the $n_1$ objects of type 1: each true arrangement gets overcounted by $n_1!$ (the orderings of those $n_1$ identical objects among themselves don't matter). Similarly for type 2, etc. Divide: $\text{True count} = \dfrac{n!}{n_1! \cdot n_2! \cdots n_k!}. \qed$

Case 3: Circular arrangements

When $n$ distinct objects are arranged in a circle (e.g. around a round table), only the relative positions matter , rotating the whole circle gives the same arrangement. So we fix one object and arrange the remaining $n - 1$: $\text{Circular permutations of } n = (n - 1)!.$

If we also identify reflections (e.g. for a necklace), divide by $2$: $(n - 1)!/2$.

Worked examples

Example 1. How many license plates of three letters followed by four digits are there, with repetition allowed?

Letters: $26^3 = 17{,}576$. Digits: $10^4 = 10{,}000$. Total: $26^3 \cdot 10^4 = 175{,}760{,}000$.

Example 2. How many arrangements of the letters of the word MISSISSIPPI?

Letters: $M(1), I(4), S(4), P(2)$. Total letters: $11$. $\dfrac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \dfrac{39{,}916{,}800}{24 \cdot 24 \cdot 2} = \dfrac{39{,}916{,}800}{1152} = 34{,}650.$

Example 3. How many ways can $6$ people sit around a round table?

Circular permutations: $(6 - 1)! = 120$.

Example 4. How many words can be formed from the letters of BANANA so that the two $N$'s are always together?

Glue $NN$ as a block. Letters to arrange: $B, A, A, A, NN$ , $5$ objects with $A$'s repeating. $\dfrac{5!}{3!} = 20.$

Example 5 (harder). How many ways can $7$ beads of $3$ different colours (e.g. $3$ red, $2$ green, $2$ blue) be strung in a circular necklace? (Reflections identified.)

If beads were distinguishable: $(7 - 1)!/2 = 360$.

With identical beads, we cannot simply divide by repetitions because rotation/reflection interact non-trivially with identical beads. The correct count uses Burnside's lemma, beyond Class-XI scope. In a typical Class-XI problem you would take the beads as distinguishable.

If the beads are distinguishable, the answer is $\dfrac{6!}{2} = 360$.

If we just count distinct linear arrangements with identical beads: $\dfrac{7!}{3! \cdot 2! \cdot 2!} = 210$. Circular (without reflection): $\dfrac{210}{7} = 30$.

(Class XI problems typically stop at the simpler cases.)

Try it yourself

1. How many $5$-letter words can be formed from $A$–$Z$ with repetition allowed?
2. How many distinct arrangements of the letters of LEVEL?
3. How many distinct arrangements of STATISTICS?
4. How many ways can $5$ persons sit around a round table?
5. How many ways can $4$ men and $4$ women sit around a circular table, alternating?
6. How many $4$-digit even numbers with digits from $0$–$9$ (repetition allowed)?
7. How many arrangements of "PENCIL" have the two vowels together?
8. How many distinct arrangements of "INDEPENDENCE"?
9. How many garlands can be made from $7$ different flowers? (Circular with reflection.)
10. How many three-letter strings using $A, B, C, D, E$ allow letter repetition?
11. How many arrangements of "ALLAHABAD" have the vowels in odd places?
12. Find the number of arrangements of $a, b, c, d, e, f, g$ in which $a, c, e$ appear in that relative order.

Pitfalls / Tricks

• For identical objects, divide by $n_1! \cdot n_2! \cdots$. Forgetting to do this multiplies your answer by a factorial.
• For circular permutations of $n$ distinct objects, the count is $(n - 1)!$, not $n!$. The $n!$ overcounts by a factor of $n$ (one rotation for each starting position).
• Necklaces vs round tables: necklaces identify reflections (divide by $2$), tables don't.
• Insight. Repetition allowed and identical objects are opposites: repetition allowed expands the count (to $n^r$), while identical objects contract it (divide by factorials). Apply the right one to your problem.