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

  • $\begingroup$ 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$? $\endgroup$ – tmp Jul 5 '16 at 17:09
  • $\begingroup$ @tmp what do you mean by $n \ll m$? How much larger is $m$ than $n$? $\endgroup$ – D Poole Jul 5 '16 at 17:25
  • $\begingroup$ 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. $\endgroup$ – tmp Jul 6 '16 at 9:03
  • $\begingroup$ @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. $\endgroup$ – D Poole Jul 6 '16 at 12:31
  • $\begingroup$ 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? $\endgroup$ – tmp Jul 6 '16 at 14:15

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.