A049856 a(n) = Sum{a(k): k=0,1,2,...,n-4,n-2,n-1}; a(n-3) is not a summand; 3 initial terms required.

0, 0, 1, 1, 2, 3, 6, 11, 21, 39, 73, 136, 254, 474, 885, 1652, 3084, 5757, 10747, 20062, 37451, 69912, 130509, 243629, 454797, 848997, 1584874, 2958580, 5522960, 10310043, 19246380, 35928380, 67069677, 125203017, 233724034, 436306771, 814480202, 1520439387

Offset

0,5

Comments

a(n+3) is also the number of binary words w of length n with the condition that every subword 11 of w is part of a longer subword of w containing only 1-digits. The a(3+3)=6 binary words of length 3 are 000, 001, 010, 100, 101, 111. - Alois P. Heinz, Mar 25 2009

a(n+2) is the number of compositions of n avoiding the part 3. [Joerg Arndt, Jul 13 2014]

Starting with 1 = INVERT transform of (1,1,0,1,1,1,...). Example: a(9) = 39 = (1,1,2,3,6,11,21) dot (1,1,1,1,0,1,1) = (1+1+2+3+0+11+21). - Gary W. Adamson, Apr 27 2009

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, example 11.

Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3

J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=3, k=0.

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).

Formula

a(n) = 2*a(n-1) -a(n-3) +a(n-4); 4 initial terms required.

a(n+2) = Sum_{i=0..n} F(i+1)*C(n-i,i)) where F=A000045. - Benoit Cloitre, Sep 21 2004

G.f.: x^2*(1-x)/(1-2*x+x^3-x^4). - Vladimir Kruchinin, May 11 2011

a(n) = A218796(n-2,0) for n>1. - Alois P. Heinz, Nov 06 2012

a(n) = A059633(n+1) - A059633(n). - R. J. Mathar, Aug 04 2019

Maple

a:= n-> -(Matrix(4, (i, j)-> if i=j-1 then 1 elif j=1 then [2, 0, -1, 1][i] else 0 fi)^n)[3, 2]: seq (a(n), n=0..40); # Alois P. Heinz, Mar 25 2009

Mathematica

LinearRecurrence[{2, 0, -1, 1}, {0, 0, 1, 1}, 40] (* Harvey P. Dale, Jul 23 2013 *)

Crossrefs

Cf. A049858.

Sequence in context: A034074 A018175 A316356 * A302017 A113409 A092684

Adjacent sequences: A049853 A049854 A049855 * A049857 A049858 A049859

Keyword

nonn,easy

Author

Clark Kimberling

Status

approved