|
|
A001590
|
|
Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=0, a(1)=1, a(2)=0.
(Formerly M0784 N0296)
|
|
130
|
|
|
0, 1, 0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, 4841, 8904, 16377, 30122, 55403, 101902, 187427, 344732, 634061, 1166220, 2145013, 3945294, 7256527, 13346834, 24548655, 45152016, 83047505, 152748176, 280947697, 516743378, 950439251
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
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
Starting with offset 3: (1, 2, 3, 6, 11, 10, 37, ...) = row sums of triangle A145579. - Gary W. Adamson, Oct 13 2008
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
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
Primes in the sequence are 2, 3, 11, 37, 634061, 7256527, ... in A231574. - R. J. Mathar, Aug 09 2012
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
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
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
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
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
|
|
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
|
M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
|
|
FORMULA
|
G.f.: x*(1-x)/(1-x-x^2-x^3).
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.
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)
A000213(n-2) = a(n+1)-a(n) for n>1. (End)
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
For n>=4, a(n)=2*a(n-1)-a(n-4). - Bob Selcoe, Feb 18 2014
|
|
EXAMPLE
|
a(12)=a(11)+a(10)+a(9): 230=125+68+37.
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
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Sage)
W = [0, 1, 0]
while True:
yield W[0]
W.append(sum(W))
W.pop(0)
(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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|