A statistical question I'm studying has led me to the following counting problem: Let $\lambda_j := \binom{j}{2}$. For integers $1 \le q \le n$ and $1 \le b \le \lambda_n$, determine $X[n,q,b]=$ the number of compositions $(i_1,\dots,i_q)$ of $n$ (i.e. $\sum i_j = n$ and $\min_j i_j \ge 1$) such that $\sum_{j=1}^q \lambda_{i_j} = b$.

I can calculate $X[n,q,b]$ by means of the recursion $$X[n,q,b] = \sum_{r=1}^q \binom{q}{r} X[n-q,r,b+q-n]$$ with base cases $$ \begin{align} X[n,n,b] &= \mathbf{1}\{b=0\}\\ X[n,1,b] &= \mathbf{1}\{b=\lambda_n\}\\ X[n,q,b] &= 0,\,q>n\text{ or }b>\lambda_{n-q+1}. \end{align} $$

At each level $n$ of the recursion there are $O(n^3)$ terms to compute, and each one takes $O(n)$ time, so this trying to solve for $X$ in this way becomes prohibitively slow for large $n$.

I'm wondering if there is a way to speed this computation up, particularly if there is any sort of asymptotic (in $n$) approximation possible. The reason I think there might be is that normalizing the sequence $\{X[n,q,b]\}_{b=1}^{\lambda_n}$ by its sum $\binom{n-1}{q-1}$ and smoothing the resulting density a bit shows it to have a nice form that looks something like a gamma density, except with a heavier tail. It would be interesting to understand why. Anyways, any pointers to related literature would be appreciated.

  • 1
    $\begingroup$ So a generating function is $\sum_{n\ge 1\atop b\ge1} X(n,q,b)x^ny^b=\Big(\sum_{i=1}^{\infty}x^iy^{(\!{i\atop 2})}\Big)^q.$ $\endgroup$ – Pietro Majer Feb 18 '17 at 0:44
  • $\begingroup$ $\sum_j \lambda_{i_j} = b$ here is equivalent to $\sum_j i_j^2=2b+n$. $\endgroup$ – Max Alekseyev Feb 18 '17 at 18:17
  • $\begingroup$ In fact, $X[n,q,b]$ can be computed in $O(bnq^2)$ time. $\endgroup$ – Max Alekseyev Feb 18 '17 at 19:57
  • $\begingroup$ @MaxAlekseyev That's right. Since $b$ and $q$ are as large as $O(n^2)$ and $n$, respectively, the whole thing ends up taking at least $O(n^5)$ (there is also the need to use BigNums, so the complexity is actually higher). $\endgroup$ – jth Feb 19 '17 at 13:24

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.