A195971 Number of n X 1 0..4 arrays with each element x equal to the number its horizontal and vertical neighbors equal to 2,0,1,3,4 for x=0,1,2,3,4.

0, 1, 3, 4, 5, 9, 16, 25, 39, 64, 105, 169, 272, 441, 715, 1156, 1869, 3025, 4896, 7921, 12815, 20736, 33553, 54289, 87840, 142129, 229971, 372100, 602069, 974169, 1576240, 2550409, 4126647, 6677056, 10803705, 17480761, 28284464, 45765225

Offset: 0

Author

R. H. Hardin, Sep 25 2011

Keywords

• nonn
• easy

Comments

Every 0 is next to 0 2's, every 1 is next to 1 0's, every 2 is next to 2 1's, every 3 is next to 3 3's, every 4 is next to 4 4's.

Column 1 of A195978.

a(n) is the number of total dominating sets in the (n+1)-path graph. - Eric W. Weisstein, Apr 10 2018

Equivalently, a(n) is the number of 0-1 sequences (every term is "0" or "1") of length n+1 whose every term is adjacent to a term "1". - Yuda Chen, Apr 06 2022

From Wajdi Maaloul, Jun 23 2022: (Start)

For n > 1, a(n) is the number of ways to tile the figure below using squares and dominoes: a horizontal strip of length n-1 that contains a central vertical strip of length 3. Below are figures for a(2) through a(5):

|| |_| ||_ |_|_

|| ||_| |||_| |||_|_|

|| || || ||

(End)

a(n) is the number of compositions of n+2 with 1's, 3's and 4's, with the restriction that you cannot begin with two 1's. - Greg Dresden and Yuan Shen, Aug 10 2024

Examples

			All solutions for n=4:
  0   0   1   1   0
  0   0   0   0   1
  0   0   0   0   1
  1   0   1   0   0
		

Links

• R. H. Hardin, Table of n, a(n) for n = 0..200 (corrected by _R. H. Hardin_, Jan 19 2019)
• Eric Weisstein's World of Mathematics, Path Graph
• Eric Weisstein's World of Mathematics, Total Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Crossrefs

Cf. A195978.

Programs

GAP

a:=[1,3,4,5];; for n in [5..40] do a[n]:=a[n-1]+a[n-3]+a[n-4]; od; Concatenation([0], a); # G. C. Greubel, Apr 03 2019

Magma

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1+x)^2/(1-x-x^3-x^4) )); // G. C. Greubel, Apr 03 2019

Mathematica

Table[(LucasL[n + 3] - 2 Sin[n Pi/2] - 4 Cos[n Pi/2])/5, {n, 0, 40}] (* Eric W. Weisstein, Apr 10 2018 *)
LinearRecurrence[{1, 0, 1, 1}, {0, 1, 3, 4, 5}, 40] (* Eric W. Weisstein, Apr 10 2018; amended for a(0) by Georg Fischer, Apr 03 2019 *)
CoefficientList[Series[x*(1+x)^2/(1-x-x^3-x^4), {x, 0, 40}], x] (* Eric W. Weisstein, Apr 10 2018 *)

PARI

my(x='x+O('x^40)); concat([0], Vec(x*(1+x)^2/(1-x-x^3-x^4))) \\ G. C. Greubel, Apr 03 2019

Sage

(x*(1+x)^2/(1-x-x^3-x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 03 2019

Formula

a(n) = a(n-1) + a(n-3) + a(n-4).

G.f.: x*(1 + x)^2 / ((1 + x^2)*(1 - x - x^2)). - Colin Barker, Feb 17 2018

a(n) = (A000032(n + 3) - 2*sin(n*Pi/2) - 4*cos(n*Pi/2))/5. - Eric W. Weisstein, Apr 10 2018

a(n) = (Lucas(n+3) - (-1)^(floor(n/2))*(3+(-1)^n))/5. - G. C. Greubel, Apr 03 2019

From Wajdi Maaloul, Jun 23 2022: (Start)

a(2n) = A226205(n+1) = - A121646(n+1) = Fibonacci(n+1)^2 - Fibonacci(n)^2 = Fibonacci(n+2)*Fibonacci(n-1);

a(2n+1) = Fibonacci(n+2)^2 = A007598(n+2).

(End)