OFFSET
0,1
COMMENTS
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
For n >= 3, a(n) is also the number of total dominating sets in the n-cycle graph. - Eric W. Weisstein, Apr 10 2018
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
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
T. D. Noe, Table of n, a(n) for n = 0..1000
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Fern Gossow, Lyndon-like cyclic sieving and Gauss congruence, arXiv:2410.05678 [math.CO], 2024. See p. 26.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Middle European Math Olympiad 2010, Team Problem 3. Available online at the Art of Problem Solving. - Joel B. Lewis, Sep 12 2010
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Wikipedia, Companion matrix.
A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no.
6, 2006, pp. 840-855.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).
FORMULA
G.f.: (1-x)*(4+x+x^2)/((1+x^2)*(1-x-x^2)).
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.
a(n) = a(n-1) + a(n-3) + a(n-4). - Eric W. Weisstein, Apr 10 2018
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
MAPLE
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
MATHEMATICA
LinearRecurrence[{1, 0, 1, 1}, {4, 1, 1, 4}, 50] (* T. D. Noe, Aug 09 2012 *)
Table[LucasL[n] + 2 Cos[n Pi/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 10 2018 *)
CoefficientList[Series[(-4 + 3 x + x^3)/(-1 + x + x^3 + x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 10 2018 *)
PROG
(PARI) a(n)=if(n<0, 0, fibonacci(n+1)+fibonacci(n-1)+simplify(I^n+(-I)^n))
(PARI) a(n)=if(n<0, 0, polsym((1+x-x^2)*(1+x^2), n)[n+1])
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Edited by Michael Somos, Feb 17 2002 and Nov 02 2002
STATUS
approved