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 '19 at 17:05
  • 1
    $\begingroup$ $c_{n,k}$ is the sequence A105114 in the OEIS. $\endgroup$ – Freddy Barrera Jun 21 '19 at 21:56

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$ – Brendan McKay Jun 21 '19 at 19:05
  • $\begingroup$ @BrendanMcKay Yes, I really meant $\propto$ instead of $\sim$. Thanks for your comment. $\endgroup$ – Somos Jun 21 '19 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$ – Torsten Mütze Jun 22 '19 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.