A001638 - OEIS

%I M3351 N1348 #70 Oct 14 2024 12:17:24

%S 4,1,1,4,9,11,16,29,49,76,121,199,324,521,841,1364,2209,3571,5776,

%T 9349,15129,24476,39601,64079,103684,167761,271441,439204,710649,

%U 1149851,1860496,3010349,4870849,7881196,12752041,20633239,33385284,54018521,87403801

%N A Fielder sequence: a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4.

%C For n > 1, a(n) is the number of ways of choosing a subset of vertices of an n-cycle so that every vertex of the n-cycle is adjacent to one of the chosen vertices. (Note that this is not the same as the number of dominating sets of the n-cycle, which is given by A001644.) - _Joel B. Lewis_, Sep 12 2010

%C For n >= 3, a(n) is also the number of total dominating sets in the n-cycle graph. - _Eric W. Weisstein_, Apr 10 2018

%C For n > 0, a(n) is the number of ways to tile a strip of length n with squares, trominos, and quadrominos where the inital tile (of length 1, 3, or 4) can take on 1, 3, or 4 colors respectively. - _Greg Dresden_ and Yuan Shen, Aug 10 2024

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A001638/b001638.txt">Table of n, a(n) for n = 0..1000</a>

%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/fielder.pdf">Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly 6, 1968, 64-70.

%H Fern Gossow, <a href="https://arxiv.org/abs/2410.05678">Lyndon-like cyclic sieving and Gauss congruence</a>, arXiv:2410.05678 [math.CO], 2024. See p. 26.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H Middle European Math Olympiad 2010, Team Problem 3. Available online at <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?t=366470">the Art of Problem Solving</a>. - _Joel B. Lewis_, Sep 12 2010

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotalDominatingSet.html">Total Dominating Set</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Companion_matrix">Companion matrix</a>.

%H A. V. Zarelua, <a href="https://doi.org/10.1007/s11006-006-0090-y">On Matrix Analogs of Fermat's Little Theorem</a>, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no.

%H  6, 2006, pp. 840-855.

%H <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,1).

%F G.f.: (1-x)*(4+x+x^2)/((1+x^2)*(1-x-x^2)).

%F a(n) = L(n) + i^n + (-i)^n, a(2n) = L(n)^2, a(2n+1) = L(2n+1) where L() is Lucas sequence A000032.

%F a(n) = a(n-1) + a(n-3) + a(n-4). - _Eric W. Weisstein_, Apr 10 2018

%F a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 1; 0, 1, 0, 0; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - x - 1. . It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - _Peter Bala_, Jan 08 2023

%p A001638:=-(z+1)*(4*z**2-z+1)/(z**2+z-1)/(z**2+1); # conjectured by _Simon Plouffe_ in his 1992 dissertation; gives sequence except for the initial 4

%t LinearRecurrence[{1, 0, 1, 1}, {4, 1, 1, 4}, 50] (* _T. D. Noe_, Aug 09 2012 *)

%t Table[LucasL[n] + 2 Cos[n Pi/2], {n, 0, 20}] (* _Eric W. Weisstein_, Apr 10 2018 *)

%t CoefficientList[Series[(-4 + 3 x + x^3)/(-1 + x + x^3 + x^4), {x, 0, 20}], x] (* _Eric W. Weisstein_, Apr 10 2018 *)

%o (PARI) a(n)=if(n<0,0,fibonacci(n+1)+fibonacci(n-1)+simplify(I^n+(-I)^n))

%o (PARI) a(n)=if(n<0,0,polsym((1+x-x^2)*(1+x^2),n)[n+1])

%o (Magma) I:=[4,1,1,4]; [n le 4 select I[n] else Self(n-1) + Self(n-3) + Self(n-4): n in [1..30]]; // _G. C. Greubel_, Jan 09 2018

%Y Cf. A000032, A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

%K nonn,easy

%O 0,1

%A _N. J. A. Sloane_

%E Edited by _Michael Somos_, Feb 17 2002 and Nov 02 2002