A294627 Expansion of x*(1 + x)/((1-2*x)*(1+x+x^2)).

0, 1, 2, 3, 7, 14, 27, 55, 110, 219, 439, 878, 1755, 3511, 7022, 14043, 28087, 56174, 112347, 224695, 449390, 898779, 1797559, 3595118, 7190235, 14380471, 28760942, 57521883, 115043767, 230087534, 460175067, 920350135, 1840700270, 3681400539, 7362801079, 14725602158, 29451204315

Offset

0,3

Comments

A generalized tribonacci (A001590) sequence.

For n > 2, 6*a(n) is the number of quaternary sequences of length n in which all triples (q(i),q(i+1),q(i+2)) contain two (arbitrarily chosen) digits, e.g., 0 and 3.

Similarly, recurrences a(n) = a(n-1) + a(n-2) + k*a(n-3) are related to binary (k=0, the Fibonacci sequence A000045), ternary (k=1, the tribonacci sequence A001590), quinary (k=3) and so on sequences with all triples (t(i),t(i+1),t(i+2)) containing two (arbitrarily chosen) digits (usually 0 and k+1).

For n > 0, a(n) is the number of ways to tile a strip of length n with squares, dominoes, and two colors of trominoes, with the restriction that the first tile cannot be a tromino. - Greg Dresden and Bora Bursalı, Aug 31 2023

For n > 1, a(n) is the number of ways to tile a strip of length n-2 with squares, dominoes, and two colors of trominoes, where the strip begins with an upper level of two cells. For example, when n=7 we have this strip of length 5:

___

|_|_|_____

|_|_|_|_|_|. - Guanji Chen and Greg Dresden, Jun 17 2024

Links

Wojciech Florek, Table of n, a(n) for n = 0..500

Wojciech Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.

Index entries for linear recurrences with constant coefficients, signature (1,1,2).

Formula

a(n) = a(n-1) + a(n-2) + 2*a(n-3) for n > 2.

a(n+1)/a(n) tends to 2, the unique real root of x^3 - x^2 - x - 2 = 0.

a(n+1) = abs(A078043(n)).

7*a(n) = 3*2^n - A167373(n+1). - R. J. Mathar, Mar 24 2018

E.g.f.: exp(-x/2)*(9*exp(5*x/2) - 9*cos(sqrt(3)*x/2) - sqrt(3)*sin(sqrt(3)*x/2))/21. - Stefano Spezia, Aug 29 2024

Example

For n=4 there are 6*7=42 quaternary sequences of length 4 such that each triple (i.e., exactly two of them: q1,q2,q3 and q2,q3,q4) contain both 0 and 3. They are 003x, 030x, 03y0, 0330, 330x, 303x, 30y3, 3003, 0y30, 3y03, y03x, y30x, where x=0,1,2,3 and y=1,2.

Mathematica

LinearRecurrence[{1, 1, 2}, {0, 1, 2}, 50] (* Paolo Xausa, Aug 28 2024 *)

Prog

(PARI) my(x='x+O('x^99)); concat(0, Vec(x*(1+x)/(1-x-x^2-2*x^3))) \\ Altug Alkan, Mar 03 2018

Crossrefs

Cf. A000045, A001590, A007040, A033129 (partial sums), A078043, A167373.

Sequence in context: A131300 A333342 A078043 * A293326 A308092 A262765

Adjacent sequences: A294624 A294625 A294626 * A294628 A294629 A294630

Keyword

nonn,easy

Author

Wojciech Florek, Feb 12 2018

Status

approved