2

More precise generic formulation of the problem:

Given an alphabet of $A$ different letters, how many $K$ length words can we form that have exactly $D$ different letters?

Example:

Given $\{a,b,c,d,e,f\}$ as the alphabet (for $A = 6$), how many $5$ letter words (for $K = 5$) can we form that have exactly $3$ different letters (for $D = 3$)?

So a couple of such words would be:

$$ abddd, adbdd, abeee, abfff, abbcc, abcbc, afafb, fabbf $$

...etc

Any suggestion to look for the shortest general solution is appreciated.

Willie Wong
  • 73,139
alian
  • 163

3 Answers3

4

The Stirling numbers of the second kind $\def\st{\genfrac\{\}0{}}\st nk$ count the number of ways to partition a set of $n$ distinct values into $k$ nonempty subsets. Taking those $n$ objects to be the $n$ positions in a word, and the subsets those that will receive the same letter, we see that with an alphabet of $x$ letters we can make $$ \st nk\,x^{\underline k}\stackrel{\rm def}=\st nk\,x(x-1)\ldots(x-k+1)=\st nk\binom xkk! $$ different words of length $n$ that use exactly $k$ different letters: once our partition into subsets chosen, we have $x$ choices for the letter to attached to the first subset, $x-1$ choices for the second subset, and so forth.

Note that $\sum_{k=0}^n\st nk\,x^{\underline k}=x^n$ is a well known relation, and in our application expresses the fact that each of the $x^n$ words of length$~n$ contributes to the term for exactly one vale of$~k$, its number of different letters.

In terms of the names used in the question, take $n=K$, $k=D$, and $x=A$.

There are many ways to compute the Stirling numbers of the second kind efficiently, but no simple multiplicative formula as for the binomial coefficients. If you need to go up to $n=100$ then you certainly need big integers to store them; to compute them I would personally just use the additive recursion $$ \st{n+1}k=\st n{k-1}+k\st nk $$ which computes them using $O(n^2)$ small multiplications and additions.

Marc van Leeuwen
  • 115,048
  • Thanks much for this effort. It appears to me so far from my empirical tests that this solution is correct, I'm still checking this it by hand and will let you know. It took me a minute to wrap my head around to choose the letter positions as the objects and the ones that get the same letter as the subsets, it's rather inverted... – alian Jul 02 '13 at 15:00
1

First, you select the letters to use in ${A \choose D}$ ways. Then you find a composition of $K$ into $D$ parts. Then you use the multinomial distribution to arrange the characters of the parts. By hand, it is a mess, for small numbers in a computer, it is easy.

Added: Say we have $A=100, K=16, D=6$. There are ${100 \choose 6}= 1192052400$ ways to select the six letters to use. Then there are ${15 \choose 5}=3003$ ways to choose how many of each letter. One of them would have four of the first letter, three of the second, one of the third, fourth, and fifth, and six of the last. There are then $\frac {16!}{4!3!6!}= 201801600$ ways to arrange them. So this selection gives $1192052400*3003*201801600=722395919056331520000\approx 7.22\cdot 10^{20}$ possibilities. Does your computer have that much memory?

Ross Millikan
  • 374,822
  • I need to work this out for fairly large alphabets A > 100, and words of length K > 16. Actually what I'm interested in is the probability of such a word occurring from a normal distribution of all words over the given alphabet. But that's trivial if I know how to calculate the number of possible such words. Partitioning would count abbcc and abcbc as equal? How is that going to work? Not sure I get how the multinomial distribution works for this either? – alian Jul 01 '13 at 04:45
  • Checking for your example it seems to be incorrect, the number should be ~2.347326552×10²¹ for A = 100, K = 16, D = 6. – alian Jul 02 '13 at 15:01
  • I only did versions that split the $16$ as $4+3+1+1+1+6$. I think your figure is way low for the total-I would guess around $10^{25}.$ How did you get it? – Ross Millikan Jul 02 '13 at 17:41
  • See my comments to the solution above, this result is based on that, I checked it empirically also. – alian Jul 02 '13 at 18:31
0

I finally sat down to confirm that the solution by Marc van Leeuwen is correct.

Bellow is the download page to the program code I wrote to calculate the solutions to this problem.

http://ambits.org/download.html

http://ambits.org/akd/akd.c

alian
  • 163