How many strings of length L and n distinct lowercase letters?

Question

Given a set of the lower case alphabet letters {a, b, c, .., z} and two integers n, l.

How many strings of length l are there containing only n distinct letters?

Example:

At n = 2, l=6, some valid strings are: "ababab", "aaabbb", "accccc", "ccccca"

Answer 1

Suppose you have an alphabet of $w$ letters and want to find the number of words of length $n$ with exactly $k$ distinct letters.

To count this first select the $k$ letters in $ \binom{w}{k}$ ways.

Once we have done this the problem is equivalent to finding surjective functions from the $n$ spaces to the $k$ letters.

This can be solved using stirling numbers of the second kind, we get $k!\times { n \brace k}$.

---

Hence the final answer is $\binom{w}{k} \times k! \times \ { n \brace k}$.

Calculating stirling coefficients can be done linearly (assuming we can get binomial coefficients constantly) using inclusion exclusion or quadratically using the recursion (similar to the binomial coefficient recursion, see the wiki page for more info)