Counting permutation of duplicate items
I am not really sure I fully understand the formula for finding the number of permutation of duplicate items.
The formula is:
$$\frac{n!}{p!q!r!\cdots}$$
Where do the factorials in the denominator exactly come from?
If we asssume the string "ANNA" and we want the count of the permutation of duplicate items.
We have $4$ characters so since we have $4$ options for the first character, $3$ for the second, $2$ for the third and $1$ for the last we have $4!$ different permutations.
But some of the characters are duplicates.
We have "A" and "N" repeated, meaning it adds more permutations to the outcome.
If $p=2$ is the number of occurences of "A" and if $q = 2$ is the number of occurences for "N" then would the $p!$ and $q!$ essentially be selecting $1$ item at a time from $2$ (or $p$) duplicates? So essentially are the denominators the binomial $\binom{2}{1}$ (or generally $\binom{p}{1}$ where $p$ are the number of repeated characters) where order does not matter?
Is my understanding correct?
4 Answers
$\begingroup$A different way of viewing this formula which avoids "division by symmetry" arguments:
Given $n$ items, $p$ of which are identical of one type, $q$ of which are identical of another type, $r$ of which are identical of a third type, etc... with $p+q+r+\dots = n$, approach the count by following the steps:
Pick which of the spaces are used by the $p$ objects of the first type. There are $\binom{n}{p}$ ways to make this choice
Pick which of the remaining spaces are used by the $q$ objects of the second type. There are $\binom{n-p}{q}$ ways to make this choice given the earlier choice
Pick which of the remaining spaces are used by the $r$ objects of the third type. There are $\binom{n-p-q}{r}$ ways to make this choice given the earlier choices
$\vdots$
This gives a final total of:
$$\binom{n}{p}\binom{n-p}{q}\binom{n-p-q}{r}\cdots$$
Note, this explanation was able to completely avoid division as an operation as binomial coefficients could have been defined recursively purely using addition and multiplication.
Now... if you insist on rewriting this using fractions, you should know that $\binom{a}{b}=\dfrac{a!}{b!(a-b)!}$ in which case you have
$$\binom{n}{p}\binom{n-p}{q}\binom{n-p-q}{r}\cdots = \dfrac{n!}{p!\color{red}{(n-p)!}}\cdot \dfrac{\color{red}{(n-p)!}}{q!\color{blue}{(n-p-q)!}}\cdot\dfrac{\color{blue}{(n-p-q)!}}{r!(n-p-q-r)!}\cdots$$
Cancelling the numerators of each term after the first in the product with a portion of the denominator from the previous term gives the well known $$\dfrac{n!}{p!q!r!\cdots}$$
$\endgroup$ 6 $\begingroup$The first part giving $4!=24$ different permutations of $4$ distinct objects is fine.
Now we consider the word $ANNA$ where we have two letters of one kind $A$ and two letters of another kind $N$.
Let $x$ denote the number of different permutations we can obtain from the letters $A,A,N,N$.
Suppose the $2$ letters $A$ are replaced by $2$ new letters, distinct from each other and from all other letters being permuted. These $2$ new letters may be permuted in $2!$ ways; hence the number of permutations of the new set of objects is $x\cdot 2!$.
Next suppse the $2$ letters $N$ are replaced by $2$ new letters, distinct from each other and from all other letters being permuted. These $2$ new letters may be permuted in $2!$ ways; hence the number of permutations of the new set of objects is $x\cdot 2! \cdot 2!$.
Since the number of permutations of $4$ distinct letters is $4!$ we obtain\begin{align*} x\cdot 2!\cdot 2!&=4!\\ \color{blue}{x}&\color{blue}{=\frac{4!}{2!2!}} \end{align*}
Doing the same approach with $p$ equal objects of one kind, $q$ equal objects of another kind, and so on, we obtain in general\begin{align*} \frac{n!}{p!q!\cdots} \end{align*}with $p+q+\cdots =n$.
$\endgroup$ 2 $\begingroup$$n!$ is, as you stated, the number of ways to permutate if no item is a duplicate. However, let's take ANNA as an example. Lets's number the letters by 1-4 according to their position ($1=4=A$, $2=3=N$) So, within the $4!$ options, we have, for example, 1324 and 1234 which are identical (both spell ANNA). The inner permutation between two identical items is what you see in the denominator; for this example, you have $2!$ since $1=4$, and $2!$ since $2=3$. So, all in all you get $ \frac {4!} {2!2!} = 24/4 = 6$
$\endgroup$ 2 $\begingroup$The denominators (p, q, r...) are permutations themselves. You mention C(p, 1) = p as the denominator which is not correct. The correct denominator is $p!$
A simpler way to understand this is: Let's take the string "ANNA". We have 4! (n! for n letters) permutations of this, ignoring repetitions. For each instance of these permutation, e.g., $A_1 A_2 NN$ and $A_2 A_1 N N$, where $A_1$ is the first A and so on. So the string $AANN$ is repeated twice (2!, in case of p repetitions of a letter it is p!), if we only take the duplicates due to the permutations of A. To discount the duplicates, you need to divide by p! If you follow the same line of logic, you get the formula you mentioned.
$\endgroup$ 4
