# Solving n-tuple alphabet problem with recurrence relation

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))


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$.

• For clarification, $F(l, 1) = |A|$ and $F(l, n) = 0$ for $l \lt n$? I am unfortunately not getting the expected results. – Paul Feb 18 '18 at 2:29
• Ahh, I think I found one error in your relation. In case 2, the value of $A$ in $F(l-1, n-1)$ should be $|A| - 1$. That is, the value of $A$ must also be passed, something like $F(l,n,|A|) = |A|(F(l-1,n,|A|) + F(l-1,n-1,|A|-1)$ and a few base cases. – Paul Feb 18 '18 at 2:41
• Ah, you are right. I will change it. And you are correct about the base cases. – Riley Feb 18 '18 at 2:46
• There still seems to be a problem. I tested an implementation of the recurrence and it returned 24 instead of 18. I'll add more details in the main post. – Paul Feb 18 '18 at 3:05
• I've figured out the source of the double counting. It's coming from Case 1, because nothing is guaranteeing that one of the $n$ characters selected in that iteration must be $a_1$. I fixed my answer, and this time, it got your example correct! Sorry I made so many mistakes. – Riley Feb 18 '18 at 3:34