%I M1074 N0406 #673 Nov 23 2024 09:05:08

%S 0,0,1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,

%T 35890,66012,121415,223317,410744,755476,1389537,2555757,4700770,

%U 8646064,15902591,29249425,53798080,98950096,181997601,334745777,615693474,1132436852

%N Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1.

%C The name "tribonacci number" is less well-defined than "Fibonacci number". The sequence A000073 (which begins 0, 0, 1) is probably the most important version, but the name has also been applied to A000213, A001590, and A081172. - _N. J. A. Sloane_, Jul 25 2024

%C Also (for n > 1) number of ordered trees with n+1 edges and having all leaves at level three. Example: a(4)=2 because we have two ordered trees with 5 edges and having all leaves at level three: (i) one edge emanating from the root, at the end of which two paths of length two are hanging and (ii) one path of length two emanating from the root, at the end of which three edges are hanging. - _Emeric Deutsch_, Jan 03 2004

%C a(n) is the number of compositions of n-2 with no part greater than 3. Example: a(5)=4 because we have 1+1+1 = 1+2 = 2+1 = 3. - _Emeric Deutsch_, Mar 10 2004

%C Let A denote the 3 X 3 matrix [0,0,1;1,1,1;0,1,0]. a(n) corresponds to both the (1,2) and (3,1) entries in A^n. - _Paul Barry_, Oct 15 2004

%C Number of permutations satisfying -k <= p(i)-i <= r, i=1..n-2, with k=1, r=2. - _Vladimir Baltic_, Jan 17 2005

%C Number of binary sequences of length n-3 that have no three consecutive 0's. Example: a(7)=13 because among the 16 binary sequences of length 4 only 0000, 0001 and 1000 have 3 consecutive 0's. - _Emeric Deutsch_, Apr 27 2006

%C Therefore, the complementary sequence to A050231 (n coin tosses with a run of three heads). a(n) = 2^(n-3) - A050231(n-3) - _Toby Gottfried_, Nov 21 2010

%C Convolved with the Padovan sequence = row sums of triangle A153462. - _Gary W. Adamson_, Dec 27 2008

%C For n > 1: row sums of the triangle in A157897. - _Reinhard Zumkeller_, Jun 25 2009

%C a(n+2) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 0, 0, 1; 1, 0, 0] or [1, 1, 0; 1, 0, 1; 1, 0, 0] or [1, 1, 1; 1, 0, 0; 0, 1, 0] or [1, 0, 1; 1, 0, 0; 1, 1, 0]. - _R. J. Mathar_, Feb 03 2014

%C a(n-1) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 0, 1; 1, 1, 1; 0, 1, 0], [0, 1, 0; 0, 1, 1; 1, 1, 0], [0, 0, 1; 1, 0, 1; 0, 1, 1] or [0, 1, 0; 0, 0, 1; 1, 1, 1]. - _R. J. Mathar_, Feb 03 2014

%C Also row sums of A082601 and of A082870. - _Reinhard Zumkeller_, Apr 13 2014

%C Least significant bits are given in A021913 (a(n) mod 2 = A021913(n)). - _Andres Cicuttin_, Apr 04 2016

%C The nonnegative powers of the tribonacci constant t = A058265 are t^n = a(n)*t^2 + (a(n-1) + a(n-2))*t + a(n-1)*1, for n >= 0, with a(-1) = 1 and a(-2) = -1. This follows from the recurrences derived from t^3 = t^2 + t + 1. See the example in A058265 for the first nonnegative powers. For the negative powers see A319200. - _Wolfdieter Lang_, Oct 23 2018

%C The term "tribonacci number" was coined by Mark Feinberg (1963), a 14-year-old student in the 9th grade of the Susquehanna Township Junior High School in Pennsylvania. He died in 1967 in a motorcycle accident. - _Amiram Eldar_, Apr 16 2021

%C Andrews, Just, and Simay (2021, 2022) remark that it has been suggested that this sequence is mentioned in Charles Darwin's Origin of Species as bearing the same relation to elephant populations as the Fibonacci numbers do to rabbit populations. - _N. J. A. Sloane_, Jul 12 2022

%D M. Agronomof, Sur une suite récurrente, Mathesis (Series 4), Vol. 4 (1914), pp. 125-126.

%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.

%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

%D J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.

%D Raphael Schumacher, Explicit formulas for sums involving the squares of the first n Tribonacci numbers, Fib. Q., 58:3 (2020), 194-202.

%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 Simone Sandri, <a href="/A000073/b000073.txt">Table of n, a(n) for n = 0..3000</a> (first 200 terms from T. D. Noe)

%H Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, <a href="http://arxiv.org/abs/1409.6454">Colored compositions, Invert operator and elegant compositions with the "black tie"</a>, arXiv:1409.6454 [math.NT], 2014; Discrete Math. 335 (2014), 1-7. MR3248794

%H Abdullah Açikel, Amrouche Said, Hacene Belbachir, and Nurettin Irmak, <a href="https://doi.org/10.55730/1300-0098.3416">On k-generalized Lucas sequence with its triangle</a>, Turkish J. Math. (2023) Vol. 47, No. 4, Art. 6, 1129-1143. See p. 1130.

%H Kunle Adegoke, Adenike Olatinwo, and 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 Adel Alahmadi and Florian Luca, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Luca/luca52.html">On Tribonacci Numbers that are Products of Factorials</a>, J. Int. Seq., Vol. 26 (2023), Article 23.2.2.

%H Said Amrouche and Hacène Belbachir, <a href="https://doi.org/10.3906/mat-1811-109">Unimodality and linear recurrences associated with rays in the Delannoy triangle</a>, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.

%H Pornpawee Anantakitpaisal and Kantaphon Kuhapatanakul, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Kuhapatanakul/kuha7.html">Reciprocal Sums of the Tribonacci Numbers</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.2.1.

%H George E. Andrews, Matthew Just, and Greg Simay, <a href="https://arxiv.org/abs/2102.01613">Anti-palindromic compositions</a>, arXiv:2102.01613 [math.CO], 2021. Also Fib. Q., 60:2 (2022), 164-176.

%H Kassie Archer and Aaron Geary, <a href="https://arxiv.org/abs/2312.14351">Powers of permutations that avoid chains of patterns</a>, arXiv:2312.14351 [math.CO], 2023. See p. 15.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.307-309.

%H J. L. Arocha and B. Llano, <a href="http://arxiv.org/abs/1601.01268">The number of dominating k-sets of paths, cycles and wheels</a>, arXiv:1601.01268 [math.CO], 2016.

%H Christos Athanasiadis, Jesús De Loera, and Zhenyang Zhang, <a href="https://arxiv.org/abs/2002.00999">Enumerative problems for arborescences and monotone paths on polytopes</a>, arXiv:2002.00999 [math.CO], 2020.

%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No. 1 (April 2010), 119-135.

%H Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, <a href="http://arxiv.org/abs/1601.07723">Non-overlapping matrices</a>, arXiv:1601.07723 [cs.DM], 2016.

%H D. Birmajer, J. Gil and M. Weiner, <a href="http://arxiv.org/abs/1405.7727">Linear recurrence sequences and their convolutions via Bell polynomials</a>, arXiv:1405.7727 [math.CO], 2014.

%H Daniel Birmajer, Juan B. Gil, and 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 Eric Fernando Bravo, <a href="https://www.mathos.unios.hr/mc/index.php/mc/article/view/4733">On concatenations of Padovan and Perrin numbers</a>, Math. Commun. (2023) Vol 28, 105-119.

%H David Broadhurst, <a href="http://arxiv.org/abs/1504.05303">Multiple Landen values and the tribonacci numbers</a>, arXiv:1504.05303 [hep-th], 2015.

%H Martin Burtscher, Igor Szczyrba, and 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 P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., <a href="http://www.fq.math.ca/Scanned/10-1/carlitz3-a.pdf">Fibonacci representations of higher order</a>, Fib. Quart., 10 (1972), 43-69.

%H Nataliya Chekhova, Pascal Hubert, and Ali Messaoudi, <a href="http://archive.numdam.org/item/JTNB_2001__13_2_371_0">Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci</a>, Journal de théorie des nombres de Bordeaux, 13(2) (2001), 371-394.

%H Fan R. K. Chung, Persi Diaconis, and Ron Graham, <a href="https://statweb.stanford.edu/~cgates/PERSI/papers/sequential_sampling_10.pdf">Permanental generating functions and sequential importance sampling</a>, Stanford University (2018).

%H Curtis Cooper, S. Miller, P. Moses, M. Sahin, et al., <a href="http://thotsaporn.com/Cooper.pdf">On Identities Of Ruggles, Horadam, Howard, and Young</a>, Preprint, 2016; Proceedings of the 17th International Conference on Fibonacci Numbers and Their Applications, Université de Caen-Normandie, Caen, France, June 26 to July 2, 2016.

%H Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, <a href="https://doi.org/10.37236/2099">Non-contiguous pattern avoidance in binary trees</a>. Electron. J. Combin. 19(3) (2012), Paper 22, 21 pp., MR2967227.

%H Mahadi Ddamulira, <a href="https://hal.archives-ouvertes.fr/hal-02547159">Tribonacci numbers that are concatenations of two repdigits</a>, hal-02547159, Mathematics [math] / Number Theory [math.NT], 2020.

%H F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, <a href="https://doi.org/10.37236/8905">Queens in exile: non-attacking queens on infinite chess boards</a>, Electronic J. Combin., 27(1) (2020), #P1.52.

%H Ömür Deveci, Zafer Adıgüzel, and Taha Doğan, <a href="https://doi.org/10.7546/nntdm.2020.26.1.179-190">On the Generalized Fibonacci-circulant-Hurwitz numbers</a>, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.

%H G. P. B. Dresden and Z. Du, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Dresden/dresden6.html">A Simplified Binet Formula for k-Generalized Fibonacci Numbers</a>, J. Int. Seq. 17 (2014) # 14.4.7.

%H M. S. El Naschie, <a href="http://dx.doi.org/10.1016/0898-1221(95)00062-4">Statistical geometry of a Cantor discretum and semiconductors</a>, Computers & Mathematics with Applications, Vol. 29 (Issue 12, June 1995), 103-110.

%H Nathaniel D. Emerson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.html">A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.

%H Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, <a href="https://arxiv.org/abs/2107.01029">Words in Random Binary Sequences I</a>, arXiv:2107.01029 [math.GM], 2021.

%H Tim Evink and Paul Alexander Helminck, <a href="https://arxiv.org/abs/1801.04605">Tribonacci numbers and primes of the form p=x^2+11y^2</a>, arXiv:1801.04605 [math.NT], 2018.

%H Vinicius Facó and D. Marques, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Marques/marques22.html">Tribonacci Numbers and the Brocard-Ramanujan Equation</a>, Journal of Integer Sequences, 19 (2016), #16.4.4.

%H M. Feinberg, <a href="http://www.fq.math.ca/Scanned/1-3/feinberg.pdf">Fibonacci-Tribonacci</a>, Fib. Quart. 1(3) (1963), 71-74.

%H M. Feinberg, <a href="http://www.fq.math.ca/Scanned/2-3/feinberg.pdf">New slants</a>, Fib. Quart. 2 (1964), 223-227.

%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, 12(1) (2018), 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, 12(7) (2018), 307-324.

%H Taras Goy and Mark Shattuck, <a href="http://toc.ui.ac.ir/article_24437.html">Determinant identities for Toeplitz-Hessenberg matrices with tribonacci number entries</a>, Transactions on Combinatorics 9(3) (2020), 89-109. See also <a href="https://arxiv.org/abs/2003.10660">arXiv:2003.10660</a>, [math.CO], 2020.

%H Hans-Christian Herbig, <a href="https://hal.science/hal-04091017">Pivotal condensation and chemical balancing</a>, hal-04091017 [math] 2023.

%H M. D. Hirschhorn, <a href="http://www.fq.math.ca/Papers1/44-1/quartMichaelhirschhorn01_2006.pdf">Coupled third-order recurrences</a>, Fib. Quart., 44 (2006), 26-31.

%H F. T. Howard and Curtis Cooper, <a href="http://www.fq.math.ca/Papers1/49-3/HowardCooper.pdf">Some identities for r-Fibonacci numbers</a>, Fibonacci Quart. 49 (2011), no. 3, 231-243.

%H Omar Khadir, László Németh, and László Szalay, <a href="https://doi.org/10.1007/s00025-024-02284-3">Tiling of dominoes with ranked colors</a>, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.

%H Bahar Kuloğlu and Engin Özkan, <a href="https://doi.org/10.37394/23206.2023.22.25">d-Tribonacci Polynomials and Their Matrix Representations</a>, WSEAS Trans. Math. (2023) Vol. 22, 204-212.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=10">Encyclopedia of Combinatorial Structures 10</a>

%H Nurettin Irmak and László Szalay, <a href="http://dx.doi.org/10.7146/math.scand.a-23293">Tribonacci Numbers Close to the Sum 2^a+3^b+5^c</a>, Math. Scand. 118(1) (2016), 27-32.

%H M. Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Janjic/janjic42.html">Determinants and Recurrence Sequences</a>, Journal of Integer Sequences, 2012, Article 12.3.5. - _N. J. A. Sloane_, Sep 16 2012

%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(1) (1985), 29-35 [a(n+2) = T_n on p. 35].

%H S. Kak, <a href="http://arxiv.org/abs/physics/0411195">The Golden Mean and the Physics of Aesthetics</a>, arXiv:physics/0411195 [physics.hist-ph], 2004.

%H Tamara Kogan, L. Sapir, A. Sapir, and A. Sapir, <a href="https://doi.org/10.1016/j.apnum.2016.08.012">The Fibonacci family of iterative processes for solving nonlinear equations</a>, Applied Numerical Mathematics 110 (2016), 148-158.

%H Takao Komatsu, <a href="http://pjm.ppu.edu/sites/default/files/papers/PJM_April2019_413to417.pdf">Convolution identities for tribonacci-type numbers with arbitrary initial values</a>, Palestine Journal of Mathematics, Vol. 8(2) (2019), 413-417.

%H T. Komatsu and V. Laohakosol, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Komatsu/komatsu6.html">On the Sum of Reciprocals of Numbers Satisfying a Recurrence Relation of Order s</a>, J. Int. Seq. 13 (2010), #10.5.8.

%H Vladimir Kruchinin, <a href="http://arxiv.org/abs/1009.2565">Composition of ordinary generating functions</a>, arXiv:1009.2565 [math.CO], 2010.

%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1810.09787">The Tribonacci and ABC Representations of Numbers are Equivalent</a>, arXiv preprint arXiv:1810.09787 [math.NT], 2018.

%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(2) (1988), 131-134.

%H Steven Linton, James Propp, Tom Roby, and Julian West, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.

%H Sepideh Maleki and Martin Burtscher, <a href="https://doi.org/10.1145/3173162.3173168">Automatic Hierarchical Parallelization of Linear Recurrences</a>, Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems, ACM, 2018.

%H T. Mansour, <a href="https://arxiv.org/abs/math/9909019">Permutations avoiding a set of patterns from S_3 and a pattern from S_4</a>, arXiv:math/9909019 [math.CO], 1999.

%H T. Mansour and M. Shattuck, <a href="http://dx.doi.org/10.1016/j.amc.2012.12.052">Polynomials whose coefficients are generalized Tribonacci numbers</a>, Applied Mathematics and Computation, Volume 219(15) (2013), 8366-8374.

%H T. Mansour and M. Shattuck, <a href="http://arxiv.org/abs/1410.6943">A monotonicity property for generalized Fibonacci sequences</a>, arXiv:1410.6943 [math.CO], 2014.

%H O. Martin, A. M. Odlyzko and S. Wolfram, <a href="http://projecteuclid.org/euclid.cmp/1103941055">Algebraic properties of cellular automata</a>, Comm. Math. Physics, 93 (1984), pp. 219-258, Reprinted in Theory and Applications of Cellular Automata, S. Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113. See Eq. 5.5b.

%H László Németh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Nemeth/nemeth6.html">The trinomial transform triangle</a>, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also <a href="https://arxiv.org/abs/1807.07109">arXiv:1807.07109</a> [math.NT], 2018.

%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, 8 (2005), Article 05.4.4.

%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; arXiv:0911.4975 [math.NT], 2009.

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

%H János Podani, Ádám Kun and András Szilágyi, <a href="https://doi.org/10.1007/s10739-017-9488-5">How fast does Darwin’s elephant population grow?</a>, Journal of the History of Biology, Vol. 51, No. 2 (2018), pp. 259-281.

%H H. Prodinger, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Prodinger2/prod31.html">Counting Palindromes According to r-Runs of Ones Using Generating Functions</a>, J. Int. Seq. 17 (2014) # 14.6.2, odd length middle 0 with r=2.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013

%H J. L. Ramirez and V. F. Sirvent, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ramirez/ramirez4.html">Incomplete Tribonacci Numbers and Polynomials</a>, Journal of Integer Sequences, 17 (2014), #14.4.2.

%H J. L. Ramírez and V. F. Sirvent, <a href="https://doi.org/10.37236/4618">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.

%H Michel Rigo, <a href="http://arxiv.org/abs/1602.03364">Relations on words</a>, arXiv:1602.03364 [cs.FL], 2016.

%H Jeffrey Shallit, <a href="https://arxiv.org/abs/2210.03996">Some Tribonacci conjectures</a>, arXiv:2210.03996 [math.CO], 2022.

%H A. G. Shannon, <a href="https://www.fq.math.ca/Scanned/15-3/shannon-a.pdf">Tribonacci numbers and Pascal's pyramid</a>, <a href="https://www.fq.math.ca/Scanned/15-3/shannon-b.pdf">part b</a>, Fibonacci Quart. 15(3) (1977), 268-275.

%H M. Shattuck, <a href="http://arxiv.org/abs/1406.2755">Combinatorial identities for incomplete tribonacci polynomials</a>, arXiv:1406.2755 [math.CO], 2014.

%H W. R. Spickerman, <a href="https://www.fq.math.ca/Scanned/20-2/spickerman.pdf"> Binet's formula for the tribonacci sequence</a>, The Fibonacci Quarterly 20(2) (1982), 118-120.

%H H. J. H. Tuenter, <a href="https://doi.org/10.1080/00029890.2023.2231796">In Search of Comrade Agronomof: Some Tribonacci History</a>, The American Mathematical Monthly, 130(8):708-719, October 2023.

%H M. E. Waddill and L. Sacks, <a href="http://www.fq.math.ca/Scanned/5-3/waddill.pdf">Another generalized Fibonacci sequence</a>, Fib. Quart., 5 (1967), 209-222.

%H Hsin-Po Wang and Chi-Wei Chin, <a href="https://arxiv.org/abs/2405.17499">On Counting Subsequences and Higher-Order Fibonacci Numbers</a>, arXiv:2405.17499 [cs.IT], 2024. See p. 2.

%H Kai Wang, <a href="https://www.researchgate.net/publication/344295426_IDENTITIES_FOR_GENERALIZED_ENNEANACCI_NUMBERS">Identities for generalized enneanacci numbers</a>, Generalized Fibonacci Sequences (2020).

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

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

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers">Generalizations of Fibonacci numbers</a>.

%H Ce Xu and Jianqiang Zhao, <a href="https://arxiv.org/abs/2009.10774">Alternating Multiple T-Values: Weighted Sums, Duality, and Dimension Conjecture</a>, arXiv:2009.10774 [math.NT], 2020.

%H Shujie Zhou and Li Chen, <a href="https://doi.org/10.3390/sym11101195">Tribonacci Numbers and Some Related Interesting Identities</a>, Symmetry, 11(10) (2019), 1195.

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

%F G.f.: x^2/(1 - x - x^2 - x^3).

%F G.f.: x^2 / (1 - x / (1 - x / (1 + x^2 / (1 + x)))). - _Michael Somos_, May 12 2012

%F G.f.: Sum_{n >= 0} x^(n+2) *[ Product_{k = 1..n} (k + k*x + x^2)/(1 + k*x + k*x^2) ] = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + ... may be proved by the method of telescoping sums. - _Peter Bala_, Jan 04 2015

%F a(n+1)/a(n) -> A058265. a(n-1)/a(n) -> A192918.

%F a(n) = central term in M^n * [1 0 0] where M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 1 1]. (M^n * [1 0 0] = [a(n-1) a(n) a(n+1)].) a(n)/a(n-1) tends to the tribonacci constant, 1.839286755... = A058265, an eigenvalue of M and a root of x^3 - x^2 - x - 1 = 0. - _Gary W. Adamson_, Dec 17 2004

%F a(n+2) = Sum_{k=0..n} T(n-k, k), where T(n, k) = trinomial coefficients (A027907). - _Paul Barry_, Feb 15 2005

%F A001590(n) = a(n+1) - a(n); A001590(n) = a(n-1) + a(n-2) for n > 1; a(n) = (A000213(n+1) - A000213(n))/2; A000213(n-1) = a(n+2) - a(n) for n > 0. - _Reinhard Zumkeller_, May 22 2006

%F Let C = the tribonacci constant, 1.83928675...; then C^n = a(n)*(1/C) + a(n+1)*(1/C + 1/C^2) + a(n+2)*(1/C + 1/C^2 + 1/C^3). Example: C^4 = 11.444...= 2*(1/C) + 4*(1/C + 1/C^2) + 7*(1/C + 1/C^2 + 1/C^3). - _Gary W. Adamson_, Nov 05 2006

%F a(n) = j*C^n + k*r1^n + L*r2^n where C is the tribonacci constant (C = 1.8392867552...), real root of x^3-x^2-x-1=0, and r1 and r2 are the two other roots (which are complex), r1 = m+p*i and r2 = m-p*i, where i = sqrt(-1), m = (1-C)/2 (m = -0.4196433776...) and p = ((3*C-5)*(C+1)/4)^(1/2) = 0.6062907292..., and where j = 1/((C-m)^2 + p^2) = 0.1828035330..., k = a+b*i, and L = a-b*i, where a = -j/2 = -0.0914017665... and b = (C-m)/(2*p*((C-m)^2 + p^2)) = 0.3405465308... . - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007

%F a(n+1) = 3*c*((1/3)*(a+b+1))^n/(c^2-2*c+4) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3), c=(586+102*sqrt(33))^(1/3). Round to the nearest integer. - Al Hakanson (hawkuu(AT)gmail.com), Feb 02 2009

%F a(n) = round(3*((a+b+1)/3)^n/(a^2+b^2+4)) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3).. - _Anton Nikonov_

%F Another form of the g.f.: f(z) = (z^2-z^3)/(1-2*z+z^4). Then we obtain a(n) as a sum: a(n) = Sum_{i=0..floor((n-2)/4)} ((-1)^i*binomial(n-2-3*i,i)*2^(n-2-4*i)) - Sum_{i=0..floor((n-3)/4)} ((-1)^i*binomial(n-3-3*i,i)*2^(n-3-4*i)) with natural convention: Sum_{i=m..n} alpha(i) = 0 for m > n. - _Richard Choulet_, Feb 22 2010

%F a(n+2) = Sum_{k=0..n} Sum_{i=k..n, mod(4*k-i,3)=0} binomial(k,(4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1,k-1). - _Vladimir Kruchinin_, Aug 18 2010

%F a(n) = 2*a(n-2) + 2*a(n-3) + a(n-4). - _Gary Detlefs_, Sep 13 2010

%F Sum_{k=0..2*n} a(k+b)*A027907(n,k) = a(3*n+b), b >= 0 (see A099464, A074581).

%F a(n) = 2*a(n-1) - a(n-4), with a(0)=a(1)=0, a(2)=a(3)=1. - _Vincenzo Librandi_, Dec 20 2010

%F Starting (1, 2, 4, 7, ...) is the INVERT transform of (1, 1, 1, 0, 0, 0, ...). - _Gary W. Adamson_, May 13 2013

%F G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x + x^2)/( x*(4*k+3 + x + x^2) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 09 2013

%F a(n+2) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2*j,k)*binomial(j,k)*2^k. - _Tony Foster III_, Sep 08 2017

%F Sum_{k=0..n} (n-k)*a(k) = (a(n+2) + a(n+1) - n - 1)/2. See A062544. - _Yichen Wang_, Aug 20 2020

%F a(n) = A008937(n-1) - A008937(n-2) for n >= 2. - _Peter Luschny_, Aug 20 2020

%F From _Yichen Wang_, Aug 27 2020: (Start)

%F Sum_{k=0..n} a(k) = (a(n+2) + a(n) - 1)/2. See A008937.

%F Sum_{k=0..n} k*a(k) = ((n-1)*a(n+2) - a(n+1) + n*a(n) + 1)/2. See A337282. (End)

%F For n > 1, a(n) = b(n) where b(1) = 1 and then b(n) = Sum_{k=1..n-1} b(n-k)*A000931(k+2). - _J. Conrad_, Nov 24 2022

%F Conjecture: the congruence a(n*p^(k+1)) + a(n*p^k) + a(n*p^(k-1)) == 0 (mod p^k) holds for positive integers k and n and for all the primes p listed in A106282. - _Peter Bala_, Dec 28 2022

%F Sum_{k=0..n} k^2*a(k) = ((n^2-4*n+6)*a(n+1) - (2*n^2-2*n+5)*a(n) + (n^2-2*n+3)*a(n-1) - 3)/2. - _Prabha Sivaramannair_, Feb 10 2024

%F a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(3*r^2-2*r-1). - _Fabian Pereyra_, Nov 23 2024

%e G.f. = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + 24*x^8 + 44*x^9 + 81*x^10 + ...

%p a:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1,3]:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Dec 19 2016

%p # second Maple program:

%p A000073:=proc(n) option remember; if n <= 1 then 0 elif n=2 then 1 else procname(n-1)+procname(n-2)+procname(n-3); fi; end; # _N. J. A. Sloane_, Aug 06 2018

%t CoefficientList[Series[x^2/(1 - x - x^2 - x^3), {x, 0, 50}], x]

%t a[0] = a[1] = 0; a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3]; Array[a, 36, 0] (* _Robert G. Wilson v_, Nov 07 2010 *)

%t LinearRecurrence[{1, 1, 1}, {0, 0, 1}, 60] (* _Vladimir Joseph Stephan Orlovsky_, May 24 2011 *)

%t a[n_] := SeriesCoefficient[If[ n < 0, x/(1 + x + x^2 - x^3), x^2/(1 - x - x^2 - x^3)], {x, 0, Abs @ n}] (* _Michael Somos_, Jun 01 2013 *)

%t Table[-RootSum[-1 - # - #^2 + #^3 &, -#^n - 9 #^(n + 1) + 4 #^(n + 2) &]/22, {n, 0, 20}] (* _Eric W. Weisstein_, Nov 09 2017 *)

%o (PARI) {a(n) = polcoeff( if( n<0, x / ( 1 + x + x^2 - x^3), x^2 / ( 1 - x - x^2 - x^3) ) + x * O(x^abs(n)), abs(n))}; /* _Michael Somos_, Sep 03 2007 */

%o (PARI) my(x='x+O('x^99)); concat([0, 0], Vec(x^2/(1-x-x^2-x^3))) \\ _Altug Alkan_, Apr 04 2016

%o (PARI) a(n)=([0,1,0;0,0,1;1,1,1]^n)[1,3] \\ _Charles R Greathouse IV_, Apr 18 2016, simplified by _M. F. Hasler_, Apr 18 2018

%o (Maxima) A000073[0]:0$

%o A000073[1]:0$

%o A000073[2]:1$

%o A000073[n]:=A000073[n-1]+A000073[n-2]+A000073[n-3]$

%o makelist(A000073[n], n, 0, 40); /* _Emanuele Munarini_, Mar 01 2011 */

%o (Haskell)

%o a000073 n = a000073_list !! n

%o a000073_list = 0 : 0 : 1 : zipWith (+) a000073_list (tail

%o (zipWith (+) a000073_list $ tail a000073_list))

%o -- _Reinhard Zumkeller_, Dec 12 2011

%o (Python)

%o def a(n, adict={0:0, 1:0, 2:1}):

%o if n in adict:

%o return adict[n]

%o adict[n]=a(n-1)+a(n-2)+a(n-3)

%o return adict[n] # _David Nacin_, Mar 07 2012

%o from functools import cache

%o @cache

%o def A000073(n: int) -> int:

%o if n <= 1: return 0

%o if n == 2: return 1

%o return A000073(n-1) + A000073(n-2) + A000073(n-3) # _Peter Luschny_, Nov 21 2022

%o (Magma) [n le 3 select Floor(n/3) else Self(n-1)+Self(n-2)+Self(n-3): n in [1..70]]; // _Vincenzo Librandi_, Jan 29 2016

%o (GAP) a:=[0,0,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # _Muniru A Asiru_, Oct 24 2018

%Y Cf. A000045, A000078, A000213, A000931, A001590 (first differences, also a(n)+a(n+1)), A001644, A008288 (tribonacci triangle), A008937 (partial sums), A021913, A027024, A027083, A027084, A046738 (Pisano periods), A050231, A054668, A062544, A063401, A077902, A081172, A089068, A118390, A145027, A153462, A230216.

%Y A057597 is this sequence run backwards: A057597(n) = a(1-n).

%Y Row 3 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).

%Y Partitions: A240844 and A117546.

%Y Cf. also A092836 (subsequence of primes), A299399 = A092835 + 1 (indices of primes).

%K nonn,easy,nice,changed

%O 0,5

%A _N. J. A. Sloane_

%E Minor edits by _M. F. Hasler_, Apr 18 2018

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