3
$\begingroup$

Let us say we are trying to compute the unique permutations of the word:

$$PEPPER$$

We cannot compute this by relabeling:

$$P_1E_1P_2P_3E_2R$$

Because this would simply be $6!$ and does not take into account repetition. However, I have seen the formula: $$ \frac{6!}{3! 2!} $$ I.e take the total number of positions, and then divide by the product of factorials of repeated elements. My question is, why does this work? Could anyone supply a combinatorial argument?

$\endgroup$
3
$\begingroup$

Since the word $PEPPER$ has six letters, we have six positions to fill. We can select which three are occupied by the three $P$s in $\binom{6}{3}$ ways. That leaves three positions to fill. We can choose which two of them are occupied by the two $E$s in $\binom{3}{2}$ ways. The remaining position must be occupied by the $R$. Hence, the number of distinguishable ways the letters of the word $PEPPER$ can be arranged is $$\binom{6}{3}\binom{3}{2}\binom{1}{1} = \frac{6!}{3!3!} \cdot \frac{3!}{2!1!} \cdot \frac{1!}{1!0!} = \frac{6!}{3!2!1!0!} = \frac{6!}{3!2!1!}$$ The factor of $3!$ in the denominator represents the number of ways the three $P$s could be permuted among themselves within a given arrangement of the letters of the word $PEPPER$ without producing an arrangement that is distinguishable from that arrangement. The factors of $2!$ and $1!$ play an analogous role for the two $E$s and one $R$ in an arrangement of the letters of the word $PEPPER$.

$\endgroup$
1
$\begingroup$

There are $6!$ ways to arrange with repetition.

There are $3!$ ways to arrange the $P$'s: since $P_1 \ E \ P_2 \ P_3 \ E \ R$ is the same as $P_1 \ E \ P_3 \ P_2 \ E \ R$ and so on.

Similarly, there are $2!$ ways to arrange the $E$'s, because $P \ E_1 \ P \ P \ E_2 \ R$ and $P \ E_2 \ P \ P \ E_1 \ R$ are the same.

There is only $1!$ way to arrange $R$, so the number of combinations is:

$$\frac{6!}{3! \ 2! \ 1!}$$

$\endgroup$
1
$\begingroup$

Right, with repetition there are $6!$ ways. To convert from "with repetition" to "without repetition", you need to remove the equivalents. For example, consider $P_1P_2P_3E_1E_2R$. Now you need to ignore other choices with the three letters $P$ in the first three positions. Overall, there are $3!$ choices with the first three letters $P$: $$\color{red}{P_1}\color{green}{P_2}\color{blue}{P_3}E_1E_2R \equiv \\ \color{red}{P_1}\color{blue}{P_3}\color{green}{P_2}E_1E_2R \equiv \\ \color{green}{P_2}\color{red}{P_1}\color{blue}{P_3}E_1E_2R \equiv \\ \color{green}{P_2}\color{blue}{P_3}\color{red}{P_1}E_1E_2R \equiv \\ \color{blue}{P_3}\color{red}{P_1}\color{green}{P_2}E_1E_2R \equiv \\ \color{blue}{P_3}\color{green}{P_2}\color{red}{P_1}E_1E_2R.\ \ $$
Hence, you must divide by $3!$. Similarly, for other letters.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.