Simplest way to count distinct combinations #2
By Daniel Johnston
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
$\endgroup$ 12 Answers
$\begingroup$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$
$\endgroup$ $\begingroup$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)!}$$
$\endgroup$
