Simplest way to count distinct combinations #2

Question

Following my previous problem (which was solved) Simplest way to count distinct combinations

(Reading this topic is not mandatory).

Consider I have these letters: A, B, C, D, E.

n is the number of letters, so in this case, n = 5.

I want to get all letter combinations, with lengths from 1 to 5 (the number of letters). From A, AA, ABC, ... to EEEEE. This leads to a total of 3905 possible combinations:

• 1^n = 5
• 2^n = 25
• 3^n = 125
• 4^n = 625
• 5^n = 3125

5 + 25 + 125 + 625 + 3125 = 3905.

Now what if I want to count only combinations that can not have the same letter more than once? I know the result is 325 (when I un-duplicate by hand) but I don't succeed in finding the formula that leads to it.

Any ideas?

Thank you, Ben

Answer 1

The number of ways to make such a word with $k$ letters is given by the number of ways to choose the $k$ letters (which is $\binom5k$) multiplied by the number of ways to rearrange those letters ($k!$) giving $\frac{5!}{(5-k)!}$. Alternatively, you can think of this as a permutation: $5$ choices for the first letter, $4$ for the second, etc., which gives the same formula.

The total is then $5 + 5\cdot 4 + 5\cdot4\cdot3 + 5\cdot4\cdot3\cdot2 + 5\cdot4\cdot3\cdot2\cdot1 = 5 + 20 + 60 + 120 + 120 = 325$

Answer 2

Let's say we have $n$ letters, and we want to count the number of words of length $k$ with no repeated letters. Well, we have $n$ choices for the first letter, $(n-1)$ choices for the second letter, and so on until we get $(n-k+1)$ choices for the $k$-th letter. So we have $\frac{n!}{(n-k)!}=P(n,k)$ words of length $k$ fitting your description.

To get your final answer, we need to sum over all $k$ from $1$ to $n$:

$$\sum_{k=1}^n\frac{n!}{(n-k)!}$$