# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a001638
Showing 1-1 of 1

%I A001638 M3351 N1348 #73 Feb 16 2025 08:32:24
%S A001638 4,1,1,4,9,11,16,29,49,76,121,199,324,521,841,1364,2209,3571,5776,
%T A001638 9349,15129,24476,39601,64079,103684,167761,271441,439204,710649,
%U A001638 1149851,1860496,3010349,4870849,7881196,12752041,20633239,33385284,54018521,87403801
%N A001638 A Fielder sequence: a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4.
%C A001638 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 A001638 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 A001638 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 A001638 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001638 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001638 T. D. Noe, <a href="/A001638/b001638.txt">Table of n, a(n) for n = 0..1000</a>
%H A001638 Daniel C. Fielder, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/6-3/fielder.pdf">Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly 6, 1968, 64-70.
%H A001638 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 A001638 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 A001638 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A001638 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 A001638 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H A001638 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TotalDominatingSet.html">Total Dominating Set</a>
%H A001638 Wikipedia, <a href="https://en.wikipedia.org/wiki/Companion_matrix">Companion matrix</a>.
%H A001638 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 A001638  6, 2006, pp. 840-855.
%H A001638 <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%H A001638 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,1).
%F A001638 G.f.: (1-x)*(4+x+x^2)/((1+x^2)*(1-x-x^2)).
%F A001638 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 A001638 a(n) = a(n-1) + a(n-3) + a(n-4). - _Eric W. Weisstein_, Apr 10 2018
%F A001638 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 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 A001638 LinearRecurrence[{1, 0, 1, 1}, {4, 1, 1, 4}, 50] (* _T. D. Noe_, Aug 09 2012 *)
%t A001638 Table[LucasL[n] + 2 Cos[n Pi/2], {n, 0, 20}] (* _Eric W. Weisstein_, Apr 10 2018 *)
%t A001638 CoefficientList[Series[(-4 + 3 x + x^3)/(-1 + x + x^3 + x^4), {x, 0, 20}], x] (* _Eric W. Weisstein_, Apr 10 2018 *)
%o A001638 (PARI) a(n)=if(n<0,0,fibonacci(n+1)+fibonacci(n-1)+simplify(I^n+(-I)^n))
%o A001638 (PARI) a(n)=if(n<0,0,polsym((1+x-x^2)*(1+x^2),n)[n+1])
%o A001638 (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 A001638 Cf. A000032, A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.
%K A001638 nonn,easy,changed
%O A001638 0,1
%A A001638 _N. J. A. Sloane_
%E A001638 Edited by _Michael Somos_, Feb 17 2002 and Nov 02 2002

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE