|
%I #52 Aug 24 2022 10:02:18
%S 0,1,3,4,5,9,16,25,39,64,105,169,272,441,715,1156,1869,3025,4896,7921,
%T 12815,20736,33553,54289,87840,142129,229971,372100,602069,974169,
%U 1576240,2550409,4126647,6677056,10803705,17480761,28284464,45765225
%N 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.
%C 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.
%C Column 1 of A195978.
%C a(n) is the number of total dominating sets in the (n+1)-path graph. - _Eric W. Weisstein_, Apr 10 2018
%C 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
%C From _Wajdi Maaloul_, Jun 23 2022: (Start)
%C 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):
%C _ _ _ _
%C |_| _|_| _|_|_ _ _|_|_
%C |_| |_|_| |_|_|_| |_|_|_|_|
%C |_| |_| |_| |_|
%C (End)
%H R. H. Hardin, <a href="/A195971/b195971.txt">Table of n, a(n) for n = 0..200</a> (corrected by _R. H. Hardin_, Jan 19 2019)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotalDominatingSet.html">Total Dominating Set</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,1).
%F a(n) = a(n-1) + a(n-3) + a(n-4).
%F G.f.: x*(1 + x)^2 / ((1 + x^2)*(1 - x - x^2)). - _Colin Barker_, Feb 17 2018
%F a(n) = (A000032(n + 3) - 2*sin(n*Pi/2) - 4*cos(n*Pi/2))/5. - _Eric W. Weisstein_, Apr 10 2018
%F a(n) = (Lucas(n+3) - (-1)^(floor(n/2))*(3+(-1)^n))/5. - _G. C. Greubel_, Apr 03 2019
%F From _Wajdi Maaloul_, Jun 23 2022: (Start)
%F a(2n) = A226205(n+1) = - A121646(n+1) = Fibonacci(n+1)^2 - Fibonacci(n)^2 = Fibonacci(n+2)*Fibonacci(n-1);
%F a(2n+1) = Fibonacci(n+2)^2 = A007598(n+2).
%F (End)
%e All solutions for n=4:
%e 0 0 1 1 0
%e 0 0 0 0 1
%e 0 0 0 0 1
%e 1 0 1 0 0
%t Table[(LucasL[n + 3] - 2 Sin[n Pi/2] - 4 Cos[n Pi/2])/5, {n, 0, 40}] (* _Eric W. Weisstein_, Apr 10 2018 *)
%t 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 *)
%t CoefficientList[Series[x*(1+x)^2/(1-x-x^3-x^4), {x, 0, 40}], x] (* _Eric W. Weisstein_, Apr 10 2018 *)
%o (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
%o (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
%o (Sage) (x*(1+x)^2/(1-x-x^3-x^4)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Apr 03 2019
%o (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
%Y Cf. A195978.
%K nonn,easy
%O 0,3
%A _R. H. Hardin_, Sep 25 2011
|
