A000213 - OEIS (original) (raw)

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

COMMENTS

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

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

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

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

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.

B. G. Baumgart, Letter to the editor Part 1 Part 2 Part 3, Fib. Quart. 2 (1964), 260, 302.

Joanna Jaszunska and Jan Okninski, Structure of Chinese algebras, Journal of Algebra, Volume 346, Issue 1, 15 November 2011, Pages 31-81.

Eric Weisstein's World of Mathematics, Path Graph

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) = 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

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) = Sum_{r root of x^3-x^2-x-1} r^n/(-r^2+2*r+2). - Fabian Pereyra, Nov 21 2024

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

# Alternative:

MATHEMATICA

LinearRecurrence[{1, 1, 1}, {1, 1, 1}, 45] (* Harvey P. Dale, May 23 2011 *)

(* Alternative: *)

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

(* Alternative: *)

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))

(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

(SageMath) ((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)]