login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000213 Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=a(2)=1.
(Formerly M2454 N0975)
144

%I M2454 N0975 #221 Jan 31 2024 08:03:00

%S 1,1,1,3,5,9,17,31,57,105,193,355,653,1201,2209,4063,7473,13745,25281,

%T 46499,85525,157305,289329,532159,978793,1800281,3311233,6090307,

%U 11201821,20603361,37895489,69700671,128199521,235795681,433695873,797691075,1467182629

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

%C Number of (n-1)-bit binary sequences with each one adjacent to a zero. - _R. H. Hardin_, Dec 24 2007

%C The binomial transform is A099216. The inverse binomial transform is (-1)^n*A124395(n). - _R. J. Mathar_, Aug 19 2008

%C Equals INVERT transform of (1, 0, 2, 0, 2, 0, 2, ...). a(6) = 17 = (1, 1, 1, 3, 5, 9) dot (0, 2, 0, 2, 0, 1) = (0 + 2 + 0 + 6 + 0 + 9) = 17. - _Gary W. Adamson_, Apr 27 2009

%C From _John M. Campbell_, May 16 2011: (Start)

%C Equals the number of tilings of a 2 X n grid using singletons and "S-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {2, 0}, {2, 1}, {3, 1}, {3, 2}, {1, 2}, {1, 1}, {0, 1}}]).

%C Also equals the number of tilings of a 2 X n grid using singletons and "T-shaped tetrominoes" (i.e., shapes of the form Polygon[{{0, 0}, {3, 0}, {3, 1}, {2, 1}, {2, 2}, {1, 2}, {1, 1}, {0, 1}}]). (End)

%C Pisano period lengths: 1, 1, 13, 4, 31, 13, 48, 8, 39, 31, 110, 52, 168, 48, 403, 16, 96, 39, 360, 124, ... (differs from A106293). - _R. J. Mathar_, Aug 10 2012

%C a(n) is the number of compositions of n with no consecutive 1's. a(4) = 5 because we have: 4, 3+1, 1+3, 2+2, 1+2+1. Cf. A239791, A003242. - _Geoffrey Critzer_, Mar 27 2014

%C a(n+2) is the number of words of length n over alphabet {1,2,3} without having {11,12,22,23} as substrings. - _Ran Pan_, Sep 16 2015

%C Satisfies Benford's law [see A186190]. - _N. J. A. Sloane_, Feb 09 2017

%C a(n) is also the number of dominating sets on the (n-1)-path graph. - _Eric W. Weisstein_, Mar 31 2017

%C a(n) is also the number of maximal irredundant sets and minimal dominating sets in the (2n-3)-triangular snake graph. - _Eric W. Weisstein_, Jun 09 2019

%C a(n) is also the number of anti-palindromic compositions of n, where a composition (c(1), c(2),..., c(k)) is anti-palindromic if c(i) is not equal to c(k+1-i) whenever 1 <= i <= k/2. For instance, there are a(4) = 5 anti-palindromic compositions of 4: 4, 31, 13, 211, 112. - _Jia Huang_, Apr 08 2023

%D Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.

%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 Indranil Ghosh, <a href="/A000213/b000213.txt">Table of n, a(n) for n = 0..3772</a> (terms 0..200 from T. D. Noe)

%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. See Table 1.

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

%H J.-L. Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.

%H B. G. Baumgart, Letter to the editor <a href="http://www.fq.math.ca/Scanned/2-4/baumgart-a.pdf">Part 1</a> <a href="http://www.fq.math.ca/Scanned/2-4/baumgart-b.pdf">Part 2</a> <a href="http://www.fq.math.ca/Scanned/2-4/baumgart-c.pdf">Part 3</a>, Fib. Quart. 2 (1964), 260, 302.

%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 Kenneth Edwards and Michael A. Allen, <a href="https://arxiv.org/abs/1907.06517">A new combinatorial interpretation of the Fibonacci numbers squared</a>, arXiv:1907.06517 [math.CO], 2019.

%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 Nick Hobson, <a href="/A000213/a000213.py.txt">Python program for this sequence</a>

%H Joanna Jaszunska and Jan Okninski, <a href="http://dx.doi.org/10.1016/j.jalgebra.2011.08.020">Structure of Chinese algebras</a>, Journal of Algebra, Volume 346, Issue 1, 15 November 2011, Pages 31-81.

%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 I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras, <a href="https://arxiv.org/abs/1911.10883">Chains with Small Intervals in the Lattice of Binary Paths</a>, arXiv:1911.10883 [math.CO], 2019.

%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/IrredundantSet.html">Irredundant Set</a>

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

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

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

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

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

%H <a href="/index/Be#Benford">Index entries for sequences related to Benford's law</a>

%F G.f.: (1-x)*(1+x)/(1-x-x^2-x^3). - _Ralf Stephan_, Feb 11 2004

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

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

%F a(n) = A001590(n+3) - A001590(n+2); a(n+1) - a(n) = 2*A000073(n); a(n) = A000073(n+3) - A000073(n+1). - _Reinhard Zumkeller_, May 22 2006

%F a(n) = A001590(n) + A001590(n+1). - _Philippe Deléham_, Sep 25 2006

%F a(n) ~ (F - 1) * T^n, where F = A086254 and T = A058265. - _Charles R Greathouse IV_, Nov 09 2008

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

%F a(n) = Sum_{m=0..n/2} Sum_{i=0..m} binomial(n-2*m+1,m-i)*binomial(n-2*m+i, n-2*m). - _Vladimir Kruchinin_, Dec 17 2011

%F a(n) = 2*A008937(n-2) + 1 for n > 1. - _Reinhard Zumkeller_, Apr 07 2012

%F G.f.: 1+x/(U(0) - x) where U(k) = 1 - x^2/(1 - 1/(1 + 1/U(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Nov 16 2012

%F G.f.: 1 + x + x^2/(G(0)-x) where G(k) = 1 - x*(2*k+1)/(1 - 1/(1 + (2*k+1)/G(k+1))); (continued fraction, 3-step). - _Sergei N. Gladkovskii_, Nov 17 2012

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

%F G.f.: 1/(1+x-G(0)), where G(k) = 1 - 1/(1 - x/(x - 1/(1 + 1/(1 - x/(x + 1/G(k+1)))))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 20 2013

%F a(n) = (-1)^n * A180735(-1-n) for all n in Z. - _Michael Somos_, Aug 15 2015

%e G.f. = 1 + x + x^2 + 3*x^3 + 5*x^4 + 9*x^5+ 17*x^6 + 31*x^7 + 57*x^8 + ...

%p K:=(1-z^2)/(1-z-z^2-z^3): Kser:=series(K, z=0, 45): seq((coeff(Kser, z, n)), n= 0..34); # _Zerinvary Lajos_, Nov 08 2007

%p A000213:=(z-1)*(1+z)/(-1+z+z**2+z**3); # _Simon Plouffe_ in his 1992 dissertation

%t LinearRecurrence[{1, 1, 1}, {1, 1, 1}, 45] (* _Harvey P. Dale_, May 23 2011 *)

%t Table[RootSum[-1 - # - #^2 + #^3 &, 2 #^n - 4 #^(n + 1) + 3 #^(n + 2) &]/11, {n, 0, 45}] (* _Eric W. Weisstein_, Apr 10 2018 *)

%t CoefficientList[Series[(1-x)(1+x)/(1-x-x^2-x^3), {x, 0, 45}], x] (* _Eric W. Weisstein_, Apr 10 2018 *)

%o (PARI) a(n)=tn=[1,1,1;1,0,0;0,1,0]^n;tn[3,1]+tn[3,2]+tn[3,3] \\ _Charles R Greathouse IV_, Feb 18 2011

%o (Maxima) a(n):=sum(sum(binomial(n-2*m+1,m-i)*binomial(n-2*m+i,n-2*m), i,0,m),m,0,(n)/2); /* _Vladimir Kruchinin_, Dec 17 2011 */

%o (Haskell)

%o a000213 n = a000213_list !! n

%o a000213_list = 1 : 1 : 1 : zipWith (+) a000213_list

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

%o -- _Reinhard Zumkeller_, Apr 07 2012

%o (Magma) I:=[1,1,1]; [n le 3 select I[n] else Self(n-1) + Self(n-2) + Self(n-3): n in [1..45]]; // _G. C. Greubel_, Jun 09 2019

%o (Sage) ((1-x^2)/(1-x-x^2-x^3)).series(x, 45).coefficients(x, sparse=False) # _G. C. Greubel_, Jun 09 2019

%o (GAP) a:=[1,1,1];; for n in [4..45] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # _G. C. Greubel_, Jun 09 2019

%o (Python)

%o alst = [1, 1, 1]

%o [alst.append(alst[n-1] + alst[n-2] + alst[n-3]) for n in range(3, 37)]

%o print(alst) # _Michael S. Branicky_, Sep 21 2021

%Y Cf. A000073, A000288, A000322, A000383, A046735, A060455, A180735, A186190.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:26 EDT 2024. Contains 371254 sequences. (Running on oeis4.)