# Count weighted integer compositions

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

• Can we say $c_{n,k}=c_{n-2,k-1}k+1)$, and thus produce a recursion? – vidyarthi Jun 21 at 17:05
• $c_{n,k}$ is the sequence A105114 in the OEIS. – Freddy Barrera Jun 21 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$$.

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