A001638 -id:A001638 - cp's OEIS frontend

A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.

3, 1, 3, 7, 11, 21, 39, 71, 131, 241, 443, 815, 1499, 2757, 5071, 9327, 17155, 31553, 58035, 106743, 196331, 361109, 664183, 1221623, 2246915, 4132721, 7601259, 13980895, 25714875, 47297029, 86992799, 160004703, 294294531, 541292033, 995591267, 1831177831

Offset: 0

N. J. A. Sloane

For n >= 3, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain three consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(3)=7 because only the sequences 110, 101, 011, 001, 010, 100 and 000 avoid three consecutive ones. (For n=1,2 the statement is still true provided we allow the sequence to wrap around itself on a circle.) - Petros Hadjicostas, Dec 16 2016
For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - Eric W. Weisstein, Mar 30 2017
For n >= 3, also the number of minimal dominating sets and maximal irredundant sets on the n-sun graph. - Eric W. Weisstein, Jul 28 and Aug 17 2017
For n >= 3, also the number of minimal edge covers in the n-web graph. - Eric W. Weisstein, Aug 03 2017
For n >= 1, also the number of ways to tile a bracelet of length n with squares, dominoes, and trominoes. - Ruijia Li and Greg Dresden, Sep 14 2019
If n is prime, then a(n)-1 is a multiple of n ; a counterexample for the converse is given by n = 182. - Robert FERREOL, Apr 03 2024

			G.f. = 3 + x + 3*x^2 + 7*x^3 + 11*x^4 + 21*x^5 + 39*x^6 + 71*x^7 + 131*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
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).

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 1..200 from T. D. Noe)
Kunle Adegoke, Robert Frontczak, and Taras Goy, Binomial Tribonacci Sums, Disc. Math. Lett. (2022) Vol. 8, 30-37.
Kunle Adegoke, Adenike Olatinwo, and Winning Oyekanmi, New Tribonacci Recurrence Relations and Addition Formulas, arXiv:1811.03663 [math.CO], 2018.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, On Identities Of Ruggles, Horadam, Howard, and Young, Preprint, 2016.
Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, On identities of Ruggles, Hradam, Howard, and Young, The Fibonacci Quarterly, 55.5 (2017), 42-65.
M. Elia, Derived Sequences, The Tribonacci Recurrence and Cubic Forms, The Fibonacci Quarterly, 39.2 (2001), 107-109.
G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.
G. Everest, Y. Puri and T. Ward, Integer sequences counting periodic points, arXiv:math/0204173 [math.NT], 2002.
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Robert Frontczak, Sums of Tribonacci and Tribonacci-Lucas Numbers, International Journal of Mathematical Analysis, Vol. 12 (2018), No. 1, pp. 19-24.
Robert Frontczak, Convolutions for Generalized Tribonacci Numbers and Related Results, International Journal of Mathematical Analysis (2018) Vol. 12, Issue 7, 307-324.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
A. Ilic, S. Klavzar, and Y. Rho, Generalized Lucas Cubes, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,...
Günter Köhler, Generating functions of Fibonacci-like sequences and decimal expansion of some fractions, The Fibonacci Quarterly 23, no.1, (1985), 29-35 [a(n) is there Lambda_n on p. 35].
Pin-Yen Lin, De Moivre type identities for the Tribonacci numbers, The Fibonacci Quarterly 26, no.2, (1988), 131-134.
Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 21.
J. Pan, Some Properties of the Multiple Binomial Transform and the Hankel Transform of Shifted Sequences, J. Int. Seq. 14 (2011) # 11.3.4, remark 17.
Andreas N. Philippou and Spiros D. Dafnis, A simple proof of an identity generalizing Fibonacci-Lucas identities, Fibonacci Quarterly (2018) Vol. 56, No. 4, 334-336.
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
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Souvik Roy, Nazim Fatès, and Sukanta Das, Reversibility of Elementary Cellular Automata with fully asynchronous updating: an analysis of the rules with partial recurrence, hal-04456320 [nlin.CG], [cs], 2024. See p. 17.
S. Saito, T. Tanaka, and N. Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, J. Int. Seq. 14 (2011) # 11.2.4, Table 3.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Lucas n-Step Number
Eric Weisstein's World of Mathematics, Maximal Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Edge Cover
Eric Weisstein's World of Mathematics, Sun Graph
Eric Weisstein's World of Mathematics, Tribonacci Number
Eric Weisstein's World of Mathematics, Web Graph
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.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums).
Cf. A058265.
Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

a:=[3,1,3];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # Muniru A Asiru, Dec 18 2018

a001644 n = a001644_list !! n
a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+))
               a001644_list (tail a001644_list) (drop 2 a001644_list)
-- Reinhard Zumkeller, Apr 13 2014

I:=[3,1,3]; [n le 3 select I[n] else Self(n-1)+Self(n-2)+ Self(n-3): n in [1..40]]; // Vincenzo Librandi, Aug 04 2017

A001644:=-(1+2*z+3*z**2)/(z**3+z**2+z-1); # Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 3
A001644 :=proc(n)
    option remember;
    if n <= 2 then
        1+2*modp(n+1,2)
    else
        procname(n-1)+procname(n-2)+procname(n-3);
    end if;
end proc:
seq(A001644(n),n=0..80) ;

a[x_]:= a[x] = a[x-1] +a[x-2] +a[x-3]; a[0] = 3; a[1] = 1; a[2] = 3; Array[a, 40, 0]
a[n_]:= n*Sum[Sum[Binomial[j, n-3*k+2*j]*Binomial[k, j], {j,n-3*k,k}]/k, {k, n}]; a[0] = 3; Array[a, 40, 0] (* Robert G. Wilson v, Feb 24 2011 *)
LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)
Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* Eric W. Weisstein, Mar 30 2017 *)
RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* Eric W. Weisstein, Aug 17 2017 *)

{a(n) = if( n<0, polsym(1 - x - x^2 - x^3, -n)[-n+1], polsym(1 + x + x^2 - x^3, n)[n+1])}; /* Michael Somos, Nov 02 2002 */

my(x='x+O('x^40)); Vec((3-2*x-x^2)/(1-x-x^2-x^3)) \\ Altug Alkan, Apr 19 2018

((3-2*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Mar 22 2019

Binet's formula: a(n) = r1^n + r2^n + r3^n, where r1, r2, r3 are the roots of the characteristic polynomial 1 + x + x^2 - x^3, see A058265.
a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2).
G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - Miklos Kristof, Jul 29 2002
a(n) = n*Sum_{k=1..n} Sum_{j=n-3*k..k} binomial(j, n-3*k+2*j)*binomial(k,j)/k, n > 0, a(0)=3. - Vladimir Kruchinin, Feb 24 2011
a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3. - Harvey P. Dale, Feb 01 2015
a(n) = A073145(-n). for all n in Z. - Michael Somos, Dec 17 2016
Sum_{k=0..n} k*a(k) = (n*a(n+3) - a(n+2) - (n+1)*a(n+1) + 4)/2. - Yichen Wang, Aug 30 2020
a(n) = Trace(M^n), where M = [0, 0, 1; 1, 0, 1; 0, 1, 1] is the companion matrix to the monic polynomial x^3 - x^2 - 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, Dec 29 2022

Edited by Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A001254 Squares of Lucas numbers.

Original entry on oeis.org

4, 1, 9, 16, 49, 121, 324, 841, 2209, 5776, 15129, 39601, 103684, 271441, 710649, 1860496, 4870849, 12752041, 33385284, 87403801, 228826129, 599074576, 1568397609, 4106118241, 10749957124, 28143753121, 73681302249, 192900153616, 505019158609, 1322157322201, 3461452808004, 9062201101801, 23725150497409

Offset: 0

N. J. A. Sloane

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 36, 60.
J. M. Borwein and P. B. Borwein, Pi and the AGM, Wiley, 1987, p. 97.
Thomas Koshy, "Fibonacci and Lucas Numbers and Applications", Wiley, New York, 2001. [Note that Identity 34.7 on page 404 is wrong. - Alonso del Arte, Sep 07 2010]

G. C. Greubel, Table of n, a(n) for n = 0..2375 (terms 0..200 from T. D. Noe)
Mohammad K. Azarian, Identities Involving Lucas or Fibonacci and Lucas Numbers as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 45, 2012, pp. 2221-2227.
Tanya Khovanova, Recursive Sequences
T. Mansour, A note on sum of k-th power of Horadam's sequence, arXiv:math/0302015 [math.CO], 2003.
P. Stanica, Generating functions, weighted and non-weighted sums for powers of second-order recurrence sequences, arXiv:math/0010149 [math.CO], 2000.
Index entries for linear recurrences with constant coefficients, signature (2,2,-1).

Cf. A000032, A000204.
Cf. A007598, A079291.
With alternating signs, cf. A075150.
Bisection of A001638 and A006499. First differences of A005970.
Second row of array A103324.

[ Lucas(n)^2 : n in [0..120]]; // Vincenzo Librandi, Apr 14 2011

with(combinat):seq(5*fibonacci(n)^2+4*(-1)^n, n=0..26)

Table[LucasL[n]^2, {n, 0, 29}] (* Alonso del Arte, Apr 11 2011 *)
LinearRecurrence[{2, 2, -1}, {4, 1, 9}, 33] (* Jean-François Alcover, Jan 07 2019 *)

a(n)=5*fibonacci(n)^2 + 4*(-1)^n \\ Charles R Greathouse IV, Sep 24 2015

from sympy import lucas
def a(n):  return lucas(n)**2
print([a(n) for n in range(33)]) # Michael S. Branicky, Apr 01 2021

a(n) = A000032(n)^2.
G.f.: ( 4-7*x-x^2 ) / ( (1+x)*(x^2-3*x+1) ). - Len Smiley, Nov 30 2001
From Ralf Stephan, Feb 08 2003: (Start)
a(n) = r^n + (1/r)^n + 2*(-1)^n, with r=(3+sqrt(5))/2.
a(n+3) = 2*a(n+2) + 2*a(n+1) - a(n). (End)
a(n) = L(2*n) + 2*(-1)^n = L(n-1)*L(n+1) + 5(-1)^n.
a(n) = 5*Fibonacci(n)^2 + 4*(-1)^n.
a(n) + a(n+1) = A106729(n). - R. J. Mathar, Nov 17 2011
E.g.f.: 2*exp(-x)*(exp(5*x/2)*cosh(sqrt(5)*x/2)+1). - Wolfdieter Lang, Jan 14 2012
a(n) = 1/4*( a(n-2) - a(n-1) - a(n+1) + a(n+2) ). The same recurrence holds for A007598. - Peter Bala, Aug 18 2015
For n>1, a(n)=(10*F(2*n-1) + 2*L(n-2)*L(n+1))/4 where F(n)=A000045(n), L(n)=A000204(n). - J. M. Bergot, Nov 25 2015
a(n) = (L(n-2)*L(n+2) + L(n-1)*L(n+1))/2 with L(k)=A000032(k). - J. M. Bergot, May 25 2017
From Peter Bala, Nov 13 2019: (Start)
Sum_{n >= 1} 1/a(n) = (1/8)*( theta_3(beta)^4 - 1 ) = A105394, where beta = (3 - sqrt(5))/2 and theta_3(q) = 1 + 2*Sum_{n >= 1} q^(n^2) is a theta function. See Borwein and Borwein, Exercise 7(f), p. 97.
Sum_{n >= 1} 1/(a(n) - 5) = (3 - sqrt(5))/6; Sum_{n >= 1} (-1)^n/(a(n) - 5) = (15 - sqrt(5))/30; Sum_{n >= 1} 1/(a(2*n) - 5) = (5 - sqrt(5))/10.
Sum_{n >= 1} 1/(a(n) - 25/a(n)) = 2/9.
Conjecture: Sum_{n >= 1} 1/(a(n) - 5*(-1)^n*F(2*k+1)^2) = 1/(2*a(2*k+1)) for k = 0,1,2,.... (End)
a(n) = 3*a(n-1) - a(n-2) + 10*(-1)^n. - Greg Dresden, May 18 2020

A111569 a(n) = a(n-1) + a(n-3) + a(n-4) for n > 3, a(0) = -1, a(1) = 1, a(2) = 2, a(3) = 1.

Original entry on oeis.org

-1, 1, 2, 1, 1, 4, 7, 9, 14, 25, 41, 64, 103, 169, 274, 441, 713, 1156, 1871, 3025, 4894, 7921, 12817, 20736, 33551, 54289, 87842, 142129, 229969, 372100, 602071, 974169, 1576238, 2550409, 4126649, 6677056, 10803703, 17480761, 28284466, 45765225

Offset: 0

Creighton Dement, Aug 07 2005

In reference to the program code given, 4*tesseq[A*H] = A001638 (a Fielder sequence) where A001638(2n) = L(n)^2. Here we have: a(2n+1) = A007598(n+1) = Fibonacci(n+1)^2.
Floretion Algebra Multiplication Program, FAMP Code: 4kbaseiseq[B+H] with B = - .25'i + .25'j - .25i' + .25j' + k' - .5'kk' - .25'ik' - .25'jk' - .25'ki' - .25'kj' - .5e and H = + .75'ii' + .75'jj' + .75'kk' + .75e
First bisection is A260259 (see previous comment for the second bisection). [Bruno Berselli, Nov 02 2015]

Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Robert Munafo, Sequences Related to Floretions.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 1, 1).

Cf. A000045, A001638, A007598, A111570, A111571, A111572, A111573, A260259.

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

a(n) = 2*A056594(n+3)/5 - 6*A056594(n)/5 + A000032(n+1)/5. [R. J. Mathar, Nov 12 2009]

A111573 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 0,1,3,3.

Original entry on oeis.org

0, 1, 3, 3, 4, 8, 14, 21, 33, 55, 90, 144, 232, 377, 611, 987, 1596, 2584, 4182, 6765, 10945, 17711, 28658, 46368, 75024, 121393, 196419, 317811, 514228, 832040, 1346270, 2178309, 3524577, 5702887, 9227466, 14930352, 24157816, 39088169

Offset: 0

Creighton Dement, Aug 10 2005

See comment and FAMP code for A111569.

Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A001638, A111569, A111570, A111571, A111572, A111574, A111575, A111576.

Table[Fibonacci[n + 1] - Cos[n*Pi/2], {n, 0, 40}] (* Greg Dresden, Oct 16 2021 *)

G.f.: -x*(1+2*x)/((x^2+x-1)*(x^2+1)).
a(n) = A056594(n+3) + A000045(n+1). - R. J. Mathar, Nov 10 2009
From Greg Dresden, Jan 15 2024: (Start)
a(2*n) = Fibonacci(n)*Lucas(n+1);
a(2*n+1) = Fibonacci(2*n+1). (End)

Name clarified by Robert C. Lyons, Feb 06 2025

A111570 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 2,5,4,7.

Original entry on oeis.org

2, 5, 4, 7, 14, 23, 34, 55, 92, 149, 238, 385, 626, 1013, 1636, 2647, 4286, 6935, 11218, 18151, 29372, 47525, 76894, 124417, 201314, 325733, 527044, 852775, 1379822, 2232599, 3612418, 5845015, 9457436, 15302453, 24759886

Offset: 0

Creighton Dement, Aug 10 2005

See comment and FAMP code for A111569.

Floretion Algebra Multiplication Program, FAMP Code: 1vesseq[B+H] with B = - .25'i + .25'j - .25i' + .25j' + k' - .5'kk' - .25'ik' - .25'jk' - .25'ki' - .25'kj' - .5e and H = + .75'ii' + .75'jj' + .75'kk' + .75e

Index entries for linear recurrences with constant coefficients, signature (1, 0, 1, 1).

Cf. A001638, A111569, A111571, A111572, A111573, A007598, A000045.

G.f.: (-2-3*x+x^2-x^3)/((1+x^2)*(x^2+x-1)).

Name clarified by Robert C. Lyons, Feb 06 2025

A111571 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 1,1,-2,-1.

Original entry on oeis.org

1, 1, -2, -1, 1, 0, -3, -3, -2, -5, -11, -16, -23, -39, -66, -105, -167, -272, -443, -715, -1154, -1869, -3027, -4896, -7919, -12815, -20738, -33553, -54287, -87840, -142131, -229971, -372098, -602069, -974171, -1576240, -2550407, -4126647, -6677058, -10803705

Offset: 0

Creighton Dement, Aug 10 2005

See comment and FAMP code for A111569.

Floretion Algebra Multiplication Program, FAMP Code: 1jesseq[B+H] with B = - .25'i + .25'j - .25i' + .25j' + k' - .5'kk' - .25'ik' - .25'jk' - .25'ki' - .25'kj' - .5e and H = + .75'ii' + .75'jj' + .75'kk' + .75e

Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A001638, A111569, A111570, A111572, A111573, A007598, A000045.

LinearRecurrence[{1,0,1,1},{1,1,-2,-1},40] (* or *) CoefficientList[ Series[ (-1+3*x^2)/((1+x^2)*(x^2+x-1)),{x,0,40}],x]  (* Harvey P. Dale, Apr 23 2011 *)

G.f.: (-1+3*x^2)/((1+x^2)*(x^2+x-1)).

Name clarified by Robert C. Lyons, Feb 06 2025

A111572 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms -1,3,2,1.

Original entry on oeis.org

-1, 3, 2, 1, 3, 8, 11, 15, 26, 45, 71, 112, 183, 299, 482, 777, 1259, 2040, 3299, 5335, 8634, 13973, 22607, 36576, 59183, 95763, 154946, 250705, 405651, 656360, 1062011, 1718367, 2780378, 4498749, 7279127, 11777872, 19056999, 30834875, 49891874, 80726745

Offset: 0

Creighton Dement, Aug 10 2005

See comment and FAMP code for A111569.
Floretion Algebra Multiplication Program, FAMP Code: 4ibaseseq[B+H] with B = - .25'i + .25'j - .25i' + .25j' + k' - .5'kk' - .25'ik' - .25'jk' - .25'ki' - .25'kj' - .5e and H = + .75'ii' + .75'jj' + .75'kk' + .75e
From Greg Dresden and Jiaqi Wang, Jun 24 2023: (Start)
For n >= 5, a(n) is also the number of ways to tile this "central staircase" figure of length n-2 with squares and dominoes. This is the picture for length 9; there are a(11)=112 ways to tile it:
             _
   _______|_|___
  |||_|||_|||_|
        |_|            (End)

Index entries for linear recurrences with constant coefficients, signature (1, 0, 1, 1).

Cf. A001638, A111569, A111570, A111571, A111573, A111574, A111575, A111576.

Cf. A000032, A000045.

G.f.: (1-4*x+x^2)/((1+x^2)*(x^2+x-1))
From Greg Dresden and Jiaqi Wang, Jun 24 2023: (Start)
a(2*n) = F(n+1)*L(n-1) + F(n)*F(n-1),
a(2*n+1) = F(n+1)*(F(n+1) + 2*F(n-1)), for F(n) and L(n) the Fibonacci and Lucas numbers.
(End)

Name clarified by Robert C. Lyons, Feb 06 2025

A300738 Number of minimal total dominating sets in the n-cycle graph.

Original entry on oeis.org

0, 0, 3, 4, 5, 9, 7, 4, 12, 25, 22, 25, 39, 49, 68, 100, 119, 144, 209, 289, 367, 484, 644, 841, 1130, 1521, 1983, 2601, 3480, 4624, 6107, 8100, 10717, 14161, 18807, 24964, 33004, 43681, 57918, 76729, 101639, 134689, 178364, 236196, 313007, 414736, 549289

Offset: 1

Andrew Howroyd, Apr 15 2018

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Cycle Graph.
Eric Weisstein's World of Mathematics, Minimal Total Dominating Set.
Index entries for linear recurrences with constant coefficients, signature (0,0,1,1,1,1,0,-1,-1).

Cf. A001608, A001638 (total dominating sets), A253413, A302653, A302655, A302918.

Table[RootSum[-1 - # + #^3 &, #^n &] + (1 + (-1)^n) RootSum[-1 + #^2 + #^3 &, #^(n/2) &], {n, 20}]
Perrin[n_] := RootSum[-1 - # + #^3 &, #^n &]; Table[With[{b = Mod[n, 2, 1]}, Perrin[n/b]^b], {n, 20}]
LinearRecurrence[{0, 0, 1, 1, 1, 1, 0, -1, -1}, {0, 0, 3, 4, 5, 9, 7, 4, 12}, 20]
CoefficientList[Series[x^2 (3 + 4 x + 5 x^2 + 6 x^3 - 8 x^5 - 9 x^6)/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9), {x, 0, 20}], x]

concat([0,0], Vec((3 + 4*x + 5*x^2 + 6*x^3 - 8*x^5 - 9*x^6)/((1 - x^2 - x^3)*(1 + x^2 - x^6)) + O(x^50)))

a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) - a(n-8) - a(n-9) for n > 9.
G.f.: x^3*(3 + 4*x + 5*x^2 + 6*x^3 - 8*x^5 - 9*x^6)/((1 - x^2 - x^3)*(1 + x^2 - x^6)).
a(2*n) = A001608(n)^2.
a(2*n-1) = A001608(2*n-1), where A001608 are the Perrin numbers.

A001645 A Fielder sequence.

Original entry on oeis.org

1, 3, 7, 11, 26, 45, 85, 163, 304, 578, 1090, 2057, 3888, 7339, 13862, 26179, 49437, 93366, 176321, 332986, 628852, 1187596, 2242800, 4235569, 7998951, 15106172, 28528288, 53876211, 101746240, 192149690, 362878313, 685302531, 1294206745, 2444133829

Offset: 1

N. J. A. Sloane

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

T. D. Noe, Table of n, a(n) for n = 1..1000
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
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
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,1,1,0,1).

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

I:=[1,3,7,11,26]; [n le 5 select I[n] else Self(n-1) + Self(n-2) + Self(n-3) + Self(n-5): n in [1..30]]; // G. C. Greubel, Dec 19 2017

A001645:=-(1+2*z+3*z**2+5*z**4)/(-1+z+z**2+z**3+z**5); [Conjectured by Simon Plouffe in his 1992 dissertation.]

LinearRecurrence[{1, 1, 1, 0, 1}, {1, 3, 7, 11, 26}, 50] (* T. D. Noe, Aug 09 2012 *)
CoefficientList[Series[x*(1+2*x+3*x^2+5*x^4)/(1-x-x^2-x^3-x^5), {x, 0, 50}], x] (* G. C. Greubel, Dec 19 2017 *)

a(n)=if(n<0,0,polcoeff(x*(1+2*x+3*x^2+5*x^4)/(1-x-x^2-x^3-x^5)+x*O(x^n),n))

G.f.: x*(1+2*x+3*x^2+5*x^4)/(1-x-x^2-x^3-x^5).

a(n) = trace(M^n), where M = [0, 0, 0, 0, 1; 1, 0, 0, 0, 0; 0, 1, 0, 0, 1; 0, 0, 1, 0, 1; 0, 0, 0, 1, 1] is the 5 x 5 companion matrix to the monic polynomial x^5 - x^4 - x^3 - x^2 - 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 09 2023

A001641 A Fielder sequence: a(n) = a(n-1) + a(n-2) + a(n-4).

Original entry on oeis.org

1, 3, 4, 11, 16, 30, 50, 91, 157, 278, 485, 854, 1496, 2628, 4609, 8091, 14196, 24915, 43720, 76726, 134642, 236283, 414645, 727654, 1276941, 2240878, 3932464, 6900996, 12110401, 21252275, 37295140, 65448411, 114853952, 201554638, 353703730, 620706779

Offset: 1

N. J. A. Sloane

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

T. D. Noe, Table of n, a(n) for n = 1..1000
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
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.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
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,1,0,1).

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

I:=[1,3,4,11]; [n le 4 select I[n] else Self(n-1) + Self(n-2) + Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 09 2018

A001641:=-(1+2*z+4*z**3)/(z+1)/(z**3-z**2+2*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

LinearRecurrence[{1, 1, 0, 1}, {1, 3, 4, 11}, 50] (* T. D. Noe, Aug 09 2012 *)

a(n):=(sum(sum(binomial(j,n-4*k+3*j)*binomial(k,j),j,floor((4*k-n)/3),floor((4*k-n)/2))/k,k,1,n))*n; /* Vladimir Kruchinin, May 25 2011 */

a(n)=if(n<0,0,polcoeff(x*(1+2*x+4*x^3)/(1-x-x^2-x^4)+x*O(x^n),n))

G.f.: x*(1+2*x+4*x^3)/(1-x-x^2-x^4).
a(n) = n*Sum_{k=1..n} Sum_{j=floor((4*k-n)/3)..floor((4*k-n)/2)} binomial(j,n-4*k+3*j)*binomial(k,j)/k. - Vladimir Kruchinin, May 25 2011
a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 0; 0, 1, 0, 1; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - x^2 - 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, Dec 31 2022

cp's OEIS Frontend

A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A001254 Squares of Lucas numbers.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A111569 a(n) = a(n-1) + a(n-3) + a(n-4) for n > 3, a(0) = -1, a(1) = 1, a(2) = 2, a(3) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A111573 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 0,1,3,3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A111570 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 2,5,4,7.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A111571 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms 1,1,-2,-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A111572 a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4, with initial terms -1,3,2,1.

Views

Author

Keywords

Comments

Links