login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001644 a(n) = a(n-1) + a(n-2) + a(n-3), a(0)=3, a(1)=1, a(2)=3.
(Formerly M2625 N1040)
80

%I M2625 N1040

%S 3,1,3,7,11,21,39,71,131,241,443,815,1499,2757,5071,9327,17155,31553,

%T 58035,106743,196331,361109,664183,1221623,2246915,4132721,7601259,

%U 13980895,25714875,47297029,86992799,160004703,294294531,541292033,995591267,1831177831

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

%C 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

%C For n >= 3, also the number of dominating sets on the n-cycle graph C_n. - _Eric W. Weisstein_, Mar 30 2017

%C 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

%C For n >= 3, also the number of minimal edge covers in the n-web graph. - _Eric W. Weisstein_, Aug 03 2017

%C For n >= 1, also the number of ways to tile a bracelet of length n with squares, dominos, and trominos. - _Ruijia Li_ and _Greg Dresden_, Sep 14 2019

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%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 G. C. Greubel, <a href="/A001644/b001644.txt">Table of n, a(n) for n = 0..1000</a> (terms 1..200 from T. D. Noe)

%H Kunle Adegoke, Adenike Olatinwo, Winning Oyekanmi, <a href="https://arxiv.org/abs/1811.03663">New Tribonacci Recurrence Relations and Addition Formulas</a>, arXiv:1811.03663 [math.CO], 2018.

%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="http://arxiv.org/abs/1505.06339">Linear recurrence sequences with indices in arithmetic progression and their sums</a>, arXiv:1505.06339 [math.NT], 2015.

%H Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

%H C. A. Charalambides, <a href="http://www.fq.math.ca/Scanned/29-4/charalambides.pdf">Lucas numbers and polynomials of order k and the length of the longest circular success run</a>, The Fibonacci Quarterly, 29 (1991), 290-297.

%H Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, <a href="http://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/ruggleshoward10.pdf">On Identities Of Ruggles, Horadam, Howard, and Young</a>, Preprint, 2016.

%H Curtis Cooper, Steven Miller, Peter J. C. Moses, Murat Sahin, and Thotsaporn Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/55-5/Cooper.pdf">On identities of Ruggles, Hradam, Howard, and Young</a>, The Fibonacci Quarterly, 55.5 (2017), 42-65.

%H M. Elia, <a href="http://www.fq.math.ca/Scanned/39-2/elia.pdf">Derived Sequences, The Tribonacci Recurrence and Cubic Forms</a>, The Fibonacci Quarterly, 39.2 (2001), 107-109.

%H G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL5/Ward/ward2.html">Integer Sequences and Periodic Points</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.

%H G. Everest, Y. Puri and T. Ward, <a href="https://arxiv.org/abs/math/0204173">Integer sequences counting periodic points</a>, arXiv:math/0204173 [math.NT], 2002.

%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 Robert Frontczak, <a href="https://doi.org/10.12988/ijma.2018.712153">Sums of Tribonacci and Tribonacci-Lucas Numbers</a>, International Journal of Mathematical Analysis, Vol. 12 (2018), No. 1, pp. 19-24.

%H Robert Frontczak, <a href="https://doi.org/10.12988/ijma.2018.8429">Convolutions for Generalized Tribonacci Numbers and Related Results</a>, International Journal of Mathematical Analysis (2018) Vol. 12, Issue 7, 307-324.

%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), #16.8.2.

%H A. Ilic, S. Klavzar, Y. Rho, <a href="http://dx.doi.org/10.2298/AADM120108002I">Generalized Lucas Cubes</a>, Appl. An. Disc. Math. 6 (2012) 82-94, proposition 11 for the sequence starting 1, 2, 4, 7, 11,...

%H Günter Köhler, <a href="https://www.fq.math.ca/Scanned/23-1/kohler.pdf">Generating functions of Fibonacci-like sequences and decimal expansion of some fractions</a>, The Fibonacci Quarterly 23, no.1, (1985), 29-35 [a(n) is there Lambda_n on p. 35].

%H Pin-Yen Lin, <a href="http://www.fq.math.ca/Scanned/26-2/lin.pdf">De Moivre type identities for the Tribonacci numbers</a>, The Fibonacci Quarterly 26, no.2, (1988), 131-134.

%H Matthew Macauley , Jon McCammond, Henning S. Mortveit, <a href="http://www.emis.de/journals/JACO/Volume33_1/hgv665924j44t770.html">Dynamics groups of asynchronous cellular automata</a>, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.

%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.

%H J. Pan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Pan/pan12.html">Some Properties of the Multiple Binomial Transform and the Hankel Transform of Shifted Sequences</a>, J. Int. Seq. 14 (2011) # 11.3.4, remark 17.

%H Andreas N. Philippou, Spiros D. Dafnis, <a href="https://www.researchgate.net/publication/329752557_A_simple_proof_of_an_identity_generalizing_Fibonacci-Lucas_identities">A simple proof of an identity generalizing Fibonacci-Lucas identities</a>, Fibonacci Quarterly (2018) Vol. 56, No. 4, 334-336.

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

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

%H J. L. Ramírez, V. F. Sirvent, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.

%H S. Saito, T. Tanaka, N. Wakabayashi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Saito/saito22.html">Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values</a>, J. Int. Seq. 14 (2011) # 11.2.4, Table 3.

%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/DominatingSet.html">Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Lucasn-StepNumber.html">Lucas n-Step Number</a>

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalEdgeCover.html">Minimal Edge Cover</a>

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

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

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

%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.

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

%F 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.

%F a(n) = A000073(n) + 2*A000073(n-1) + 3*A000073(n-2).

%F G.f.: (3-2*x-x^2)/(1-x-x^2-x^3). - _Miklos Kristof_, Jul 29 2002

%F 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

%F 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

%F a(n) = A073145(-n). for all n in Z. - _Michael Somos_, Dec 17 2016

%F 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

%e 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 + ...

%p 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

%t 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]

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

%t LinearRecurrence[{1, 1, 1}, {3, 1, 3}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 08 2012 *)

%t Table[RootSum[-1 - # - #^2 + #^3 &, #^n &], {n, 0, 40}] (* _Eric W. Weisstein_, Mar 30 2017 *)

%t RootSum[-1 - # - #^2 + #^3 &, #^Range[0, 40] &] (* _Eric W. Weisstein_, Aug 17 2017 *)

%o (PARI) {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 */

%o (PARI) my(x='x+O('x^40)); Vec((3-2*x-x^2)/(1-x-x^2-x^3)) \\ _Altug Alkan_, Apr 19 2018

%o (Haskell)

%o a001644 n = a001644_list !! n

%o a001644_list = 3 : 1 : 3 : zipWith3 (((+) .) . (+))

%o a001644_list (tail a001644_list) (drop 2 a001644_list)

%o -- _Reinhard Zumkeller_, Apr 13 2014

%o (MAGMA) 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

%o (GAP) 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

%o (Sage) ((3-2*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Mar 22 2019

%Y Cf. A000073, A073145, A106293 (Pisano periods), A073728 (partial sums).

%Y Cf. A058265.

%K nonn,easy

%O 0,1

%A _N. J. A. Sloane_

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

%E Deleted certain dangerous or potentially dangerous links. - _N. J. A. Sloane_, Jan 30 2021

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 07:59 EDT 2021. Contains 343030 sequences. (Running on oeis4.)