Permutations of fixed length words of an arbitrary alphabet with fixed number of different letters

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.

-

migrated from mathoverflow.netJul 1 '13 at 2:02

This question came from our site for professional mathematicians.

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.

-
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 2 '13 at 15:00

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?

-
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 1 '13 at 4: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 2 '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 2 '13 at 17:41
See my comments to the solution above, this result is based on that, I checked it empirically also. – alian Jul 2 '13 at 18:31

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.