0
$\begingroup$

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$
  • $\begingroup$ So you want to sum the permutations of choosing $k$ letters from 5; $$ perm(5,1) + perm(5,2) + perm(5,3) + perm(5,4) + perm(5,5) = 325 $$ $\endgroup$ – Matti P. Feb 22 '18 at 16:27
1
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.