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

218 Views Asked by At

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.

1

There are 1 best solutions below

6
On BEST ANSWER

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