What is the asymptotic growth of the sequence $$a_n:=\sum_{k\geq 0} 3^k c_{n,k},$$ as $n\rightarrow\infty$, where $c_{n,k}$ denotes the number of integer compositions of $n$ with exactly $k$ many 2s?

A composition of $n$ is a sum $n=c_1+c_2+\cdots+c_p$, with all the $c_i$ positive. The first values of the sequence $a_n$ are $1,1,4,8,22,52,135,\ldots$ (not in the OEIS). [Edit: As pointed out by Somos below, the value 135 is wrong, and must be corrected to 132, and then the sequence is in the OEIS.]

So far, I was only able to prove the following bounds: As $\sum_{k\geq 0}c_{n,k}=2^{n-1}$, it follows that $$2^{n-1}\leq a_n \leq (2\sqrt{3})^n=(3.464...)^n.$$

  • $\begingroup$ Can we say $c_{n,k}=c_{n-2,k-1}k+1)$, and thus produce a recursion? $\endgroup$
    – vidyarthi
    Jun 21, 2019 at 17:05
  • 1
    $\begingroup$ $c_{n,k}$ is the sequence A105114 in the OEIS. $\endgroup$ Jun 21, 2019 at 21:56

1 Answer 1


When corrected, $a_n$ is the OEIS sequence A052528 whose first nine values are $\,1,1,4,8,22,52,132,324,808,\dots\,$ and it has a linear recurrence.

The combinatorial recurrence from its combination definition leads immediately to $$ a_n = 2a_{n-2} + \sum_{k=0}^{n-1} a_k $$ where the $\, 2a_{n-2}\,$ comes from the combination part $2.$ The ordinary generating function is $$ (1 - x)/(1 - 2 x - 2 x^2 + 2 x^3). $$ The growth rate of $\,a_n\,$ depends on the reciprocal of the smallest root $\,\alpha\,$ of $\, 2x^3 -2x^2 -2x +1.$ Thus $\,1/\alpha \approx 2.4811943\,$ so that $\,a_n \propto 1/\alpha^n.$

EDIT: The sequence $\,c_{n,k}\,$ is the triangular OEIS sequence A105114

Triangle read by rows: T(n,k) is the number of compositions of n having exactly k parts equal to 2.

Again, its combination definition leads immediately to $$ c_{n,k} = \sum_{j=1}^n c_{n-j,k-[j=2]} $$ where $\,[j=2] := 1\,$ if $j=2$, else $0$.

  • 1
    $\begingroup$ I think there is also a multiplied constant, the limit of $(1-x/\alpha)\,\mathrm{gf}(x)$ as $x\to\alpha$, which is about 0.56158611. $\endgroup$ Jun 21, 2019 at 19:05
  • $\begingroup$ @BrendanMcKay Yes, I really meant $\propto$ instead of $\sim$. Thanks for your comment. $\endgroup$
    – Somos
    Jun 21, 2019 at 19:17
  • $\begingroup$ Wonderful, thank you! The one mistake in computations I made with 135 instead of 132 spoiled my OEIS search. After entering 1,1,4,8,22,52, there were still several sequences matching, and then after entering 135, none was left. $\endgroup$ Jun 22, 2019 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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