cp's OEIS Frontend

A001590 Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=0, a(1)=1, a(2)=0.

%I A001590 M0784 N0296 #215 May 13 2025 09:59:05
%S A001590 0,1,0,1,2,3,6,11,20,37,68,125,230,423,778,1431,2632,4841,8904,16377,
%T A001590 30122,55403,101902,187427,344732,634061,1166220,2145013,3945294,
%U A001590 7256527,13346834,24548655,45152016,83047505,152748176,280947697,516743378,950439251
%N A001590 Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=0, a(1)=1, a(2)=0.
%C A001590 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 A001590 Dimensions of the homogeneous components of the higher order peak algebra associated to cubic roots of unity (Hilbert series = 1 + 1*t + 2*t^2 + 3*t^3 + 6*t^4 + 11*t^5 ...). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006
%C A001590 Starting with offset 3: (1, 2, 3, 6, 11, 10, 37, ...) = row sums of triangle A145579. - _Gary W. Adamson_, Oct 13 2008
%C A001590 Starting (1, 2, 3, 6, 11, ...) = INVERT transform of the periodic sequence (1, 1, 0, 1, 1, 0, 1, 1, 0, ...). - _Gary W. Adamson_, May 04 2009
%C A001590 The comment of May 04 2009 is equivalent to: The numbers of ordered compositions of n using integers that are not multiples of 3 is equal to a(n+2) for n>=1, see [Hoggatt-Bicknell (1975) eq (2.7)]. - _Gary W. Adamson_, May 13 2013
%C A001590 Primes in the sequence are 2, 3, 11, 37, 634061, 7256527, ... in A231574. - _R. J. Mathar_, Aug 09 2012
%C A001590 Pisano period lengths: 1, 2, 13, 8, 31, 26, 48, 16, 39, 62,110,104,168, 48,403, 32, 96, 78, 360, 248, ... . - _R. J. Mathar_, Aug 10 2012
%C A001590 a(n+1) is the top left entry of the n-th power of any of 3 X 3 matrices [0, 1, 0; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 0, 1, 0], [0, 1, 1; 0, 0, 1; 1, 0, 1] or [0, 0, 1; 1, 0, 0; 1, 1, 1]. - _R. J. Mathar_, Feb 03 2014
%C A001590 a(n+3) equals the number of n-length binary words avoiding runs of zeros of lengths 3i+2, (i=0,1,2,...). - _Milan Janjic_, Feb 26 2015
%C A001590 Sums of pairs of successive terms of A000073. - _N. J. A. Sloane_, Oct 30 2016
%C A001590 The power Q^n, for n >= 0, of the tribonacci Q-matrix Q = matrix([1, 1, 1], [1, 0, 0], [0, 1, 0]) is, by the Cayley-Hamilton theorem, Q^n = matrix([a(n+2), a(n+1) + a(n), a(n+1)], [a(n+1), a(n) + a(n-1), a(n)], [a(n), a(n-1) + a(n-2), a(n-1)]), with a(-2) = -1 and a(-1) = 1. One can use a(n) = a(n-1) + a(n-2) + a(n-3) in order to obtain a(-1) and a(-2). - _Wolfdieter Lang_, Aug 13 2018
%C A001590 a(n+2) is the number of entries n, for n>=1, in the sequence {A278038(k)}_{k>=1} (without A278038(0) = 1). - _Wolfdieter Lang_, Sep 11 2018
%C A001590 In terms of the tribonacci numbers T(n) = A000073(n) the nonnegative powers of the Q-matrix (from the Aug 13 2018 comment) are Q^n = T(n)*Q^2 + (T(n-1) + T(n-2))*Q + T(n-1)*1_3, for n >= 0, with T(-1) = 1, T(-2) = -1. This is equivalent to the powers t^n of the tribonacci constant t = A058255 (or also for powers of the complex solutions). - _Wolfdieter Lang_, Oct 24 2018
%D A001590 Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
%D A001590 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001590 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001590 T. D. Noe, <a href="/A001590/b001590.txt">Table of n, a(n) for n = 0..200</a>
%H A001590 Kassie Archer and Noel Bourne, <a href="https://arxiv.org/abs/2505.05218">Pattern avoidance in compositions and powers of permutations</a>, arXiv:2505.05218 [math.CO], 2025. See p. 8.
%H A001590 Barry Balof, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Balof/balof19.html">Restricted tilings and bijections</a>, J. Integer Seq. 15 (2012), no. 2, Article 12.2.3, 17 pp.
%H A001590 Matthias Beck and Neville Robbins, <a href="http://arxiv.org/abs/1403.0665">Variations on a Generatingfunctional Theme: Enumerating Compositions with Parts Avoiding an Arithmetic Sequence</a>, arXiv:1403.0665 [math.NT], 2014.
%H A001590 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 A001590 M. Feinberg, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/1-3/feinberg.pdf">Fibonacci-Tribonacci</a>, Fib. Quart. 1(3) (1963), 71-74.
%H A001590 M. Feinberg, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/2-3/feinberg.pdf">New slants</a>, Fib. Quart. 2 (1964), 223-227.
%H A001590 Wojciech Florek, <a href="http://doi.org/10.1016/j.amc.2018.06.014">A class of generalized Tribonacci sequences applied to counting problems</a>, Appl. Math. Comput., 338 (2018), 809-821.
%H A001590 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), Article 16.8.2.
%H A001590 V. E. Hoggatt, Jr. and Marjorie Bicknell, <a href="https://fq.math.ca/13-4.html">Palindromic compositions</a>, Fib. Quart 13 (4) (1975) 357, eq (2.7)
%H A001590 Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 9.
%H A001590 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=401">Encyclopedia of Combinatorial Structures 401</a>
%H A001590 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
%H A001590 Tamara Kogan, Luba Sapir, Amir Sapir, and Ariel 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 A001590 Daniel Krob and Jean-Yves Thibon, <a href="https://arxiv.org/abs/math/0411407">Higher order peak algebras</a>, arXiv:math/0411407 [math.CO], 2004.
%H A001590 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 A001590 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 A001590 M. A. Nyblom, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Nyblom/nyblom13.html">Counting Palindromic Binary Strings Without r-Runs of Ones</a>, J. Int. Seq. 16 (2013) #13.8.7. P_3(n) = 1,2,2,3,3,6,6,11,11,...
%H A001590 Helmut 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, even length, r=2.
%H A001590 Karim Ritter von Merkl, <a href="https://arxiv.org/abs/2505.03916">Computing colored Khovanov homology</a>, arXiv:2505.03916 [math.QA], 2025. See p. 13.
%H A001590 Neville Robbins, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/52-1/NRobbins.pdf">On Tribonacci Numbers and 3-Regular Compositions</a>, Fibonacci Quart. 52 (2014), no. 1, 16-19. See Adamson's comments.
%H A001590 Bo Tan and Zhi-Ying Wen, <a href="http://dx.doi.org/10.1016/j.ejc.2006.07.007">Some properties of the Tribonacci sequence</a>, European Journal of Combinatorics, 28 (2007) 1703-1719.
%H A001590 M. E. Waddill and L. Sacks, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/5-3/waddill.pdf">Another generalized Fibonacci sequence</a>, Fib. Quart., 5 (1967), 209-222.
%H A001590 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TribonacciNumber.html">Tribonacci Number</a>
%H A001590 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1).
%F A001590 G.f.: x*(1-x)/(1-x-x^2-x^3).
%F A001590 Limit a(n)/a(n-1) = t where t is the real solution of t^3 = 1 + t + t^2, t = A058265 = 1.839286755... . If T(n) = A000073(n) then t^n  = T(n-1) + a(n)*t + T(n)*t^2, for n >= 0, with T(-1) = 1.
%F A001590 a(3*n) = Sum_{k+l+m=n} (n!/k!l!m!)*a(l+2*m). Example: a(12)=a(8)+4a(7)+10a(6)+16a(5)+19a(4)+16a(3)+10a(2)+4a(1)+a(0) The coefficients are the trinomial coefficients. T(n) and T(n-1) also satisfy this equation. (T(-1)=1)
%F A001590 From _Reinhard Zumkeller_, May 22 2006: (Start)
%F A001590 a(n) = A000073(n+1)-A000073(n);
%F A001590 a(n) = A000073(n-1)+A000073(n-2) for n>1;
%F A001590 A000213(n-2) = a(n+1)-a(n) for n>1. (End)
%F A001590 a(n) + a(n+1) = A000213(n). - _Philippe Deléham_, Sep 25 2006
%F A001590 If p[1]=0, p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n+1)=det A. - _Milan Janjic_, May 02 2010
%F A001590 For n>=4, a(n)=2*a(n-1)-a(n-4). - _Bob Selcoe_, Feb 18 2014
%F A001590 a(-1-n) = -A078046(n). - _Michael Somos_, Jun 01 2014
%F A001590 a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(3*r+1). - _Fabian Pereyra_, Nov 22 2024
%e A001590 a(12)=a(11)+a(10)+a(9): 230=125+68+37.
%e A001590 For n=5 the partitions of 5 are 1+1+1+1+1 (1 composition), 1+1+1+2 (4 compositions), 1+2+2 (3 compositions), 1+1+3 (not contrib because 3 is a part), 2+3 (no contrib because 3 is a part), 1+4 (2 compositions) and 5 (1 composition), total 1+4+3+2+1=11 =a(5+2) - _R. J. Mathar_, Jan 13 2023
%p A001590 seq(coeff(series(x*(1-x)/(1-x-x^2-x^3),x,n+1), x, n), n = 0 .. 40); # _Muniru A Asiru_, Oct 24 2018
%p A001590 # alternative
%p A001590 A001590 := proc(n)
%p A001590     option remember;
%p A001590     if n <=2 then
%p A001590         op(n+1,[0,1,0]) ;
%p A001590     else
%p A001590         procname(n-1)+procname(n-2)+procname(n-3) ;
%p A001590     end if;
%p A001590 end proc:
%p A001590 seq(A001590(n),n=0..30) ;# _R. J. Mathar_, Nov 22 2024
%t A001590 LinearRecurrence[{1,1,1}, {0,1,0}, 50] (* _Vladimir Joseph Stephan Orlovsky_, Jan 28 2012 *)
%t A001590 RecurrenceTable[{a[0]==0, a[1]==1, a[2]==0, a[n]==a[n-1]+a[n-2]+a[n-3]}, a, {n, 40}] (* _Vincenzo Librandi_, Apr 19 2018 *)
%o A001590 (PARI) a(n)=([0,1,0; 0,0,1; 1,1,1]^n*[0;1;0])[1,1] \\ _Charles R Greathouse IV_, Jul 28 2015
%o A001590 (Sage)
%o A001590 def A001590():
%o A001590     W = [0, 1, 0]
%o A001590     while True:
%o A001590         yield W[0]
%o A001590         W.append(sum(W))
%o A001590         W.pop(0)
%o A001590 a = A001590(); [next(a) for _ in range(38)]  # _Peter Luschny_, Sep 12 2016
%o A001590 (Magma) I:=[0,1,0]; [n le 3 select I[n]  else Self(n-1)+Self(n-2)+Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Apr 19 2018
%o A001590 (GAP) a:=[0,1,0];; 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 A001590 Cf. A000045, A000073, A027907, A027053, A078042, A145579, A278038.
%K A001590 nonn,easy
%O A001590 0,5
%A A001590 _N. J. A. Sloane_
%E A001590 Additional comments from _Miklos Kristof_, Jul 03 2002