0
$\begingroup$

I'm looking for asymptotic bounds (as n goes to infinity) on the number of integer compositions of $n$ with parts in $[a,n]$ and separately for parts in $[a,b]$, with $1 < a < b < n$.

(To clarify, $n$ varies, $a$ and $b$ are fixed)

Relevant results I'm aware of, although not exactly what I'm looking for, are the following:

Jaklič, G., Vitrih, V. & Žagar, E. CLOSED FORM FORMULA FOR THE NUMBER OF RESTRICTED COMPOSITIONS. Bull. Aust. Math. Soc. 81, 289–297 (2010).

Malandro, M. E. Integer compositions with part sizes not exceeding k. arXiv:1108.0337 [math] (2012).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ A lot will depend on how $a$ and $b$ can vary with $n$. What are your requirements? $\endgroup$
    – Brendan McKay
    Commented Feb 9, 2022 at 3:47
  • $\begingroup$ Thanks. $a$ and $b$ are fixed. I'm specifically interested in whether superpolynomial lower bounds can be proven for the case where parts $x_i \in [a, n]$ and for the case where $x_i \in [a,b]$, $x_i$ being the summands in the integer composition. The case where $x_i \in [1, b]$ is already obtained in Malandro (2012). I would also be interested in whether polynomial upper bounds can be proven, if the above is not possible. $\endgroup$
    – blizzard
    Commented Feb 9, 2022 at 11:00

1 Answer 1

Reset to default
2
$\begingroup$

From the generating function: $$\frac1{1-(x^a+x^{a+1}+\dots+x^b)}=\frac{1-x}{1-x-x^a+x^{b+1}}$$ it follows that the number of compositions of $n$ with parts in $[a,b]$ (given by the coefficient of $x^n$) grows proportionally to $|\alpha|^{-n}$, where $\alpha$ is the smallest by absolute value zero of $1-x-x^a+x^{b+1}$.

Improve this answer
$\endgroup$
15
  • 2
    $\begingroup$ @blizzard, the $[a, n]$ case corresponds to g.f. $\frac{1}{1 - (x^a + x^{a+1} + \cdots)} = \frac{1-x}{1-x - x^a}$. Partial fraction decomposition turns a rational function $\frac{P(x)}{Q(x)}$ into a sum of fractions $\frac{P_\alpha(x)}{x - \alpha} = \frac{-\alpha^{-1} P_\alpha(x)}{1 - \alpha^{-1}x} = -\alpha^{-1}P_{\alpha}(x)(1 + \alpha^{-1}x + \alpha^{-2}x^2 + \cdots)$ where the $\alpha$ are the roots of $Q$. $\endgroup$
    – Peter Taylor
    Commented Feb 10, 2022 at 17:24
  • 1
    $\begingroup$ It's pretty standard argument - e.g. see Chapter 5 in the generatingfunctionology book. $\endgroup$
    – Max Alekseyev
    Commented Feb 10, 2022 at 17:26
  • 1
    $\begingroup$ Using the original gf it is easy to see that the complex zero with the smallest absolute value is the smallest positive real zero. $\endgroup$
    – Brendan McKay
    Commented Feb 11, 2022 at 2:51
  • 1
    $\begingroup$ @blizzard: Both Peter and I sum over $k\geq0$, while you sum over $k\geq1$. The extra factor you get does not affect the asymptotic though. $\endgroup$
    – Max Alekseyev
    Commented Feb 14, 2022 at 15:49
  • 1
    $\begingroup$ @blizzard: I'm not sure what mean under "unpacking". Its interpretation is that the coefficient of $x^n$ is big-Theta of $|\alpha|^{-n}$. $\endgroup$
    – Max Alekseyev
    Commented Feb 14, 2022 at 22:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .