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

4, 1, 1, 4, 9, 11, 16, 29, 49, 76, 121, 199, 324, 521, 841, 1364, 2209, 3571, 5776, 9349, 15129, 24476, 39601, 64079, 103684, 167761, 271441, 439204, 710649, 1149851, 1860496, 3010349, 4870849, 7881196, 12752041, 20633239, 33385284, 54018521, 87403801

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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.
• Middle European Math Olympiad 2010, Team Problem 3. Available online at the Art of Problem Solving. - _Joel B. Lewis_, Sep 12 2010
• 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
• 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 to sequences related to Olympiads.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Crossrefs

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

Programs

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

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 *)

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])

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

Extensions

Edited by Michael Somos, Feb 17 2002 and Nov 02 2002