Permutation with Repetition

combinatorics

Definition

Permutation with Repetition

A permutation with repetition chooses all $n$ occurrences in a multiset and places them in order. Order matters, so $AAB$ and $ABA$ are different arrangements. Equal copies are nevertheless indistinguishable, so swapping the two copies of $A$ within $AAB$ does not create a new arrangement. Each distinct element must occur with its fixed multiplicity.

Let a multiset contain $k$ distinct elements $a_1,\dots ,a_k$ with multiplicities $n_1,\dots ,n_k$, where

$$n_1+\cdots +n_k=n.$$

Such a permutation is an ordered tuple of length $n$ containing exactly $n_i$ copies of each $a_i$. The number of distinct such permutations is the multinomial coefficient

$$\left(\genfrac{}{}{0ex}{}{n}{n_1,\dots ,n_k}\right)=\frac{n!}{n_1!\cdots n_k!}.$$

Derivation from the Product Rule

Construct an arrangement by assigning positions to one distinct value at a time. First choose the $n_1$ positions occupied by $a_1$ from all $n$ positions. This can be done in $\left(\genfrac{}{}{0ex}{}{n}{n_1}\right)$ ways and leaves $n-n_1$ positions empty.

Next choose the $n_2$ positions occupied by $a_2$ from those remaining positions, giving $\left(\genfrac{}{}{0ex}{}{n-n_1}{n_2}\right)$ choices. Then choose the $n_3$ positions occupied by $a_3$ from the $n-n_1-n_2$ positions still empty, giving $\left(\genfrac{}{}{0ex}{}{n-n_1-n_2}{n_3}\right)$ choices.

Continue in the same way until every value has been placed. Because $n_1+\cdots +n_k=n$, exactly $n_k$ positions remain for $a_k$, so the final choice is forced.

For the multiset $\{\{A,A,B\}\}$, choose two of the three positions for $A$. The remaining position is then forced to contain $B$:

The three first-stage branches are the three subsets of positions of size two. Each branch has one continuation because the final position is forced.

The product rule multiplies the number of choices at each stage:

$$\left(\genfrac{}{}{0ex}{}{n}{n_1}\right)\left(\genfrac{}{}{0ex}{}{n-n_1}{n_2}\right)\left(\genfrac{}{}{0ex}{}{n-n_1-n_2}{n_3}\right)\cdots \left(\genfrac{}{}{0ex}{}{n_k}{n_k}\right).$$

Expanding the binomial coefficients exposes a telescoping product:

$$\begin{array}{rl}\frac{n!}{n_1!\cancel{(n-n_1)!}}& \cdot \frac{\cancel{(n-n_1)!}}{n_2!\cancel{(n-n_1-n_2)!}}\\ & \cdot \frac{\cancel{(n-n_1-n_2)!}}{n_3!\cancel{(n-n_1-n_2-n_3)!}}\\ & \cdot \frac{\cancel{(n-n_1-n_2-n_3)!}}{n_4!(n-n_1-n_2-n_3-n_4)!}\\ & \cdot \dots \\ & \cdot \frac{n_k!}{n_k!0!}\\ & =\frac{n!}{n_1!n_2!\cdots n_k!}.\end{array}$$

The cyan factorial counts the positions left after placing $a_1$ and before placing $a_2$, so it appears once below and once above the fraction bar. The orange and green pairs arise in the same way at the next stages. Every intermediate factorial hidden by the ellipsis cancels by this pattern. Finally, $0!=1$, leaving only $n!$ and the multiplicity factors $n_1!,\dots ,n_k!$.

Why the Denominator Appears

If all $n$ occurrences were distinct, they would have $n!$ permutations. The $n_i$ copies of $a_i$ are indistinguishable, however, so permuting those copies among themselves does not change the resulting tuple.

Every distinct tuple is therefore counted

$$n_1!\dots n_k!$$

times among the $n!$ labelled arrangements. Dividing by this overcount gives the formula.

Why division rather than subtraction?

Begin with one visible arrangement, $AAB$. To count as though every occurrence were distinct, temporarily name the two copies of $A$ as $A_1$ and $A_2$. The same visible arrangement then has two labelled descriptions:

The factor $2!$ is not a collection of two bad arrangements to remove. It is the number of labelled descriptions of every one visible arrangement. More generally, if the multiplicities are $n_1,\dots ,n_k$, then each visible arrangement has

$$q=n_1!\cdots n_k!$$

labelled descriptions. If there are $N$ visible arrangements, the labelled world therefore consists of $N$ equal groups of size $q$:

$$n!=Nq⟹N=\frac{n!}{q}.$$

Division counts the number of equal groups. Subtraction would require removing $q-1$ duplicates from each of the still-unknown $N$ groups, so it cannot remove a fixed number globally.

Forgetting labels in $\{A,A,B\}$

Temporarily distinguish the repeated copies as $A_1$ and $A_2$. Their $3!=6$ labelled permutations collapse in pairs when the subscripts are forgotten:

Each visible arrangement has $2!$ labelled versions, obtained by swapping $A_1$ and $A_2$. Hence

$$\frac{3!}{2!}=3.$$

With several repeated values, the labels within each value can be permuted independently. The size of each collapsed group is therefore $n_1!\cdots n_k!$.

Cancelling the overcount in $\{A,A,B,B,C\}$

Here $n=5$ and the multiplicities are $2,2,1$. Expanding the factorials shows how the denominator removes the indistinguishable relabellings:

$$\begin{array}{rlrl}\frac{5!}{2!2!1!}& =\frac{(5\cdot 4\cdot 3)(2\cdot 1)}{(2\cdot 1)(2\cdot 1)(1)}& & \text{expand}\\ & =\frac{5\cdot 4\cdot 3}{2\cdot 1}& & \text{cancel }2\cdot 1\\ & =5\cdot 2\cdot 3& & \text{contract }4/2\\ & =30.& & \end{array}$$

One factor $2!$ removes permutations of the two copies of $A$; the other removes permutations of the two copies of $B$. The factor $1!$ changes nothing.

The denominator as successive collapses

Start with labelled copies and forget one family of labels at a time. Each step merges arrangements that differ only by a swap of indistinguishable copies.

The diagram and the algebra express the same quotient:

$$5!=120\stackrel{÷2!}{\to }60\stackrel{÷2!}{\to }30=\frac{5!}{2!2!1!}.$$

Fill positions instead of collapsing labels

A different construction places one value at a time. Choose two of the five positions for $A$, two of the three remaining positions for $B$, and give the final position to $C$.

The counts refer to subsets of the available positions:

$$\underset{\begin{array}{c}\text{two positions}\\ \text{for }A\end{array}}{\underbrace{\left(\genfrac{}{}{0ex}{}{5}{2}\right)}}=10,\underset{\begin{array}{c}\text{two remaining positions}\\ \text{for }B\end{array}}{\underbrace{\left(\genfrac{}{}{0ex}{}{3}{2}\right)}}=3,\underset{\begin{array}{c}\text{final position}\\ \text{for }C\end{array}}{\underbrace{\left(\genfrac{}{}{0ex}{}{1}{1}\right)}}=1.$$

Once the positions of $A$ are fixed, only three positions remain. Once the positions of $B$ are fixed, the last position is forced to contain $C$.

The successive choices multiply:

$$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{5}{2}\right)\left(\genfrac{}{}{0ex}{}{3}{2}\right)\left(\genfrac{}{}{0ex}{}{1}{1}\right)& =10\cdot 3\cdot 1\\ & =\frac{5!}{2!3!}\cdot \frac{3!}{2!1!}\cdot \frac{1!}{1!0!}\\ & =\frac{5!}{2!2!1!}\\ & =30.\end{array}$$

The intermediate $3!$ and $1!$ terms telescope. Choosing positions one value at a time therefore produces the same denominator as collapsing labelled copies.

Distinction from Sampling with Replacement

Warning

Here the multiplicity of each element is fixed in advance. If instead each of $n$ positions may independently receive any of $k$ elements, the number of possible tuples is $k^n$.

Example

Arranging BANANA

The word BANANA contains six letters with multiplicities

$$n_A=3,n_N=2,n_B=1.$$

Its number of distinct arrangements is

$$\frac{6!}{3!2!1!}=60.$$