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

1, 1, 1, 4, 7, 13, 28, 55, 109, 220, 439, 877, 1756, 3511, 7021, 14044, 28087, 56173, 112348, 224695, 449389, 898780, 1797559, 3595117, 7190236, 14380471, 28760941, 57521884, 115043767, 230087533, 460175068, 920350135, 1840700269, 3681400540

Offset: 0

Author

Philippe Deléham, Sep 20 2006

Keywords

• nonn
• easy

Comments

Equals INVERT transform of (1, 0, 3, 0, 3, 0, 3, ...). - Gary W. Adamson, Apr 27 2009

No term is divisible by 3. - Vladimir Joseph Stephan Orlovsky, Mar 24 2011

For n > 3, a(n) is the number of quaternary sequences of length n-1 starting with q(0) = 0, in which all triples (q(i), q(i+1), q(i+2)) contain digits 0 and 3; cf. A294627. - Wojciech Florek, Jul 30 2018

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 domino. - Greg Dresden and Bora Bursalı, Aug 31 2023

Examples

			It is shown in A294627 that there are 42 quaternary sequences (i.e., build from four digits 0, 1, 2, 3) and having both 0 and 3 in every (consecutive) triple. Only a(5=4+1) = 13 of them start with 0: 003x, 030x, 03y0, 0y30, 0330, where x = 0, 1, 2, 3 and y = 1, 2.
		

Links

• Wojciech Florek, Table of n, a(n) for n = 0..2000
• 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).

Crossrefs

Cf. A294627.

Programs

GAP

a:=[1,1,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+2*a[n-3]; od; a; # Muniru A Asiru, Jul 30 2018

Maple

seq(coeff(series((1-x^2)/(1-x-x^2-2*x^3), x,n+1),x,n),n=0..40); # Muniru A Asiru, Aug 02 2018

Mathematica

LinearRecurrence[{1, 1, 2}, {1, 1, 1}, 40]
CoefficientList[ Series[(x^2 - 1)/(2x^3 + x^2 + x - 1), {x, 0, 35}], x] (* Robert G. Wilson v, Jul 30 2018 *)

PARI

Vec((1-x^2)/(1-x-x^2-2*x^3)+O(x^99)) \\ Charles R Greathouse IV, Jan 17 2012

Sage

from sage.combinat.sloane_functions import recur_gen3; it = recur_gen3(1,1,1,1,1,2); [next(it) for i in range(30)] # Zerinvary Lajos, Jun 25 2008

Formula

a(3*n) = 2*a(3*n-1)+2, a(3*n+1) = 2*a(3*n)-1, a(3*n+2) = 2*a(3*n+1)-1, a(0)=1.

G.f.: (1-x^2)/(1-x-x^2-2*x^3).

a(n) = ((-1)^n*A130815(n+2) + 3*2^n)/7. - R. J. Mathar, Nov 30 2008

From Paul Curtz, Oct 02 2009: (Start)

a(n) = A140295(n+2)/4.

a(n+1) - 2a(n) = period 3: repeat -1,-1,2 = -A061347.

a(n) - a(n-1) = 0,0,3,3,6,15,27,54,111,... = 3*A077947.

a(n) - a(n-2) = 0,3,6,9,21,42,81,....

a(n) - a(n-3) = 3,6,12,24,... = A007283 = 3*A000079.

a(3n) + a(3n+1) + a(3n+2) = 3,24,192,... = A103333(n+1) = A140295(3n) + A140295(3n+1) + A140295(3n+2).

See A078010, A139217, A139218. (End)

Extensions

Corrected by T. D. Noe, Nov 01 2006, Nov 07 2006

Typo in definition corrected by Paul Curtz, Oct 02 2009