# Permutation of multiset

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?

• This is a good observation. As shown in the answers below, the number of permutations of a word with n letters is the same as the number of n-1 permutations of the word. Commented Sep 16, 2015 at 20:00
• Commented Jul 1, 2022 at 18:56
• – user1150169
Commented Feb 17, 2023 at 11:47

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}$

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!}$

• You posted an edited version of this answer later, so you can delete this one. Commented Sep 16, 2015 at 19:07
• @Taussig:Thanks, didn't know that old solution shows while I am editing. Submitting a different type of solution Commented Sep 16, 2015 at 19:25
• I think this is the "nice" answer, although the "algebraic" version is not too much different in principle. Commented Sep 16, 2015 at 19:52

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.

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*}

• Thx for replying. I just realize that the number of 9-permutation and the number of 8-permutation are the same! Is it due to the fact that for any 9-permutation I can remove, say, the last letter, to form an 8-permutation? Commented Sep 16, 2015 at 17:06
• I misread your question earlier, so I have corrected my answer to account for the fact that you were seeking the number of 8-permutations rather than the number of 9-permutations. As you noticed, they are the same for exactly the reason you cited. Commented Sep 16, 2015 at 20:32