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.$
 A: 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."
See also
Robert E. Greenwood and Mark O. Glasgow. Distribution of Maximum and Minimum Frequencies in a Sample Drawn from a Multinomial Distribution Ann. Math. Statist.
Volume 21, Number 3 (1950), 416-424.
Charles J. Corrado
The exact distribution of the maximum, minimum and the range of Multinomial/Dirichlet and Multivariate Hypergeometric frequencies
Statistics and Computing
July 2011, Volume 21, Issue 3, pp 349-359.
