Lower bound for constrained ordered partitions (i.e., compositions)?

Question

An ordered $m$-partition (also called a composition) of an integer $n$ is an ordered sequence of positive integers $a_1, \ldots, a_m$ such that $\sum_i a_i = n$. Such a partition is $N$-constrained if additionally $a_i \leq N$ for all $i$.

Let $p(N, m, n)$ denote the number of $N$-constrained, ordered $m$-partitions of $n$. Bounds on $p(N, m, n)$ are known (see Andrews, "The Theory of Partitions" or Ratsaby, "Estimate of the Number of Restricted Integer Partitions"), however the ones I have seen are given either in terms of generating functions or ugly summations.

I am looking for a closed-form lower bound on $p(N, m, n)$. Is it known that for $n$ in a certain range (depending on $N, m$) it holds that $p(N, m, n) \geq c \cdot N^m$ for some constant $c$?

Answer 1

The geometry behind your problem is that you intersect the $m$-dimensional cube $[0,N]^m$ with the $(m-1)$-dimensional simplex given by the constraints $a_j \ge 0$ and $a_1 + \cdots + a_m = n$. Your question ("$n$ in a certain range") is a bit vague, but from this geometric point of view, the power $m$ of your lower bound seems to be too big. I could certainly get you a lower bound $c \cdot N^{m-1}$ if you choose the range for $n$ carefully enough.

Answer 2

For my answer, I assume that compositions are on non-negative numbers (allowing only positive numbers does not change my statements, qualitatively). First, observe that $p(N,m,n)=\binom{m}{n}_{N+1}$, where $\binom{m}{n}_{N+1}$ is a generalized, or extended, binomial coefficient (so there you have an exact formula, not only a lower bound). Since $\binom{m}{n}_A\ge \binom{m}{n}_B$ if and only if $A\ge B$, a (very weak) lower bound for $p(N,m,n)$ is $\binom{m}{n}$, the ordinary binomial coefficient.

However, much better lower bounds can be obtained by noting that $\binom{m}{n}_{N+1}$ arises as the distribution of the sum of $m$ iid random variables, uniformly distributed on $\{0,\ldots,N\}$. Then apply the central limit theorem (or a variant of the DeMoivre-Laplace theorem) to get nice bounds ...