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

Comments

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

References

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

Links

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.

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.

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

Formula

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

Example

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]

Maple

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

Mathematica

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

Prog

(Magma) [ 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
(Haskell)
a008937 n = a008937_list !! n
a008937_list = tail $ scanl1 (+) a000073_list
-- Reinhard Zumkeller, Apr 07 2012
(PARI) {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 */
(PARI) 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
(Sage)
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
(GAP) 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

Crossrefs

Cf. A000073, A000213, A018921, A027084, A077908, A209972.

Row sums of A055216.

Column k = 1 of A140997 and second main diagonal of A140994.

Sequence in context: A008936 A320452 A073769 * A128805 A141018 A049864

Adjacent sequences: A008934 A008935 A008936 * A008938 A008939 A008940

Keyword

nonn,easy

Author

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

Status

approved