|
| |
|
|
A000073
|
|
Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1.
(Formerly M1074 N0406)
|
|
373
|
|
|
|
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Also (for n > 1) number of ordered trees with n+1 edges and having all leaves at level three. Example: a(4)=2 because we have two ordered trees with 5 edges and having all leaves at level three: (i) one edge emanating from the root, at the end of which two paths of length two are hanging and (ii) one path of length two emanating from the root, at the end of which three edges are hanging. - Emeric Deutsch, Jan 03 2004
a(n) is the number of compositions of n-2 with no part greater than 3. Example: a(5)=4 because we have 1+1+1 = 1+2 = 2+1 = 3. - Emeric Deutsch, Mar 10 2004
Let A denote the 3 X 3 matrix [0,0,1;1,1,1;0,1,0]. a(n) corresponds to both the (1,2) and (3,1) entries in A^n. - Paul Barry, Oct 15 2004
Number of permutations satisfying -k <= p(i)-i <= r, i=1..n-2, with k=1, r=2. - Vladimir Baltic, Jan 17 2005
Number of binary sequences of length n-3 that have no three consecutive 0's. Example: a(7)=13 because among the 16 binary sequences of length 4 only 0000, 0001 and 1000 have 3 consecutive 0's. - Emeric Deutsch, Apr 27 2006
Therefore, the complementary sequence to A050231 (n coin tosses with a run of three heads). a(n) = 2^(n-3) - A050231(n-3) - Toby Gottfried, Nov 21 2010
a(n+2) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 0, 0, 1; 1, 0, 0] or [1, 1, 0; 1, 0, 1; 1, 0, 0] or [1, 1, 1; 1, 0, 0; 0, 1, 0] or [1, 0, 1; 1, 0, 0; 1, 1, 0]. - R. J. Mathar, Feb 03 2014
a(n-1) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 0, 1; 1, 1, 1; 0, 1, 0], [0, 1, 0; 0, 1, 1; 1, 1, 0], [0, 0, 1; 1, 0, 1; 0, 1, 1] or [0, 1, 0; 0, 0, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
The nonnegative powers of the tribonacci constant t = A058265 are t^n = a(n)*t^2 + (a(n-1) + a(n-2))*t + a(n-1)*1, for n >= 0, with a(-1) = 1 and a(-2) = -1. This follows from the recurrences derived from t^3 = t^2 + t + 1. See the example in A058265 for the first nonnegative powers. For the negative powers see A319200. - Wolfdieter Lang, Oct 23 2018
The term "tribonacci number" was coined by Mark Feinberg (1963), a 14-year-old student in the 9th grade of the Susquehanna Township Junior High School in Pennsylvania. He died in 1967 in a motorcycle accident. - Amiram Eldar, Apr 16 2021
Andrews, Just, and Simay (2021, 2022) remark that it has been suggested that this sequence is mentioned in Charles Darwin's Origin of Species as bearing the same relation to elephant populations as the Fibonacci numbers do to rabbit populations. - N. J. A. Sloane, Jul 12 2022
|
|
|
REFERENCES
|
M. Agronomof, Sur une suite récurrente, Mathesis (Series 4), Vol. 4 (1914), pp. 125-126.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.
S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
Raphael Schumacher, Explicit formulas for sums involving the squares of the first n Tribonacci numbers, Fib. Q., 58:3 (2020), 194-202.
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.
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016.
Curtis Cooper, S. Miller, P. Moses, M. Sahin, et al., On Identities Of Ruggles, Horadam, Howard, and Young, Preprint, 2016; Proceedings of the 17th International Conference on Fibonacci Numbers and Their Applications, Université de Caen-Normandie, Caen, France, June 26 to July 2, 2016.
Christian Ennis, William Holland, Omer Mujawar, Aadit Narayanan, Frank Neubrander, Marie Neubrander, and Christina Simino, Words in Random Binary Sequences I, arXiv:2107.01029 [math.GM], 2021.
M. Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
O. Martin, A. M. Odlyzko and S. Wolfram, Algebraic properties of cellular automata, Comm. Math. Physics, 93 (1984), pp. 219-258, Reprinted in Theory and Applications of Cellular Automata, S. Wolfram, Ed., World Scientific, 1986, pp. 51-90 and in Cellular Automata and Complexity: Collected Papers of Stephen Wolfram, Addison-Wesley, 1994, pp. 71-113. See Eq. 5.5b.
|
|
|
FORMULA
|
G.f.: x^2/(1 - x - x^2 - x^3).
G.f.: x^2 / (1 - x / (1 - x / (1 + x^2 / (1 + x)))). - Michael Somos, May 12 2012
G.f.: Sum_{n >= 0} x^(n+2) *[ Product_{k = 1..n} (k + k*x + x^2)/(1 + k*x + k*x^2) ] = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + ... may be proved by the method of telescoping sums. - Peter Bala, Jan 04 2015
a(n) = central term in M^n * [1 0 0] where M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 1 1]. (M^n * [1 0 0] = [a(n-1) a(n) a(n+1)].) a(n)/a(n-1) tends to the tribonacci constant, 1.839286755... = A058265, an eigenvalue of M and a root of x^3 - x^2 - x - 1 = 0. - Gary W. Adamson, Dec 17 2004
a(n+2) = Sum_{k=0..n} T(n-k, k), where T(n, k) = trinomial coefficients (A027907). - Paul Barry, Feb 15 2005
Let C = the tribonacci constant, 1.83928675...; then C^n = a(n)*(1/C) + a(n+1)*(1/C + 1/C^2) + a(n+2)*(1/C + 1/C^2 + 1/C^3). Example: C^4 = 11.444...= 2*(1/C) + 4*(1/C + 1/C^2) + 7*(1/C + 1/C^2 + 1/C^3). - Gary W. Adamson, Nov 05 2006
a(n) = j*C^n + k*r1^n + L*r2^n where C is the tribonacci constant (C = 1.8392867552...), real root of x^3-x^2-x-1=0, and r1 and r2 are the two other roots (which are complex), r1 = m+p*i and r2 = m-p*i, where i = sqrt(-1), m = (1-C)/2 (m = -0.4196433776...) and p = ((3*C-5)*(C+1)/4)^(1/2) = 0.6062907292..., and where j = 1/((C-m)^2 + p^2) = 0.1828035330..., k = a+b*i, and L = a-b*i, where a = -j/2 = -0.0914017665... and b = (C-m)/(2*p*((C-m)^2 + p^2) = 0.3405465308... . - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007
a(n+1) = 3*c*((1/3)*(a+b+1))^n/(c^2-2*c+4) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3), c=(586+102*sqrt(33))^(1/3). Round to the nearest integer. - Al Hakanson (hawkuu(AT)gmail.com), Feb 02 2009
a(n) = round(3*((a+b+1)/3)^n/(a^2+b^2+4)) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3).. - Anton Nikonov
Another form of the g.f.: f(z) = (z^2-z^3)/(1-2*z+z^4). Then we obtain a(n) as a sum: a(n) = Sum_{i=0..floor((n-2)/4)} ((-1)^i*binomial(n-2-3*i,i)*2^(n-2-4*i)) - Sum_{i=0..floor((n-3)/4)} ((-1)^i*binomial(n-3-3*i,i)*2^(n-3-4*i)) with natural convention: Sum_{i=m..n} alpha(i) = 0 for m > n. - Richard Choulet, Feb 22 2010
a(n) = Sum_{k=1..n} Sum_{i=k..n, mod(4*k-i,3)=0} binomial(k,(4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1,k-1)). - Vladimir Kruchinin, Aug 18 2010
a(n) = 2*a(n-2) + 2*a(n-3) + a(n-4). - Gary Detlefs, Sep 13 2010
a(n) = 2*a(n-1) - a(n-4), with a(0)=a(1)=0, a(2)=a(3)=1. - Vincenzo Librandi, Dec 20 2010
Starting (1, 2, 4, 7, ...) is the INVERT transform of (1, 1, 1, 0, 0, 0, ...). - Gary W. Adamson, May 13 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x + x^2)/( x*(4*k+3 + x + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 09 2013
a(n+2) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2*j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
Sum_{k=0..n} (n-k)*a(k) = (a(n+2) + a(n+1) - n - 1)/2. - Yichen Wang, Aug 20 2020
Sum_{k=0..n} a(k) = (a(n+2) + a(n) - 1)/2.
Sum_{k=0..n} k*a(k) = ((n-1)*a(n+2) - a(n+1) + n*a(n) + 1)/2. (End)
For n > 1, a(n) = b(n) where b(1) = 1 and then b(n) = Sum_{k=1..n-1} b(n-k)*A000931(k+2). - J. Conrad, Nov 24 2022
Conjecture: the congruence a(n*p^(k+1)) + a(n*p^k) + a(n*p^(k-1)) == 0 (mod p^k) holds for positive integers k and n and for all the primes p listed in A106282. - Peter Bala, Dec 28 2022
|
|
|
EXAMPLE
|
G.f. = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + 24*x^8 + 44*x^9 + 81*x^10 + ...
|
|
|
MAPLE
|
a:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1, 3]:
# second Maple program:
A000073:=proc(n) option remember; if n <= 1 then 0 elif n=2 then 1 else procname(n-1)+procname(n-2)+procname(n-3); fi; end; # N. J. A. Sloane, Aug 06 2018
|
|
|
MATHEMATICA
|
CoefficientList[Series[x^2/(1 - x - x^2 - x^3), {x, 0, 50}], x]
a[0] = a[1] = 0; a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3]; Array[a, 36, 0] (* Robert G. Wilson v, Nov 07 2010 *)
a[n_] := SeriesCoefficient[If[ n < 0, x/(1 + x + x^2 - x^3), x^2/(1 - x - x^2 - x^3)], {x, 0, Abs @ n}] (* Michael Somos, Jun 01 2013 *)
Table[-RootSum[-1 - # - #^2 + #^3 &, -#^n - 9 #^(n + 1) + 4 #^(n + 2) &]/22, {n, 0, 20}] (* Eric W. Weisstein, Nov 09 2017 *)
|
|
|
PROG
|
(PARI) {a(n) = polcoeff( if( n<0, x / ( 1 + x + x^2 - x^3), x^2 / ( 1 - x - x^2 - x^3) ) + x * O(x^abs(n)), abs(n))}; /* Michael Somos, Sep 03 2007 */
(PARI) x='x+O('x^99); concat([0, 0], Vec(x^2/(1-x-x^2-x^3))) \\ Altug Alkan, Apr 04 2016
(PARI) a(n)=([0, 1, 0; 0, 0, 1; 1, 1, 1]^n)[1, 3] \\ Charles R Greathouse IV, Apr 18 2016, simplified by M. F. Hasler, Apr 18 2018
(Maxima) a(n):=sum(sum(if mod(4*k-i, 3)>0 then 0 else binomial(k, (4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1, k-1), i, k, n), k, 1, n); \\ Vladimir Kruchinin, Aug 18 2010
(Haskell)
a000073 n = a000073_list !! n
a000073_list = 0 : 0 : 1 : zipWith (+) a000073_list (tail
(zipWith (+) a000073_list $ tail a000073_list))
(Python)
def a(n, adict={0:0, 1:0, 2:1}):
if n in adict:
return adict[n]
adict[n]=a(n-1)+a(n-2)+a(n-3)
from functools import cache
@cache
if n <= 1: return 0
if n == 2: return 1
(Magma) [n le 3 select Floor(n/3) else Self(n-1)+Self(n-2)+Self(n-3): n in [1..70]]; // Vincenzo Librandi, Jan 29 2016
(GAP) a:=[0, 0, 1];; 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
|
Cf. A000045, A000078, A000213, A000931, A001590 (first differences, also a(n)+a(n+1)), A001644, A008288 (tribonacci triangle), A008937 (partial sums), A021913, A027024, A027083, A027084, A046738 (Pisano periods), A050231, A054668, A062544, A063401, A077902, A081172, A089068, A118390, A145027, A153462, A230216.
Row 3 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021
|
|
|
STATUS
|
approved
|
| |
|
|
