0
$\begingroup$

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))
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For clarification, $F(l, 1) = |A|$ and $F(l, n) = 0$ for $l \lt n$? I am unfortunately not getting the expected results. $\endgroup$ – Paul Feb 18 '18 at 2:29
  • $\begingroup$ 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. $\endgroup$ – Paul Feb 18 '18 at 2:41
  • $\begingroup$ Ah, you are right. I will change it. And you are correct about the base cases. $\endgroup$ – Riley Feb 18 '18 at 2:46
  • $\begingroup$ 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. $\endgroup$ – Paul Feb 18 '18 at 3:05
  • $\begingroup$ 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. $\endgroup$ – Riley Feb 18 '18 at 3:34

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.