A008937 -id:A008937 - cp's OEIS frontend

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.

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

Offset: 0

N. J. A. Sloane

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
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
Convolved with the Padovan sequence = row sums of triangle A153462. - Gary W. Adamson, Dec 27 2008
For n > 1: row sums of the triangle in A157897. - Reinhard Zumkeller, Jun 25 2009
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
Also row sums of A082601 and of A082870. - Reinhard Zumkeller, Apr 13 2014
Least significant bits are given in A021913 (a(n) mod 2 = A021913(n)). - Andres Cicuttin, Apr 04 2016
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

			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 + ...

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

Simone Sandri, Table of n, a(n) for n = 0..3000 (first 200 terms from T. D. Noe)
Marco Abrate, Stefano Barbero, Umberto Cerruti, and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", arXiv:1409.6454 [math.NT], 2014; Discrete Math. 335 (2014), 1-7. MR3248794
Abdullah Açikel, Amrouche Said, Hacene Belbachir, and Nurettin Irmak, On k-generalized Lucas sequence with its triangle, Turkish J. Math. (2023) Vol. 47, No. 4, Art. 6, 1129-1143. See p. 1130.
Kunle Adegoke, Adenike Olatinwo, and Winning Oyekanmi, New Tribonacci Recurrence Relations and Addition Formulas, arXiv:1811.03663 [math.CO], 2018.
Adel Alahmadi and Florian Luca, On Tribonacci Numbers that are Products of Factorials, J. Int. Seq., Vol. 26 (2023), Article 23.2.2.
Said Amrouche and Hacène Belbachir, Unimodality and linear recurrences associated with rays in the Delannoy triangle, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.
Pornpawee Anantakitpaisal and Kantaphon Kuhapatanakul, Reciprocal Sums of the Tribonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.2.1.
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.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 2, 6.
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
Joerg Arndt, Matters Computational (The Fxtbook), pp.307-309.
J. L. Arocha and B. Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv:1601.01268 [math.CO], 2016.
Christos Athanasiadis, Jesús De Loera, and Zhenyang Zhang, Enumerative problems for arborescences and monotone paths on polytopes, arXiv:2002.00999 [math.CO], 2020.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No. 1 (April 2010), 119-135.
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 2.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, arXiv:1405.7727 [math.CO], 2014.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.
Eric Fernando Bravo, On concatenations of Padovan and Perrin numbers, Math. Commun. (2023) Vol 28, 105-119.
David Broadhurst, Multiple Landen values and the tribonacci numbers, arXiv:1504.05303 [hep-th], 2015.
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.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
L. Carlitz, R. Scoville and V. E. Hoggatt, Jr., Fibonacci representations of higher order, Fib. Quart., 10 (1972), 43-69.
Nataliya Chekhova, Pascal Hubert, and Ali Messaoudi, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, Journal de théorie des nombres de Bordeaux, 13(2) (2001), 371-394.
Fan R. K. Chung, Persi Diaconis, and Ron Graham, Permanental generating functions and sequential importance sampling, Stanford University (2018).
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.
Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19(3) (2012), Paper 22, 21 pp., MR2967227.
Mahadi Ddamulira, Tribonacci numbers that are concatenations of two repdigits, hal-02547159, Mathematics [math] / Number Theory [math.NT], 2020.
F. Michel Dekking, Jeffrey Shallit, and N. J. A. Sloane, Queens in exile: non-attacking queens on infinite chess boards, Electronic J. Combin., 27(1) (2020), #P1.52.
Ömür Deveci, Zafer Adıgüzel, and Taha Doğan, On the Generalized Fibonacci-circulant-Hurwitz numbers, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 1, 179-190.
Gregory P. B. Dresden and Zhaohui Du, A Simplified Binet Formula for k-Generalized Fibonacci Numbers, J. Int. Seq. 17 (2014) # 14.4.7.
Mohamed S. El Naschie, Statistical geometry of a Cantor discretum and semiconductors, Computers & Mathematics with Applications, Vol. 29 (Issue 12, June 1995), 103-110.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
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.
Tim Evink and Paul Alexander Helminck, Tribonacci numbers and primes of the form p=x^2+11y^2, arXiv:1801.04605 [math.NT], 2018.
Vinicius Facó and D. Marques, Tribonacci Numbers and the Brocard-Ramanujan Equation, Journal of Integer Sequences, 19 (2016), #16.4.4.
Mark Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(3) (1963), 71-74.
Mark Feinberg, New slants, Fib. Quart. 2 (1964), 223-227.
Robert Frontczak, Sums of Tribonacci and Tribonacci-Lucas Numbers, International Journal of Mathematical Analysis, 12(1) (2018), 19-24.
Robert Frontczak, Convolutions for Generalized Tribonacci Numbers and Related Results, International Journal of Mathematical Analysis, 12(7) (2018), 307-324.
Taras Goy and Mark Shattuck, Determinant identities for Toeplitz-Hessenberg matrices with tribonacci number entries, Transactions on Combinatorics 9(3) (2020), 89-109. See also arXiv:2003.10660, [math.CO], 2020.
Hans-Christian Herbig, Pivotal condensation and chemical balancing, hal-04091017 [math] 2023.
Michael D. Hirschhorn, Coupled third-order recurrences, Fib. Quart., 44 (2006), 26-31.
F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), no. 3, 231-243.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
Bahar Kuloğlu and Engin Özkan, d-Tribonacci Polynomials and Their Matrix Representations, WSEAS Trans. Math. (2023) Vol. 22, 204-212.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 10
Nurettin Irmak and László Szalay, Tribonacci Numbers Close to the Sum 2^a+3^b+5^c, Math. Scand. 118(1) (2016), 27-32.
Milan Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5. - _N. J. A. Sloane_, Sep 16 2012
Günter Köhler, Generating functions of Fibonacci-like sequences and decimal expansion of some fractions, The Fibonacci Quarterly 23(1) (1985), 29-35 [a(n+2) = T_n on p. 35].
S. Kak, The Golden Mean and the Physics of Aesthetics, arXiv:physics/0411195 [physics.hist-ph], 2004.
Tamara Kogan, L. Sapir, A. Sapir, and A. Sapir, The Fibonacci family of iterative processes for solving nonlinear equations, Applied Numerical Mathematics 110 (2016), 148-158.
Takao Komatsu, Convolution identities for tribonacci-type numbers with arbitrary initial values, Palestine Journal of Mathematics, Vol. 8(2) (2019), 413-417.
T. Komatsu and V. Laohakosol, On the Sum of Reciprocals of Numbers Satisfying a Recurrence Relation of Order s, J. Int. Seq. 13 (2010), #10.5.8.
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
Wolfdieter Lang, The Tribonacci and ABC Representations of Numbers are Equivalent, arXiv preprint arXiv:1810.09787 [math.NT], 2018.
Pin-Yen Lin, De Moivre type identities for the Tribonacci numbers, The Fibonacci Quarterly, 26(2) (1988), 131-134.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
Sepideh Maleki and Martin Burtscher, Automatic Hierarchical Parallelization of Linear Recurrences, Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems, ACM, 2018.
T. Mansour, Permutations avoiding a set of patterns from S_3 and a pattern from S_4, arXiv:math/9909019 [math.CO], 1999.
T. Mansour and M. Shattuck, Polynomials whose coefficients are generalized Tribonacci numbers, Applied Mathematics and Computation, Volume 219(15) (2013), 8366-8374.
T. Mansour and M. Shattuck, A monotonicity property for generalized Fibonacci sequences, arXiv:1410.6943 [math.CO], 2014.
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.
László Németh, The trinomial transform triangle, J. Int. Seqs., Vol. 21 (2018), Article 18.7.3. Also arXiv:1807.07109 [math.NT], 2018.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, 8 (2005), Article 05.4.4.
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.
János Podani, Ádám Kun and András Szilágyi, How fast does Darwin’s elephant population grow?, Journal of the History of Biology, Vol. 51, No. 2 (2018), pp. 259-281.
H. Prodinger, Counting Palindromes According to r-Runs of Ones Using Generating Functions, J. Int. Seq. 17 (2014) # 14.6.2, odd length middle 0 with r=2.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
J. L. Ramirez and V. F. Sirvent, Incomplete Tribonacci Numbers and Polynomials, Journal of Integer Sequences, 17 (2014), #14.4.2.
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Michel Rigo, Relations on words, arXiv:1602.03364 [cs.FL], 2016.
Raphael Schumacher, Explicit formulas for sums involving the squares of the first n Tribonacci numbers, Fib. Q., 58:3 (2020), 194-202.
Jeffrey Shallit, Some Tribonacci conjectures, arXiv:2210.03996 [math.CO], 2022.
A. G. Shannon, Tribonacci numbers and Pascal's pyramid, part b, Fibonacci Quart. 15(3) (1977), 268-275.
M. Shattuck, Combinatorial identities for incomplete tribonacci polynomials, arXiv:1406.2755 [math.CO], 2014.
W. R. Spickerman, Binet's formula for the tribonacci sequence, The Fibonacci Quarterly 20(2) (1982), 118-120.
H. J. H. Tuenter, In Search of Comrade Agronomof: Some Tribonacci History, The American Mathematical Monthly, 130(8):708-719, October 2023.
M. E. Waddill and L. Sacks, Another generalized Fibonacci sequence, Fib. Quart., 5 (1967), 209-222.
Hsin-Po Wang and Chi-Wei Chin, On Counting Subsequences and Higher-Order Fibonacci Numbers, arXiv:2405.17499 [cs.IT], 2024. See p. 2.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Eric Weisstein's World of Mathematics, Tribonacci Number.
Wikipedia, Generalizations of Fibonacci numbers.
Ce Xu and Jianqiang Zhao, Alternating Multiple T-Values: Weighted Sums, Duality, and Dimension Conjecture, arXiv:2009.10774 [math.NT], 2020.
Shujie Zhou and Li Chen, Tribonacci Numbers and Some Related Interesting Identities, Symmetry, 11(10) (2019), 1195.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

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.
A057597 is this sequence run backwards: A057597(n) = a(1-n).
Row 3 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
Partitions: A240844 and A117546.
Cf. also A092836 (subsequence of primes), A299399 = A092835 + 1 (indices of primes).

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

a000073 n = a000073_list !! n
a000073_list = 0 : 0 : 1 : zipWith (+) a000073_list (tail
                          (zipWith (+) a000073_list $ tail a000073_list))
-- Reinhard Zumkeller, Dec 12 2011

[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

a:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1,3]:
seq(a(n), n=0..40);  # Alois P. Heinz, Dec 19 2016
# 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

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 *)
LinearRecurrence[{1, 1, 1}, {0, 0, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, May 24 2011 *)
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 *)

A000073[0]:0$
A000073[1]:0$
A000073[2]:1$
A000073[n]:=A000073[n-1]+A000073[n-2]+A000073[n-3]$
  makelist(A000073[n], n, 0, 40);  /* Emanuele Munarini, Mar 01 2011 */

{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 */

my(x='x+O('x^99)); concat([0, 0], Vec(x^2/(1-x-x^2-x^3))) \\ Altug Alkan, Apr 04 2016

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

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)
    return adict[n] # David Nacin, Mar 07 2012
from functools import cache
@cache
def A000073(n: int) -> int:
    if n <= 1: return 0
    if n == 2: return 1
    return A000073(n-1) + A000073(n-2) + A000073(n-3) # Peter Luschny, Nov 21 2022

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+1)/a(n) -> A058265.  a(n-1)/a(n) -> A192918.
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
A001590(n) = a(n+1) - a(n); A001590(n) = a(n-1) + a(n-2) for n > 1; a(n) = (A000213(n+1) - A000213(n))/2; A000213(n-1) = a(n+2) - a(n) for n > 0. - Reinhard Zumkeller, May 22 2006
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+2) = Sum_{k=0..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
Sum_{k=0..2*n} a(k+b)*A027907(n,k) = a(3*n+b), b >= 0 (see A099464, A074581).
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. See A062544. - Yichen Wang, Aug 20 2020
a(n) = A008937(n-1) - A008937(n-2) for n >= 2. - Peter Luschny, Aug 20 2020
From Yichen Wang, Aug 27 2020: (Start)
Sum_{k=0..n} a(k) = (a(n+2) + a(n) - 1)/2. See A008937.
Sum_{k=0..n} k*a(k) = ((n-1)*a(n+2) - a(n+1) + n*a(n) + 1)/2. See A337282. (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
Sum_{k=0..n} k^2*a(k) = ((n^2-4*n+6)*a(n+1) - (2*n^2-2*n+5)*a(n) + (n^2-2*n+3)*a(n-1) - 3)/2. - Prabha Sivaramannair, Feb 10 2024
a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(3*r^2-2*r-1). - Fabian Pereyra, Nov 23 2024

Minor edits by M. F. Hasler, Apr 18 2018

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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

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

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

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.
Joerg Arndt, Matters Computational (The Fxtbook), p.312
Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Jean-Luc Baril and Nathanaël Hassler, Intervals in a family of Fibonacci lattices, Univ. de Bourgogne (France, 2024). See p. 7.
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.
Mark Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(#3) (1963), 71-74.
Nick Hobson, Python program for this sequence
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
Index entries for linear recurrences with constant coefficients, signature (1,1,1).
Index entries for sequences related to Benford's law

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

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

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

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

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

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

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 */

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

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

((1-x^2)/(1-x-x^2-x^3)).series(x, 45).coefficients(x, sparse=False) # G. C. Greubel, Jun 09 2019

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

A140994 Triangle G(n, k), for 0 <= k <= n, read by rows, where G(n, n) = G(n+1, 0) = 1, G(n+2, 1) = 2, G(n+3, 2) = 4, G(n+4, m) = G(n+1, m-2) + G(n+1, m-3) + G(n+2, m-2) + G(n+3, m-1) for n >= 0 and m = 3..(n+3).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 4, 8, 1, 1, 2, 4, 9, 15, 1, 1, 2, 4, 9, 19, 28, 1, 1, 2, 4, 9, 19, 40, 52, 1, 1, 2, 4, 9, 19, 41, 83, 96, 1, 1, 2, 4, 9, 19, 41, 88, 170, 177, 1, 1, 2, 4, 9, 19, 41, 88, 188, 345, 326, 1, 1, 2, 4, 9, 19, 41, 88, 189, 400, 694, 600, 1, 1, 2, 4, 9, 19, 41, 88, 189, 406, 846, 1386, 1104, 1

Offset: 0

Juri-Stepan Gerasimov, Jul 08 2008

From Petros Hadjicostas, Jun 12 2019: (Start)
This is a mirror image of the triangular array A140997. The current array has index of asymmetry s = 2 and index of obliqueness (obliquity) e = 1. Array A140997 has the same index of asymmetry, but has index of obliqueness e = 0. (In other related sequences, the author uses the letter y for the index of asymmetry and the letter z for the index of obliqueness, but on the stone slab that appears over a tomb in a picture that he posted in those sequences, the letters s and e are used instead. See, for example, the documentation for sequences A140998, A141065, A141066, and A141067.)
In general, if the index of asymmetry (from the Pascal triangle A007318) is s, then the order of the recurrence is s + 2 (because the recurrence of the Pascal triangle has order 2). There are also s + 2 infinite sets of initial conditions (as opposed to the Pascal triangle, which has only 2 infinite sets of initial conditions, namely, G(n, 0) = G(n+1, n+1) = 1 for n >= 0).
Pascal's triangle A007318 has s = 0 and is symmetric, arrays A140998 and A140993 have s = 1 (with e = 0 and e = 1, respectively), and arrays A140996 and A140995 have s = 3 (with e = 0 and e = 1, respectively).
If A(x,y) = Sum_{n,k >= 0} G(n, k)*x^n*y^k is the bivariate g.f. for this array (with G(n, k) = 0 for 0 <= n < k) and B(x, y) = Sum_{n, k} A140997(n, k)*x^n*y^k, then A(x, y) = B(x*y, y^(-1)). This can be proved using formal manipulation of double series expansions and the fact G(n, k) = A140997(n, n-k) for 0 <= k <= n.
If we let b(k) = lim_{n -> infinity} G(n, k) for k >= 0, then b(0) = 1, b(1) = 2, b(2) = 4, and b(k) = b(k-1) + 2*b(k-2) + b(k-3) for k >= 3. (The existence of the limit can be proved by induction on k.) It follows that b(k) = A141015(k) for k >= 0.
(End)

			Triangle begins:
  1
  1 1
  1 2 1
  1 2 4 1
  1 2 4 8 1
  1 2 4 9 15  1
  1 2 4 9 19 28  1
  1 2 4 9 19 40 52   1
  1 2 4 9 19 41 83  96   1
  1 2 4 9 19 41 88 170 177    1
  1 2 4 9 19 41 88 188 345  326    1
  1 2 4 9 19 41 88 189 400  694  600    1
  1 2 4 9 19 41 88 189 406  846 1386 1104 1
... [corrected by _Petros Hadjicostas_, Jun 12 2019]
E.g., G(12, 9) = G(9, 7) + G(9, 6) + G(10, 7) + G(11, 8) = 170 + 88 + 188 + 400 = 846.

Robert Price, Table of n, a(n) for n = 0..1325
Juri-Stepan Gerasimov, Stepan's triangles and Pascal's triangle are connected by the recurrence relation ...

Cf. A007318, A008937, A140993, A140995, A140996, A140997, A140998, A141015, A141018, A141020, A141021, A141031, A141065, A141066, A141067.

G := proc(n,k) if k=0 or n =k then 1; elif k= 1 then 2 ; elif k =2 then 4; elif k > n or k < 0 then 0 ; else procname(n-3,k-2)+procname(n-3,k-3)+procname(n-2,k-2)+procname(n-1,k-1) ; end if; end proc: seq(seq(G(n,k),k=0..n),n=0..15) ; # R. J. Mathar, Apr 14 2010

nlim = 50;
Do[G[n, 0] = 1, {n, 0, nlim}];
Do[G[n, n] = 1, {n, 1, nlim}];
Do[G[n + 2, 1] = 2, {n, 0, nlim}];
Do[G[n + 3, 2] = 4, {n, 0, nlim}];
Do[G[n + 4, m] =
   G[n + 1, m - 2] + G[n + 1, m - 3] + G[n + 2, m - 2] +
    G[n + 3, m - 1], {n, 0, nlim}, {m, 3, n + 3}];
A140994 = {}; For[n = 0, n <= nlim, n++,
 For[k = 0, k <= n, k++, AppendTo[A140994, G[n, k]]]];
A140994 (* Robert Price, Aug 19 2019 *)

From Petros Hadjicostas, Jun 12 2019: (Start)
G(n, k) = A140997(n, n-k) for 0 <= k <= n.
Bivariate g.f.: Sum_{n,k >= 0} G(n, k)*x^n*y^k = (x^4*y^3 - x^3*y^3 - x^2*y^2 + x^2*y - x*y + 1)/((1- x*y)*(1 - x)*(1- x*y - x^2*y^2 - x^3*y^3 - x^3*y^2)).
(End)

Entries checked by R. J. Mathar, Apr 14 2010

A140997 Triangle G(n,k) read by rows, for 0 <= k <= n, where G(n, 0) = G(n+1, n+1) = 1, G(n+2, n+1) = 2, G(n+3, n+1) = 4, and G(n+4, m) = G(n+1, m-1) + G(n+1, m) + G(n+2, m) + G(n+3, m) for n >= 0 and m = 1..n+1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 4, 2, 1, 1, 15, 9, 4, 2, 1, 1, 28, 19, 9, 4, 2, 1, 1, 52, 40, 19, 9, 4, 2, 1, 1, 96, 83, 41, 19, 9, 4, 2, 1, 1, 177, 170, 88, 41, 19, 9, 4, 2, 1, 1, 326, 345, 188, 88, 41, 19, 9, 4, 2, 1, 1, 600, 694, 400, 189, 88, 41, 19, 9, 4, 2, 1, 1, 1104, 1386, 846, 406, 189, 88, 41, 19, 9, 4, 2, 1, 1, 2031, 2751, 1779, 871, 406, 189, 88, 41, 19, 9, 4, 2, 1, 1, 3736, 5431, 3719, 1866, 872, 406, 189, 88, 41, 19, 9, 4, 2, 1

Offset: 0

Juri-Stepan Gerasimov, Jul 08 2008

From Petros Hadjicostas, Jun 12 2019: (Start)
This is a mirror image of the triangular array A140994. The current array has index of asymmetry s = 2 and index of obliqueness (obliquity) e = 0. Array A140994 has the same index of asymmetry, but has index of obliqueness e = 1. (In other related sequences, the author uses the letter y for the index of asymmetry and the letter z for the index of obliqueness, but on the stone slab that appears over a tomb in a picture that he posted in those sequences, the letters s and e are used instead. See, for example, the documentation for sequences A140998, A141065, A141066, and A141067.)
In general, if the index of asymmetry (from the Pascal triangle A007318) is s, then the order of the recurrence is s + 2 (because the recurrence of the Pascal triangle has order 2). There are also s + 2 infinite sets of initial conditions (as opposed to the Pascal triangle, which has only 2 infinite sets of initial conditions, namely, G(n, 0) = G(n+1, n+1) = 1 for n >= 0).
Pascal's triangle A007318 has s = 0 and is symmetric, arrays A140998 and A140993 have s = 1 (with e = 0 and e = 1, respectively), and arrays A140996 and A140995 have s = 3 (with e = 0 and e = 1, respectively).
(End)

			Triangle begins:
  1
  1   1
  1   2   1
  1   4   2   1
  1   8   4   2   1
  1  15   9   4   2  1
  1  28  19   9   4  2  1
  1  52  40  19   9  4  2  1
  1  96  83  41  19  9  4  2 1
  1 177 170  88  41 19  9  4 2 1
  1 326 345 188  88 41 19  9 4 2 1
  1 600 694 400 189 88 41 19 9 4 2 1
  ...
E.g., G(14, 2) = G(11, 1) + G(11, 2) + G(12, 2) + G(13, 2) = 600 + 694 + 1386 + 2751 = 5431.

Robert Price, Table of n, a(n) for n = 0..1325
Juri-Stepan Gerasimov, Stepan's triangles and Pascal's triangle are connected by the recurrence relation ...

Cf. A007318, A008937, A140993, A140994, A140995, A140996, A140998, A141015, A141018, A141020, A141021, A141065, A141066, A141067.

nlim = 50;
Do[G[n, 0] = 1, {n, 0, nlim}];
Do[G[n + 1, n + 1] = 1, {n, 0, nlim}];
Do[G[n + 2, n + 1] = 2, {n, 0, nlim}];
Do[G[n + 3, n + 1] = 4, {n, 0, nlim}];
Do[G[n + 4, m] =
   G[n + 1, m - 1] + G[n + 1, m] + G[n + 2, m] + G[n + 3, m], {n, 0,
   nlim}, {m, 1, n + 1}];
A140997 = {}; For[n = 0, n <= nlim, n++,
 For[k = 0, k <= n, k++, AppendTo[A140997, G[n, k]]]];
A140997 (* Robert Price, Aug 25 2019 *)

From Petros Hadjicostas, Jun 12 2019: (Start)
G(n, k) = A140994(n, n-k) for 0 <= k <= n.
Bivariate g.f.: Sum_{n,k >= 0} G(n,k)*x^n*y^k = (1 - x - x^2 - x^3 + x^2*y + x^4*y)/((1 - x) * (1 - x*y) * (1 - x - x^2 - x^3 - x^3*y)).
Differentiating once w.r.t. y and setting y = 0, we get the g.f. of column k = 1: x/((1 - x) * (1 - x - x^2 - x^3)). This is the g.f. of sequence A008937.
(End)

Typo in definition corrected by R. J. Mathar, Sep 19 2008
Name edited by and more terms from Petros Hadjicostas, Jun 12 2019
Deleted extraneous term at a(29) by Robert Price, Aug 25 2019
Added 13 missing terms at a(79) by Robert Price, Aug 25 2019

A172119 Sum the k preceding elements in the same column and add 1 every time.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 4, 4, 2, 1, 1, 5, 7, 4, 2, 1, 1, 6, 12, 8, 4, 2, 1, 1, 7, 20, 15, 8, 4, 2, 1, 1, 8, 33, 28, 16, 8, 4, 2, 1, 1, 9, 54, 52, 31, 16, 8, 4, 2, 1, 1, 10, 88, 96, 60, 32, 16, 8, 4, 2, 1, 1, 11, 143, 177, 116, 63, 32, 16, 8, 4, 2, 1, 1, 12, 232, 326, 224, 124, 64, 32, 16

Offset: 0

Mats Granvik, Jan 26 2010

Columns are related to Fibonacci n-step numbers. Are there closed forms for the sequences in the columns?
We denote by a(n,k) the number which is in the (n+1)-th row and (k+1)-th-column. With help of the definition, we also have the recurrence relation: a(n+k+1, k) = 2*a(n+k, k) - a(n, k). We see on the main diagonal the numbers 1,2,4, 8, ..., which is clear from the formula for the general term d(n)=2^n. - Richard Choulet, Jan 31 2010
Most of the paper by Dunkel (1925) is a study of the columns of this table. - Petros Hadjicostas, Jun 14 2019

			Triangle begins:
n\k|....0....1....2....3....4....5....6....7....8....9...10
---|-------------------------------------------------------
0..|....1
1..|....1....1
2..|....1....2....1
3..|....1....3....2....1
4..|....1....4....4....2....1
5..|....1....5....7....4....2....1
6..|....1....6...12....8....4....2....1
7..|....1....7...20...15....8....4....2....1
8..|....1....8...33...28...16....8....4....2....1
9..|....1....9...54...52...31...16....8....4....2....1
10.|....1...10...88...96...60...32...16....8....4....2....1

Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 3.
Otto Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), # 11.4.2.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Wikipedia, Fibonacci number.

Cf. A000071 (col. 3), A008937 (col. 4), A107066 (col. 5), A001949 (col. 6), A172316 (col. 7), A172317 (col. 8), A172318 (col. 9), A172319 (col. 10), A172320 (col. 11), A144428.

Cf. (1-((-1)^T(n, k)))/2 = A051731, see formula by Hieronymus Fischer in A022003.

T:= function(n,k)
    if k=0 and k=n then return 1;
    elif k<0 or k>n then return 0;
    else return 1 + Sum([1..k], j-> T(n-j,k));
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Jul 27 2019

T:= func< n,k | (&+[(-1)^j*2^(n-k-(k+1)*j)*Binomial(n-k-k*j, n-k-(k+1)*j): j in [0..Floor((n-k)/(k+1))]]) >;
[[T(n,k): k in [0..n]]: n in [0..12]]; // G. C. Greubel, Jul 27 2019

for k from 0 to 20 do for n from 0 to 20 do b(n):=sum((-1)^j*binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j),j=0..floor(n/(k+1))):od: seq(b(n),n=0..20):od; # Richard Choulet, Jan 31 2010
A172119 := proc(n,k)
    option remember;
    if k = 0 then
        1;
    elif k > n then
        0;
    else
        1+add(procname(n-k+i,k),i=0..k-1) ;
    end if;
end proc:
seq(seq(A172119(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Sep 16 2017

T[, 0] = 1; T[n, n_] = 1; T[n_, k_] /; k>n = 0; T[n_, k_] := T[n, k] = Sum[T[n-k+i, k], {i, 0, k-1}] + 1;
Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten
Table[Sum[(-1)^j*2^(n-k-(k+1)*j)*Binomial[n-k-k*j, n-k-(k+1)*j], {j, 0, Floor[(n-k)/(k+1)]}], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 27 2019 *)

T(n,k) = if(k<0 || k>n, 0, k==1 && k==n, 1, 1 + sum(j=1,k, T(n-j,k)));
for(n=1,12, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 27 2019

@CachedFunction
def T(n, k):
    if (k==0 and k==n): return 1
    elif (k<0 or k>n): return 0
    else: return 1 + sum(T(n-j, k) for j in (1..k))
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Jul 27 2019

T(n,0) = 1.
T(n,1) = n.
T(n,2) = A000071(n+1).
T(n,3) = A008937(n-2).
The general term in the n-th row and k-th column is given by: a(n, k) = Sum_{j=0..floor(n/(k+1))} ((-1)^j binomial(n-k*j,n-(k+1)*j)*2^(n-(k+1)*j)). For example: a(5,3) = binomial(5,5)*2^5 - binomial(2,1)*2^1 = 28. The generating function of the (k+1)-th column satisfies: psi(k)(z)=1/(1-2*z+z^(k+1)) (for k=0 we have the known result psi(0)(z)=1/(1-z)). - Richard Choulet, Jan 31 2010 [By saying "(k+1)-th column" the author actually means "k-th column" for k = 0, 1, 2, ... - Petros Hadjicostas, Jul 26 2019]

A001949 Solutions of a fifth-order probability difference equation.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 4, 8, 16, 32, 63, 124, 244, 480, 944, 1856, 3649, 7174, 14104, 27728, 54512, 107168, 210687, 414200, 814296, 1600864, 3147216, 6187264, 12163841, 23913482, 47012668, 92424472, 181701728, 357216192, 702268543, 1380623604, 2714234540

Offset: 0

N. J. A. Sloane

This sequence is the case r = 5 in the solution to an r-th order probability difference equation that can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925). (Equation (3) follows equation (4) in the paper!) For r = 2, we get a shifted version of A000071. For r = 3, we get a shifted version of A008937. For r = 4, we get a shifted version of A107066. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 15 2019

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article #11.4.2.
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
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,0,-1)

Column k = 1 of A141020 (with a different offset) and second main diagonal of A141021 (with no zeros).
Column k = 5 of A172119.
Partial sums of A001591.

A001949:=1/(z-1)/(z**5+z**4+z**3+z**2+z-1); # Simon Plouffe in his 1992 dissertation

t={0,0,0,0,0};Do[AppendTo[t,t[[-5]]+t[[-4]]+t[[-3]]+t[[-2]]+t[[-1]]+1],{n,40}];t (* Vladimir Joseph Stephan Orlovsky, Jan 21 2012 *)
LinearRecurrence[{2,0,0,0,0,-1},{0,0,0,0,0,1},40] (* Harvey P. Dale, Jan 17 2015 *)

a(n):=sum(sum((-1)^j*binomial(n-5*j-5,k-1)*binomial(n-k-5*j-4,j),j,0,(n-k-4)/5),k,1,n-4); /* Vladimir Kruchinin, Oct 19 2011 */

x='x+O('x^99); concat(vector(5), Vec(x^5/((x-1)*(x^5+x^4+x^3+x^2+x-1)))) \\ Altug Alkan, Oct 04 2017

For n >= 6, a(n+1) = 2*a(n) - a(n-5).
G.f.: x^5 / ( (x-1)*(x^5 + x^4 + x^3 + x^2 + x - 1) ).
a(n) = Sum_{k=1..n-4} Sum_{j=0..floor((n-k-4)/5)} (-1)^j*binomial(n-5*j-5, k-1)*binomial(n-k-5*j-4, j). - Vladimir Kruchinin, Oct 19 2011
4*a(n) = A000322(n+1) - 1. - R. J. Mathar, Aug 16 2017
From Petros Hadjicostas, Jun 15 2019: (Start)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) for n >= 5. (See Eq. (4) and the Theorem with r = 5 on p. 356 of Dunkel (1925).)
a(n) = T(n - 5, 5) for n >= 5, where T(n, k) = Sum_{j = 0..floor(n/(k+1))} (-1)^j * binomial(n - k*j, n - (k+1)*j) * 2^(n - (k+1)*j) for 0 <= k <= n. This is Richard Choulet's formula in A172119.
(End)

Name edited by Petros Hadjicostas, Jun 15 2019

A104698 Triangle read by rows: T(n,k) = Sum_{j=0..n-k} binomial(k, j)*binomial(n-j+1, k+1).

Original entry on oeis.org

1, 2, 1, 3, 4, 1, 4, 9, 6, 1, 5, 16, 19, 8, 1, 6, 25, 44, 33, 10, 1, 7, 36, 85, 96, 51, 12, 1, 8, 49, 146, 225, 180, 73, 14, 1, 9, 64, 231, 456, 501, 304, 99, 16, 1, 10, 81, 344, 833, 1182, 985, 476, 129, 18, 1, 11, 100, 489, 1408, 2471, 2668, 1765, 704, 163, 20, 1, 12

Offset: 0

Gary W. Adamson, Mar 19 2005

The n-th column of the triangle is the binomial transform of the n-th row of A081277, followed by zeros. Example: column 3, (1, 6, 19, 44, ...) = binomial transform of row 3 of A081277: (1, 5, 8, 4, 0, 0, 0, ...). A104698 = reversal by rows of A142978. - Gary W. Adamson, Jul 17 2008
This sequence is jointly generated with A210222 as an array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1) + 1 and v(n,x) = 2x*u(n-1,x) + v(n-1,x) + 1. See the Mathematica section at A210222. - Clark Kimberling, Mar 19 2012
This Riordan triangle T appears in a formula for A001100(n, 0) = A002464(n), for n >= 1. - Wolfdieter Lang, May 13 2025

			The Riordan triangle T begins:
  n\k  0   1   2    3    4    5    6   7   8  9 10 ...
  ----------------------------------------------------
  0:   1
  1:   2   1
  2:   3   4   1
  3:   4   9   6    1
  4:   5  16  19    8    1
  5:   6  25  44   33   10    1
  6:   7  36  85   96   51   12    1
  7:   8  49 146  225  180   73   14   1
  8:   9  64 231  456  501  304   99  16   1
  9:  10  81 344  833 1182  985  476 129  18  1
  10: 11 100 489 1408 2471 2668 1765 704 163 20  1
  ... reformatted and extended by _Wolfdieter Lang_, May 13 2025
From _Wolfdieter Lang_, May 13 2025: (Start)
Zumkeller recurrence (adapted for offset [0,0]): 19 = T(4, 2) = T(2, 1) + T(3, 1) + T(3,3) = 4 + 9 + 6 = 19.
A-sequence recurrence: 19 = T(4, 2) = 1*T(3. 1) + 2*T(3. 2) - 2*T(3, 3) = 9 + 12 - 2 = 19.
Z-sequence recurrence: 5 = T(4, 0) = 2*T(3, 0) - 1*T(3, 1) + 2*T(3, 2) - 6*T(3, 3) = 8 - 9 + 12 + 6 = 5.
Boas-Buck recurrence: 19 = T(4, 2) = (1/2)*((2 + 0)*T(2, 2) + (2 + 2*2)*T(3, 2)) = (1/2)*(2 + 36) = 19. (End)

Reinhard Zumkeller, First 100 rows of triangle, flattened

Diagonal sums are A008937(n+1).
Cf. A048739 (row sums), A008288, A005900 (column 3), A014820 (column 4)
Cf. A081277, A142978 by antidiagonals, A119328, A110271 (matrix inverse).
Cf. A001100, A002464, A010673, A040000, A112478, A133872, A383857.

a104698 n k = a104698_tabl !! (n-1) !! (k-1)
a104698_row n = a104698_tabl !! (n-1)
a104698_tabl = [1] : [2,1] : f [1] [2,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) ([0] ++ us ++ [0]) $
          zipWith (+) ([1] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Jul 17 2015

A104698 := proc(n, k) add(binomial(k, j)*binomial(n-j+1, n-k-j), j=0..n-k) ; end proc:
seq(seq(A104698(n, k), k=0..n), n=0..15); # R. J. Mathar, Sep 04 2011
T := (n, k) -> binomial(n + 1, k + 1)*hypergeom([-k, k - n], [-n - 1], -1):
for n from 0 to 9 do seq(simplify(T(n, k)), k = 0..n) od;
T := proc(n, k) option remember; if k = 0 then n + 1 elif k = n then 1 else T(n-2, k-1) + T(n-1, k-1) + T(n-1, k) fi end: # Peter Luschny, May 13 2025

u[1, ] = 1; v[1, ] = 1;
u[n_, x_] := u[n, x] = x u[n-1, x] + v[n-1, x] + 1;
v[n_, x_] := v[n, x] = 2 x u[n-1, x] + v[n-1, x] + 1;
Table[CoefficientList[u[n, x], x], {n, 1, 11}] // Flatten (* Jean-François Alcover, Mar 10 2019, after Clark Kimberling *)

T(n,k)=sum(j=0,n-k,binomial(k,j)*binomial(n-j+1,k+1)) \\ Charles R Greathouse IV, Jan 16 2012

The triangle is extracted from the product A * B; A = [1; 1, 1; 1, 1, 1; ...], B = [1; 1, 1; 1, 3, 1; 1, 5, 5, 1; ...] both infinite lower triangular matrices (rest of the terms are zeros). The triangle of matrix B by rows = A008288, Delannoy numbers.
From Paul Barry, Jul 18 2005: (Start)
Riordan array (1/(1-x)^2, x(1+x)/(1-x)) = (1/(1-x), x)*(1/(1-x), x(1+x)/(1-x)).
T(n, k) = Sum_{j=0..n} Sum_{i=0..j-k} C(j-k, i)*C(k, i)*2^i.
T(n, k) = Sum_{j=0..k} Sum_{i=0..n-k-j} (n-k-j-i+1)*C(k, j)*C(k+i-1, i). (End)
T(n, k) = binomial(n+1, k+1)*2F1([-k, k-n], [-n-1], -1) where 2F1 is a Gaussian hypergeometric function. - R. J. Mathar, Sep 04 2011
T(n, k) = T(n-2, k-1) + T(n-1, k-1) + T(n-1, k) for 1 < k < n; T(n, 0) = n + 1; T(n, n) = 1. - Reinhard Zumkeller, Jul 17 2015
From Wolfdieter Lang, May 13 2025: (Start)
The Riordan triangle T = (1/(1 - x)^2, x*(1 + x)/(1 - x)) has the o.g.f. G(x, y) = 1/((1 - x)*(1 - x - y*x*(1+x))) for the row polynomials R(n, y) = Sum_{k=0..n} T(n, k)*y^k.
The o.g.f. for column k is G(k, x) = (1/(1 - x)^2)*(x*(1 + x)/(1 - x))^k, for k >= 0.
The o.g.f. for the diagonal m is D(m, x) = N(m, x)/(1 - x)^(m+1), with the numerator polynomial N(m, x) = Sum_{k=0..floor(m/2)} A034867(m, k)*x^(2*k) for m >= 0.
The row sums with o.g.f. R(x) = 1/((1 -x)*(1 - 2*x -x^2) give A048739.
The alternating row sums with o.g.f. 1/((1 - x)(1 + x^2)) give A133872.
The A-sequence for this Riordan triangle has o.g.f. A(x) = 1 + x + sqrt(1 + 6*x + x^2))/2 giving A112478(n). Hence T(n, k) = Sum_{j=0..n-k} A112478(j)*T(n-1, k-1+j), for n >= 1, k >= 1, T(n, k) = 0 for n < k, and T(0, 0) = 1.
The Z-sequence has o.g.f. (5 + x - sqrt(1 + 6*x + x^2))/2 = 3 + x - A(x) giving Z(n) = {2, -1, -A112478(n >= 2)}. Hence T(n, 0) = Sum_{j=0..n-1} Z(j)*T(n-1, j), for n >= 1. For A- and Z-sequences of Riordan triangles see a W. Lang link at A006232 with references.
The Boas-Buck sequences alpha and beta for the Riordan triangle T (see A046521 for the Aug 10 2017 comment and reference) are alpha(n) = A040000(n+1) = repeat{2} and beta(n) = A010673(n+1) = repeat{2,0}. Hence the recurrence for column T(n, k){n>=k}, with input T(k, k) = 1, for k >= 0, is T(n, k) = (1/(n-k)) * Sum{j=k..n-1} (2 + k*(1 + (-1)^(n-1-j))) *T(j,k), for n >= k+1. (End)

cp's OEIS Frontend

A073769 Duplicate of A008937.

Views

Author

Keywords

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Python

Sage

Formula

A140994 Triangle G(n, k), for 0 <= k <= n, read by rows, where G(n, n) = G(n+1, 0) = 1, G(n+2, 1) = 2, G(n+3, 2) = 4, G(n+4, m) = G(n+1, m-2) + G(n+1, m-3) + G(n+2, m-2) + G(n+3, m-1) for n >= 0 and m = 3..(n+3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A140997 Triangle G(n,k) read by rows, for 0 <= k <= n, where G(n, 0) = G(n+1, n+1) = 1, G(n+2, n+1) = 2, G(n+3, n+1) = 4, and G(n+4, m) = G(n+1, m-1) + G(n+1, m) + G(n+2, m) + G(n+3, m) for n >= 0 and m = 1..n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A172119 Sum the k preceding elements in the same column and add 1 every time.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs