7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I misread words in the title as worlds. Too bad. $\endgroup$ – Włodzimierz Holsztyński May 24 '15 at 21:47
  • $\begingroup$ @Włodzimierz Holsztyński: I am interested in your proposed formulation too:) $\endgroup$ – sergey May 24 '15 at 22:02
  • $\begingroup$ You will probably need to make more specific assumptions on how $m,d,k$ are (asymptotically) related. $\endgroup$ – Christian Remling May 24 '15 at 22:17
  • $\begingroup$ 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 :-). $\endgroup$ – Włodzimierz Holsztyński May 24 '15 at 22:18
  • 2
    $\begingroup$ 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. $\endgroup$ – Douglas Zare May 24 '15 at 22:25
3
$\begingroup$

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.

$\endgroup$

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.