A055216 -id:A055216 - cp's OEIS frontend

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, 117897840, 216847936, 398845537, 733591314, 1349284788

Offset: 0

N. J. A. Sloane, Alejandro Teruel (teruel(AT)usb.ve)

a(n+1) is the number of n-bit sequences that avoid 1100. - David Callan, Jul 19 2004 [corrected by Kent E. Morrison, Jan 08 2019]. Also the number of n-bit sequences avoiding one of the patterns 1000, 0011, 1110, ... or any binary string of length 4 without overlap at beginning and end. Strings where it is not true are: 1111, 1010, 1001, ... and their bitwise complements. - Alois P. Heinz, Jan 09 2019
Row sums of Riordan array (1/(1-x), x(1+x+x^2)). - Paul Barry, Feb 16 2005
Diagonal sums of Riordan array (1/(1-x)^2, x(1+x)/(1-x)), A104698.
A shifted version of this sequence can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925) with r = 3. (Equation (3) follows equation (4) in the paper!) The whole paper is a study of the properties of this and other similar sequences indexed by the parameter r. For r = 2, we get a shifted version of A000071. For r = 4, we get a shifted version of A107066. For r = 5, we get a shifted version of A001949. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 14 2019
Officially, to match A000073, this should start with a(0)=a(1)=0, a(2)=1. - N. J. A. Sloane, Sep 12 2020
Numbers with tribonacci representation that is a prefix of 100100100100... . - Jeffrey Shallit, Jul 10 2024

			G.f. = x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 28*x^6 + 52*x^7 + 96*x^8 + 177*x^9 + ... [edited by _Petros Hadjicostas_, Jun 12 2019]

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 41.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 6, 9.
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 pp. 356 and 369.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 7.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article # 11.4.2.
William Verreault, MacMahon Partition Analysis: a discrete approach to broken stick problems, arXiv:2107.10318 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Partial sums of A000073. Cf. A000213, A018921, A027084, A077908, A209972.
Row sums of A055216.
Column k = 1 of A140997 and second main diagonal of A140994.

a:=[0,1,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Sep 13 2019

a008937 n = a008937_list !! n
a008937_list = tail $ scanl1 (+) a000073_list
-- Reinhard Zumkeller, Apr 07 2012

[ n eq 1 select 0 else n eq 2 select 1 else n eq 3 select 2 else n eq 4 select 4 else 2*Self(n-1)-Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 21 2011

A008937 := proc(n) option remember; if n <= 3 then 2^n else 2*procname(n-1)-procname(n-4) fi; end;
a:= n-> (Matrix([[1,1,0,0], [1,0,1,0], [1,0,0,0], [1,0,0,1]])^n)[4,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 24 2008

CoefficientList[Series[x/(1-2x+x^4), {x, 0, 40}], x]
Accumulate[LinearRecurrence[{1,1,1},{0,1,1},40]] (* Harvey P. Dale, Dec 04 2017 *)
LinearRecurrence[{2, 0, 0, -1},{0, 1, 2, 4},40] (* Ray Chandler, Mar 01 2024 *)

{a(n) = if( n<0, polcoeff( - x^3 / (1 - 2*x^3 + x^4) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^4) + x * O(x^n), n))}; /* Michael Somos, Aug 23 2014 */

a(n) = sum(j=0, n\2, sum(k=0, j, binomial(n-2*j,k+1)*binomial(j,k)*2^k)); \\ Michel Marcus, Sep 08 2017

def A008937_list(prec):
    P = PowerSeriesRing(ZZ, 'x', prec)
    x = P.gen().O(prec)
    return (x/(1-2*x+x^4)).list()
A008937_list(40) # G. C. Greubel, Sep 13 2019

a(n) = A018921(n-2) = A027084(n+1) + 1.
a(n) = (A000073(n+2) + A000073(n+4) - 1)/2.
From Mario Catalani (mario.catalani(AT)unito.it), Aug 09 2002: (Start)
G.f.: x/((1-x)*(1-x-x^2-x^3)).
a(n) = 2*a(n-1) - a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4. (End)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3). E.g., a(11) = 1 + 600 + 326 + 177 = 1104. - Philippe LALLOUET (philip.lallouet(AT)orange.fr), Oct 29 2007
a(n) = term (4,1) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,0; 1,0,0,1]^n. - Alois P. Heinz, Jul 24 2008
a(n) = -A077908(-n-3). - Alois P. Heinz, Jul 24 2008
a(n) = (A000213(n+2) - 1) / 2. - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k+1) *binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
a(n) = Sum_{k=0..floor(n/2)} (n-2*k)*hypergeom([-k,-n+2*k+1], [2], 2). - Peter Luschny, Nov 09 2017
a(n) = 2^(n-1)*hypergeom([1-n/4, 1/4-n/4, 3/4-n/4, 1/2-n/4], [1-n/3, 1/3-n/3, 2/3-n/3], 16/27) for n > 0. - Peter Luschny, Aug 20 2020
a(n-1) = T(n) + T(n-3) + T(n-6) + ... + T(2+((n-2) mod 3)), for n >= 4, where T is A000073(n+1). - Jeffrey Shallit, Dec 24 2020

A055217 a(n) = sum of the first n coefficients of (1+x+x^2)^n.

Original entry on oeis.org

1, 3, 10, 31, 96, 294, 897, 2727, 8272, 25048, 75747, 228826, 690691, 2083371, 6280650, 18925047, 57002616, 171633840, 516632307, 1554702516, 4677501237, 14069962041, 42314975352, 127240600050, 382555886571, 1150026301089

Offset: 0

Clark Kimberling, May 07 2000

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, The Combinatorics of Motzkin Polyominoes, arXiv:2401.06228 [math.CO], 2024.
Taras Goy and Mark Shattuck, Determinant identities for the Catalan, Motzkin and Schröder numbers, Art Disc. Appl. Math., Vol. 7, No. 1 (2024).

T(2n+1, n), array T as in A055216.
Cf. A000244, A002426, A027914.
Cf. A001006, A117186.

a055217 n = sum $ take (n + 1) $ a027907_row (n + 1)
-- Reinhard Zumkeller, Jan 22 2013

a := n -> simplify((3^(n+1) - GegenbauerC(n+1,-n-1,-1/2))/2):
seq(a(n), n=0..25); # Peter Luschny, May 12 2016

Total/@Table[Take[CoefficientList[Expand[(1+x+x^2)^n],x],n],{n,30}] (* Harvey P. Dale, Aug 14 2011 *)

a(n):=sum(sum(binomial(n,j)*binomial(j,2*j-n-k),j,ceiling((n+k)/2),n),k,1,n); /* Vladimir Kruchinin, Aug 11 2010 */

a(n) = my(v=Vec((1+'x+'x^2)^n)); sum(k=1, n, v[k]);

From Paul Barry, Jan 20 2008: (Start)
Binomial transform of A117186.
G.f.: (1+x-sqrt(1-2x-3x^2))/(2x*(1-2x-3x^2)).
a(n) = (3^(n+1) + A002426(n+1))/2. (End)
From Vladimir Kruchinin, Aug 11 2010: (Start)
Logarithm g.f.: log(1/(1-x*M(x))) = Sum_{n>0} a(n-1)/n*x^n, M(x) - o.g.f Motzkin numbers (A001006).
a(n) = sum(sum(binomial(n,j)*binomial(j,2*j-n-k),j,ceiling((n+k)/2),n),k,1,n), n>0. (End)
Conjecture: (n+1)*a(n) -(5*n+1)*a(n-1) +3*(n-1)*a(n-2) +9*(n-1)*a(n-3)=0. - R. J. Mathar, Nov 14 2011
a(n) = 3^n * 3/2 + O(3^n/sqrt(n)). - Charles R Greathouse IV, Dec 02 2015
From Peter Luschny, May 12 2016: (Start)
a(n) = (3^(n+1) - hypergeom([-(n+1)/2, -n/2], [1], 4))/2.
a(n) = (3^(n+1) - GegenbauerC(n+1,-n-1,-1/2))/2. (End)

New description from Paul D. Hanna, Oct 09 2003

cp's OEIS Frontend

A055218 a(n) = T(2*n+2,n), array T as in A055216.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055219 T(2n+3,n), array T as in A055216.

Views

Author

Keywords

Formula

A055220 T(2n+4,n), array T as in A055216.

Views

Author

Keywords

A055221 T(2n+5,n), array T as in A055216.

Views

Author

Keywords

A055222 T(2n+6,n), array T as in A055216.

Views

Author

Keywords

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A055217 a(n) = sum of the first n coefficients of (1+x+x^2)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

PARI

Formula

Extensions