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
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).
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
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Sep 25 2011
STATUS
approved