7
$\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$
1

3 Answers 3

4
$\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$
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$
3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .