# Combinatorial formula for the number of different words

I originally posted this question here:
https://math.stackexchange.com/questions/1296199/combinatorial-formula-for-the-number-of-different-words :

I am interested in the asymptotic behaviour of the following quantity:

Suppose we have $m$ distinct letters and we are allowed to use each letter at most $d$ times. What is the number of distinct words of length $k$ that can be formed?

Indeed, one can find a recurrence formula, but I do not quite see how one can find a uniform asymptotic for all $m,d,k.$

Edit: After discussion in the comments, I can reduce my problem to the range, $m\ge k$ and $d\ll m.$

• I misread words in the title as worlds. Too bad. – Włodzimierz Holsztyński May 24 '15 at 21:47
• @Włodzimierz Holsztyński: I am interested in your proposed formulation too:) – sergey May 24 '15 at 22:02
• You will probably need to make more specific assumptions on how $m,d,k$ are (asymptotically) related. – Christian Remling May 24 '15 at 22:17
• Mine would be not so much from another world as off the wall. Your q. is harder than I thought at first. Thus I up-voted it. Now I expect the specialists to answer your question, possibly using some Bernoulli numbers or similar--let me see (let them sweat :-). – Włodzimierz Holsztyński May 24 '15 at 22:18
• For $d$ slightly greater than $k/m$ it is natural to use a multidimensional normal approximation. I don't know whether that is progress for the ranges of values you care about. – Douglas Zare May 24 '15 at 22:25

After rescaling by the number of unrestricted words $m^k$, this asks for the probability that a multinomial distribution with equal probabilities will have largest count at most $d$. This has been studied before.

In this question about tail bounds I gave some coarse estimates, but you might find tergi's answer more helpful, with the references to

Algorithm AS 145: Exact Distribution of the Largest Multinomial Frequency P. R. Freeman Journal of the Royal Statistical Society. Series C (Applied Statistics) Vol. 28, No. 3 (1979), pp. 333-336

Bruce Levin, 1983, "On Calculations Involving the Maximum Cell Frequency."