1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ $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. $\endgroup$ Mar 9, 2014 at 14:54

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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