6
$\begingroup$

Let $d,m, r$ be positive integers, and define $$ S = \left\{ (i_1, i_2, \dots, i_m) \in {\bf Z}_{+}^{m} \left | \sum_j i_j = d; \& \forall j, i_j \leq r \right. \right\}; $$ Here ${\bf Z}_+$ denotes the set of nonnegative integers (that is, including zero). So we are taking all (ordered) integer partitions of $d$ with $m$ constituents (permitting zero as a constituent), with the constituents bounded above by r.

I would like a good upper bound (in terms of $m$, $d$, and $r$) for $$ \sum_{(i_j) \in S} \frac 1{i_1! \cdot i_2! \cdot \dots \cdot i_m!}. $$ When there is no $r$ condition (e.g., if $r \geq d$), then it looks like the sum is exactly $m^d/d!$, arising from representing $m^d$ as a combination of descending products. And of course, if $mr < d$, then there are no terms.

However, I am most interested in the case when $d$ is less than $mr$ (special cases: if $d = mr-1, mr-2, mr-3, mr-4, $, etc.; exact results are easily obtained). But I would like a general result or a reference for this type of problem (with $d$ much less than $mr$); this must have been considered before.

$\endgroup$
2
  • 3
    $\begingroup$ If you multiply by $d!$ you are summing multinational coefficients. There should be a ton of information about sums of binomial/multinational coefficients. $\endgroup$ Oct 17, 2015 at 20:34
  • $\begingroup$ Your problem is closely related to the problem of Elkies on the Coupon collector's earworm. (see mathoverflow.net/questions/215664/the-coupon-collectors-earworm) In particular see Theorem 1 in the paper linked in the accepted answer to that question. That will give ranges of $r$ where the answer is asymptotic to $m^d/d!$ and the range in which it is $o(m^d/d!)$. $\endgroup$
    – Lucia
    Oct 17, 2015 at 22:01

2 Answers 2

6
$\begingroup$

I'll just make my comment above an answer. The sum in question multiplied by $d!/m^d$ can be interpreted as the probability that when $d$ balls are thrown into $m$ boxes then each box contains no more than $r$ balls (the balls are thrown into boxes at random uniformly and independently).

This problem arose earlier on MathOverflow in connection with Elkies's coupon collector's earworm question. From the answer there, I link the paper by Raab and Steger, and Theorem 1 there gives information on the behavior of this probability (or equivalently of your sum). There is a sharp range of $r$ in which the sum transitions from $o(m^d/d!)$ to $(1-o(1))m^d/d!$.

$\endgroup$
4
$\begingroup$

What you have is the coefficient of $x^d$ in $f(x)^m$, where $f(x) = \sum_{j=0}^r x^j/j!$. This is the sort of problem for which the saddle-point method works readily. For sure it has all been worked out before, but I don't remember where.

You can usually get the right answer by a probabilistic device. For any $\alpha>0$, $f(\alpha x)/f(\alpha)$ is the probability generating function for a random variable $X$, so $f(\alpha x)^m/f(\alpha)^m$ is the pgf for the sum of $m$ independent copies of $X$. Choose $\alpha$ so that the mean of $X$ is about $d/m$; this involves solving some nonlinear equation but there is no escape since the solution really appears in the answer. Then apply the central limit theorem (say Berry-Esseen) to the sum of $m$ copies of $X$, together with the fact that the sequence is log-concave, to estimate the coefficient of $x^d$. It should be possible to get precise asymptotics over the full range (perhaps with ad hoc methods at the extremes).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.