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)
145
1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, 85525, 157305, 289329, 532159, 978793, 1800281, 3311233, 6090307, 11201821, 20603361, 37895489, 69700671, 128199521, 235795681, 433695873, 797691075, 1467182629 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Number of (n-1)-bit binary sequences with each one adjacent to a zero. - R. H. Hardin, Dec 24 2007
The binomial transform is A099216. The inverse binomial transform is (-1)^n*A124395(n). - R. J. Mathar, Aug 19 2008
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
From John M. Campbell, May 16 2011: (Start)
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}}]).
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)
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
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
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
Satisfies Benford's law [see A186190]. - N. J. A. Sloane, Feb 09 2017
a(n) is also the number of dominating sets on the (n-1)-path graph. - Eric W. Weisstein, Mar 31 2017
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
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
REFERENCES
Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
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).
LINKS
Indranil Ghosh, Table of n, a(n) for n = 0..3772 (terms 0..200 from T. D. Noe)
George E. Andrews, Matthew Just, and Greg Simay, Anti-palindromic compositions, arXiv:2102.01613 [math.CO], 2021. Also Fib. Q., 60:2 (2022), 164-176. See Table 1.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
B. G. Baumgart, Letter to the editor Part 1 Part 2 Part 3, Fib. Quart. 2 (1964), 260, 302.
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.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
M. Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(#3) (1963), 71-74.
Joanna Jaszunska and Jan Okninski, Structure of Chinese algebras, Journal of Algebra, Volume 346, Issue 1, 15 November 2011, Pages 31-81.
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
I. Tasoulas, K. Manes, A. Sapounakis, and P. Tsikouras, Chains with Small Intervals in the Lattice of Binary Paths, arXiv:1911.10883 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, Minimal Dominating Set
Eric Weisstein's World of Mathematics, Path Graph
Eric Weisstein's World of Mathematics, Triangular Snake Graph
Eric Weisstein's World of Mathematics, Tribonacci Number
FORMULA
G.f.: (1-x)*(1+x)/(1-x-x^2-x^3). - Ralf Stephan, Feb 11 2004
G.f.: 1 / (1 - x / (1 - 2*x^2 / (1 + x^2))). - Michael Somos, May 12 2012
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
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
a(n) = A001590(n) + A001590(n+1). - Philippe Deléham, Sep 25 2006
a(n) ~ (F - 1) * T^n, where F = A086254 and T = A058265. - Charles R Greathouse IV, Nov 09 2008
a(n) = 2*a(n-1) - a(n-4), n > 3. - Gary Detlefs, Sep 13 2010
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
a(n) = 2*A008937(n-2) + 1 for n > 1. - Reinhard Zumkeller, Apr 07 2012
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
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
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
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
a(n) = (-1)^n * A180735(-1-n) for all n in Z. - Michael Somos, Aug 15 2015
EXAMPLE
G.f. = 1 + x + x^2 + 3*x^3 + 5*x^4 + 9*x^5+ 17*x^6 + 31*x^7 + 57*x^8 + ...
MAPLE
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
A000213:=(z-1)*(1+z)/(-1+z+z**2+z**3); # Simon Plouffe in his 1992 dissertation
MATHEMATICA
LinearRecurrence[{1, 1, 1}, {1, 1, 1}, 45] (* Harvey P. Dale, May 23 2011 *)
Table[RootSum[-1 - # - #^2 + #^3 &, 2 #^n - 4 #^(n + 1) + 3 #^(n + 2) &]/11, {n, 0, 45}] (* Eric W. Weisstein, Apr 10 2018 *)
CoefficientList[Series[(1-x)(1+x)/(1-x-x^2-x^3), {x, 0, 45}], x] (* Eric W. Weisstein, Apr 10 2018 *)
PROG
(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
(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 */
(Haskell)
a000213 n = a000213_list !! n
a000213_list = 1 : 1 : 1 : zipWith (+) a000213_list
(tail $ zipWith (+) a000213_list (tail a000213_list))
-- Reinhard Zumkeller, Apr 07 2012
(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
(Sage) ((1-x^2)/(1-x-x^2-x^3)).series(x, 45).coefficients(x, sparse=False) # G. C. Greubel, Jun 09 2019
(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
(Python)
alst = [1, 1, 1]
[alst.append(alst[n-1] + alst[n-2] + alst[n-3]) for n in range(3, 37)]
print(alst) # Michael S. Branicky, Sep 21 2021
CROSSREFS
Sequence in context: A102475 A066173 A114322 * A074858 A074860 A297300
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved

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 February 28 14:45 EST 2024. Contains 370400 sequences. (Running on oeis4.)