# Sums of reciprocals of products of factorials

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.

• If you multiply by $d!$ you are summing multinational coefficients. There should be a ton of information about sums of binomial/multinational coefficients. – Daniel Parry Oct 17 '15 at 20:34
• 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!)$. – Lucia Oct 17 '15 at 22:01

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