How do you calculate the number of $k$ letter words on an alphabet of length $n$, with conditions:
- order of letters doesn't matter
- words with repeated letters are excluded
E.g. The $2$-letter words on an alphabet of size $3$ $\{A, B, C\}$ would be $3$:
- $AB, BC, CA$
(since by 1. $AB = BA$ etc, and by 2. $AA, BB, CC$ are excluded).
Best Answer
If the order of letters doesn't matter, and we cannot repeat letters, then we are effectively looking for the number of subsets of size $k$ of the alphabet. The formula for the binomial coefficient calculates exactly this:
$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$
In the case $k=2$, a more intuitive method for coming to the above formula may be the following:
First, the total number of $2$-letter words on an alphabet of size $n$ is:
$$n^2$$
Since you have $n$ choices for the first letter, and $n$ choices for the second.
But since we cannot repeat letters, we are effectively choosing our first letter in our word without replacing it back to the alphabet for the second choice, so the formula becomes:
$$n(n-1)$$
And since the order of letters doesn't matter, which in words of length $2$ is equivalent to saying reflected words are identified, we cut our number of words in half:
$$\frac{n(n-1)}{2}$$
Which is equivalent to the above formula for $k=2$.
If calculating this value programatically for large numbers is a concern, the python function
scipy.special.comb(n, k, exact=True)is an option.