Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
$c(m) N^m$ obviously can't be a lower bound, since $N^m/N$ is an upper bound. You can also rule out $c(N) N^m.$ The CLT tells you what to expect. –  Douglas Zare Mar 9 at 14:54

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.