Solving n-tuple alphabet problem with recurrence relation

Question

I am trying to solve a programming problem which I think involves n-tuples, but please tell me if I am wrong.

Given an alphabet $A$, how many words of length $l$ can be made using exactly $n$ distinct letters, where $n \le |A| \le l$?

So if, $A=\{a, b, c\},l = 3, n = 2$,

Then the possible words would be: $\{aab, aba, baa, aac, aca, caa, bba, bab, abb, bbc, bcb, cbb, cca, cac, acc, ccb, cbc, bcc\}$ (I think thats all of them)

I am familiar with the multinomial theorem, and I think I can brute force this by solving for every denominator. But this is kind of cumbersome, I was wondering if there is a simpler approach.

#python example of Riley's solution

def F(l, n, A):
    if (l < n):
        return 0
    elif (n == 1):
        return A
    else:
        return A * (F(l - 1, n, A, D) + F(l - 1, n - 1, A - 1, D) - F(l - 1, n, A - 1, D))

Answer 1

Let $\{a_i\}$ be the sequence of letters representing our word. Let's try to think about this recursively. The first letter $a_1$ can be any of the $|A|$ letters. Then there are two cases:

Case 1. The letter $a_1$ appears again in our string. Then the rest of the string reduces to the problem of the number of words of length $l-1$ with $n$ distinct characters.

But there is a small problem here. We must make sure that $a_1$ is in fact repeated in this subproblem, to avoid double counting with Case 2. We can do this by subtracting off the subproblem of the number of words of length $l-1$ with $n$ distinct characters from the reduced alphabet $A\setminus \{a_1\}$

Case 2. The letter $a_1$ does not appear again in our string. Then the rest of the string reduces to the problem of the number of words of length $l-1$ with $n-1$ distinct characters, and with an alphabet one letter smaller.

So, if $F(l,n,|A|)$ is the number of words of length $l$ with $n$ distinct characters from an alphabet of size $|A|$, then we have the recurrence relation $$F(l,n,|A|)=|A|(F(l-1,n,|A|)+F(l-1,n-1,|A|-1)-F(l-1,n,|A|-1))$$

Since this is a programming problem, I would use dynamic programming. I tested this new recurrence with your provided python code, and it turned up the correct answer of $18$.