1
$\begingroup$

If want to know if the following inequality holds for general values of $s \leq n \ll m$.

$$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$

$C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of weak integer compositions of $n$ into $m$ parts (without restriction). In other words, it's the number of ways to distribute $n$ identical objects into $m$ distinct bins.

$C_0(n,m,s) = \sum_{j=0}^m (-1)^j \binom{m}{j}\binom{n+m-j(s+1)-1}{m-1}$ is the number of weak integer compositions of $n$ into $m$ parts with restricted part size $s$. In other words, it's the number of ways to distribute $n$ identical objects into $m$ distinct bins, where each bin has capacity $s$.

$m^n$ is the number of strings of length $n$ over an alphabet of $m$ symbols. In other words, it's the number of ways to distribute $n$ distinct objects into $m$ distinct bins.

$p(n,m,s) = n![z^n]\left(\sum_{j=0}^s \frac{z^j}{k!}\right)^m = \sum\limits_{\substack{k_1 + \cdots + k_m=n\\0\leq k_i \leq s}} \binom{n}{k_1\cdots k_m}$ is the number of strings of length $n$ over an alphabet of $m$ symbols, such that each symbol occurs at most $s$ times in each string. In other words, it's the number of ways to distribute $n$ distinct objects into $m$ distinct bins, where each bin has capacity $s$.

Is this a known combinatorial problem? Does anyone know a source with the proof or disproof? What might be a suitable approach to prove it?

I verified the inequality algorithmically for $2 \leq m \leq 14$ and $1 \leq n \leq \lfloor \frac{m}{2} \rfloor$ and $1 \leq s \leq n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.