Permutations with Repetition and Restrictions

The formula $^{n}P_{r} = \dfrac{n!}{(n-r)!}$ from Section 3 assumes every object is distinct and none is repeated in the arrangement. Three common variations extend this basic idea.

Permutations when repetition of objects is allowed

If each of the $r$ positions may independently reuse any of the $n$ available types (e.g. digits in a code, where the same digit can appear more than once), the number of choices for every position stays at $n$ — it never decreases, because nothing is "used up." By the Fundamental Principle of Counting applied $r$ times:

For instance, filling 3 positions with digits from a set of 4 available digits, repetition allowed, gives $4 \times 4 \times 4 = 4^3 = 64$ arrangements — noticeably more than the no-repetition count $^{4}P_{3} = 4 \times 3 \times 2 = 24$, since reuse is now permitted at every stage.

Permutations when the objects themselves are not all distinct

Suppose $n$ objects are to be arranged in a row, but they are not all different — say $p_1$ of one kind are identical to each other, $p_2$ of a second kind are identical, and so on, with $p_1 + p_2 + \cdots + p_k = n$. If all $n$ objects were distinct, there would be $n!$ arrangements; but swapping two identical objects with each other produces an arrangement that looks exactly the same, so the naive count $n!$ over-counts every truly distinct arrangement by a factor of $p_1!$ (the internal orderings of the first repeated kind) times $p_2!$, and so on. Dividing this overcount out gives:

Restricted permutations

Many problems fix extra conditions on which arrangements are allowed:

• Particular objects fixed in particular positions. If certain positions are pre-assigned to certain objects, remove both from consideration and simply arrange the remaining objects in the remaining positions using $^{n}P_{r}$ or $n!$ as appropriate.
• Particular objects always together. Glue the objects that must stay together into a single combined "block." Arrange this block along with the remaining separate objects (fewer total units now), then multiply by the number of ways the objects can be ordered within the block, since the FPC treats "arrange the units" and "arrange inside the block" as two independent stages of one combined process. …