Permutation of multiset

Question

How many 8-permutation are there of the letters of the word 'ADDRESSES'?

My textbook suggests that we should divide the situation into cases where a different letter is removed. In other words, for the multiset $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$, we count the number of permutation of the follow set:

1. $\{0 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$
2. $\{1 \cdot A, 1 \cdot D, 1 \cdot R, 2 \cdot E, 3 \cdot S\}$
3. $\{1 \cdot A, 2 \cdot D, 0 \cdot R, 2 \cdot E, 3 \cdot S\}$
4. $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 1 \cdot E, 3 \cdot S\}$
5. $\{1 \cdot A, 2 \cdot D, 1 \cdot R, 2 \cdot E, 2 \cdot S\}$

It is easy to show that the total number of 8-permutation is $15120$. I am not happy with this case-dividing computation and I want to have a direct computation of the result. Accidentally, I find that $$C_8^9\frac{8!}{2!2!3!}=15120.$$ I further test this formula, e.g. 3-permutation of a multiset with 4 elements, and it actually works. So I think there should be a nice explanation why the formula works. Can anyone explain that for me?

Answer 1

An algebraic solution

The permutations of all 9 letters taken together = $\dfrac{9!}{1!2!1!2!3!}=\dfrac{9!}{a!b!c!d!e!}$, say

Leaving 1 letter at a time, we get $8!\left[\dfrac{1}{(a-1)!b!c!d!e!} + \dfrac{1}{a!(b-1)!c!d!e!} . . . +\dfrac{1}{a!b!c!d!(e-1)!}\right]$

Putting under a common denominator, we get $8!\left[\dfrac{a+b+c+d+e}{a!b!c!d!e!} \right]$

But $a+b+c+d+e = 9$, so ...... you should be able to see the end.

To simplify, we can leave the multiplication factor as 9 rather than ${9\choose 8}$

Answer 2

There are nine letters in ADDRESSES, but we have eight positions to fill. Thus, we must omit one of the letters. If we omit the A, we can fill two of the eight positions in $\binom{8}{2}$ ways. We can then fill one of the reamining six positions with an R in $\binom{6}{1}$ ways. We can fill two of the remaining positions with E's in $\binom{5}{2}$ ways. Finally, we fill the remaining three positions with S's in $\binom{3}{3}$ ways. Hence, there are $$\binom{8}{2}\binom{6}{1}\binom{5}{2}\binom{3}{3} = \frac{8!}{2!6!} \cdot \frac{6!}{1!5!} \cdot \frac{5!}{2!3!} \cdot \frac{3!}{0!3!} = \frac{8!}{2!1!2!0!3!} = \frac{8!}{2!2!3!}$$ $8$ permutations of the letters of ADDRESSES in which A is omitted. Since there is only one A and one R in ADDRESSES, there are the same number of $8$ permutations in which an R is omitted (interchange the roles of A and R in the above argument).

By similar argument, the number of $8$ permutations in which a D is omitted is $$\binom{8}{1}\binom{7}{1}\binom{6}{1}\binom{5}{2}\binom{3}{3} = \frac{8!}{2!3!}$$ Since there are two D's and two E's in addresses, there are the same number of permutations in which an E is omitted.

The number of $8$ permutations in which an S is omitted is $$\binom{8}{1}\binom{7}{2}\binom{5}{1}\binom{4}{2}\binom{2}{2} = \frac{8!}{2!2!2!}$$

Adding the cases above yields \begin{align*} \frac{8!}{2!2!3!} + \frac{8!}{2!2!3!} + \frac{8!}{2!3!} + \frac{8!}{2!3!} + \frac{8!}{2!2!2!} & = \frac{8!}{2!2!3!}(1 + 1 + 2 + 2 + 3)\\ & = 9 \cdot \frac{8!}{2!2!3!}\\ & = \frac{9!}{2!2!3!} \end{align*}

Answer 3

A combinatoric solution

Imagine $9$ distinct types of candy labelled $1$ to $9$ being distributed to $5$ children, numbers given to a child $(1-1-2-2-3)$ based on (say) age, type(s) given to a particular child random.

We distribute the candies one by one. After we have distributed $8$ candies, there is only one way to distribute the last one.

So whether we actually distribute the last one or not, the total number of ways to distribute remains the same, $\dfrac{9!}{1!1!2!2!3!}$

Answer 4

As you observed (in a comment on a different answer), the number of 8-permutations of this multiset is equal to the number of 9-permutations. As noted in another answer, we can show that this is true by observing that every 9-permutation can be mapped to an 8-permutation by dropping the last letter; and the inverse of this mapping exists (simply add back the letter that was dropped; there is only one possible way to do this), so it is one-to-one and onto and the two sets of combinations have equal size.

This is a general observation that is true for any 9-letter word.

The reason not to ignore the method of the book is that the "one-case" method works in general only for $(n-1)$-permutations (and of course $n$-permutations) of an $n$-letter word. If you were looking for 7-permutations of 'ADDRESSES' then you might need to consider the different cases depending on which letters were removed. There will certainly not be a one-to-one mapping to the 9-permutations.