# A Closed Form Lower Bound Approximating $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m$

Here, I found $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m = \sum\limits_{\substack{k_1 + \cdots + k_m=n\\0\leq k_i \leq s}} \frac{n!}{k_1!\cdots k_m!}$ as the number of ways to distribute $n$ distinct objects into $m$ distinct bins, where each bin has capacity $s$.

I'm looking for a closed form lower bound that approximates $p_{n,m,s}$ for $s \leq n \ll m$ and does not involve a generating function.

Note that $p_{n,m,s}$ can be broken into $$p_{n,m,s} = p_{n,m,s}^{1} + p_{n,m,s}^{\geq 2},$$ where $p_{n,m,s}^1$ is the number of ways to distribute $n$ balls into $m$ bins such that each bin has at most 1 ball and $p_{n,m,s}^{\geq 2}$ is the number of ways to distribute these balls so that at least 1 bin has at least 2 balls. Trivially, $p_{n,m,s} \geq p_{n,m,s}^{1}$. Note that $p_{n,m,s}^1 = m (m-1) (m-2) \cdots (m-n+1) = (m)_n$. Hence $$p_{n,m,s} \geq (m)_n.$$
Depending on the nature of $n \ll m$, the main contribution to $p_{n,m,s}$ will come from $p_{n,m,s}^1$. Note that $$p_{n,m,s}^{\geq 2} \leq {m \choose 1} {n \choose 2} (m)^{n-2},$$ where we choose a bin to have at least 2 balls, then choose two balls in this bin; finally, distribute the remaining $n-2$ balls among any bins.
Note that if $n^2/m \to 0$ (as $m \to \infty$), then $$\frac{{m \choose 1} {n \choose 2} (m)^{n-2}}{(m)_n} \leq \frac{n^2}{m} \frac{m^n}{(m)_n} \leq \frac{n^2}{m} \left( \frac{m}{m-n} \right)^n = \frac{n^2}{m} \left( 1 + \frac{n}{m-n}\right)^n \leq \frac{n^2}{m} e^{n^2/(m-n)} \to 0.$$ In this case, $$\frac{p_{n,m,s}}{p_{n,m,s}^1} \to 1.$$ So this lower bound is tight if $n^2/m \to 0$.
• Your answer provides a very interesting insight for the limiting case $n^2/m \rightarrow 0$ (as $m \rightarrow \infty$). However, bounding $p_{n,m,s}$ by $p_{n,m,1}$ might not be that tight for finite $m$. Do you think there is a way to derive a non-trivial bound dependent on $s$? – tmp Jul 5 '16 at 17:09
• @tmp what do you mean by $n \ll m$? How much larger is $m$ than $n$? – D Poole Jul 5 '16 at 17:25
• There is no clear direct connection between $n$ and $m$. You may assume $n \sim \sqrt{m}$. Sorry that my use of $\ll$ is unprecise. – tmp Jul 6 '16 at 9:03
• @tmp I ask because you can get better lower bounds based on how large $n$ is compared to $m$. For instance, if $n \sim \sqrt{m}$, then you can show that $p_{n, m, s}^{\geq 3}/p_{n, m, s} \to 0$ as $m \to \infty$. So a very close lower bound on $p_{n, m, s}$ is those assignments with at most 2 balls per bin. For a fixed $s$, unless $n$ is on the order of at least $m^{1 - 1/s}$, those assignments with at least one bin having $s$ balls will be negligible compared to those without. – D Poole Jul 6 '16 at 12:31
• I guess I see your point. Do you mean (in analogy to your answer) to show $p_{n,m,s}^{\geq 3}/p_{n,m,2} \rightarrow 0$ as $m \rightarrow \infty$? How would I explicitly write the denominator in that case? It should be more complicated than $(m)_n$. Are suggesting to argue that $p_{n,m,s}^{\geq3}/p_{n,m,2} < p_{n,m,s}^{\geq3}/p_{n,m,1}$? Why is $m^{1-1/s}$ critical? – tmp Jul 6 '16 at 14:15