login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
17
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,3
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
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
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)
EXAMPLE
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
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 *)
PROG
(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
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( 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
(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
CROSSREFS
Cf. A195978.
Sequence in context: A195609 A117125 A000692 * A080552 A215176 A063781
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Sep 25 2011
STATUS
approved