A049858 -id:A049858 - cp's OEIS frontend

A049864 a(n) = Sum_{k=0,1,2,...,n-4,n-2,n-1} a(k); a(n-3) is not a summand, with a(0)=a(1)=a(2)=1.

1, 1, 1, 2, 4, 8, 15, 28, 52, 97, 181, 338, 631, 1178, 2199, 4105, 7663, 14305, 26704, 49850, 93058, 173717, 324288, 605368, 1130077, 2109583, 3938086, 7351463, 13723420, 25618337, 47823297, 89274637, 166654357, 311103754, 580756168, 1084132616, 2023815835

Offset: 0

Clark Kimberling

Number of binary sequences of length n-2 with no subsequence 0110. E.g., a(7)=28 because among the 32 (=2^5) binary sequences of length 5 only 01100,01101,00110 and 10110 contain the subsequence 0110. - Emeric Deutsch, May 04 2006
This is a_3(n) in the Doroslovacki reference. - Max Alekseyev, Jun 26 2007
Column 0 of A118890. - Emeric Deutsch, May 04 2006

R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).

Cf. A005251, A049858, A118890, A118891, A118892.

(With a different offset:) a[0]:=1:a[1]:=2:a[2]:=4:a[3]:=8: for n from 4 to 35 do a[n]:=2*a[n-1]-a[n-3]+a[n-4] od: seq(a[n],n=0..35); # Emeric Deutsch, May 04 2006

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

a(n) = 2*a(n-1) - a(n-3) + a(n-4).

G.f.: (1+z)*(1-z)^2/(1 - 2z + z^3 - z^4). - Emeric Deutsch, May 04 2006

Edited by N. J. A. Sloane, Nov 16 2007, at the suggestion of Max Alekseyev

A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

Original entry on oeis.org

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

Clark Kimberling

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
For n>=4, a(n) is the number of binary strings of length n-3 without any maximal runs of ones of length 2. - Félix Balado, Aug 25 2025

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

Cf. A049858.

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

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

a(n) = 2*a(n-1) - a(n-3) + a(n-4) for n >= 4.
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

A290986 Expansion of x^6/((1 - x)^2(1 - 2x + x^3 - x^4)).

Original entry on oeis.org

1, 4, 11, 25, 52, 103, 199, 379, 716, 1346, 2523, 4721, 8825, 16487, 30791, 57494, 107343, 200400, 374116, 698403, 1303770, 2433846, 4543428, 8481513, 15832975, 29556394, 55174730, 102998026, 192272662, 358927018, 670030771

Offset: 6

R. J. Mathar, Aug 16 2017

Robert Israel, Table of n, a(n) for n = 6..3688
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
Index entries for linear recurrences with constant coefficients, signature (4,-5,1,3,-3,1).

Cf. A049858, A290987, A290989.

I:=[1,4,11,25,52,103]; [n le 6 select I[n] else 4*Self(n-1)-5*Self(n-2)+Self(n-3)+3*Self(n-4)-3*Self(n-5)+Self(n-6): n in [1..40]]; // Vincenzo Librandi, Aug 17 2017

f:= gfun:-rectoproc({a(n)-a(n+1)+2*a(n+3)-a(n+4)+n-1, a(0) = 0, a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 0, a(6) = 1}, a(n), remember):
map(f, [$6..100]); # Robert Israel, Aug 17 2017

 LinearRecurrence[{4,-5,1,3,-3,1}, {1,4,11,25,52,103}, 40] (* Vincenzo Librandi, Aug 17 2017 *)

Vec(x^6/((1-x)^2*(1-2*x+x^3-x^4)) + O(x^50)) \\ Michel Marcus, Aug 17 2017

def A290986_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x^6/((1-x)^2*(1-2*x+x^3-x^4)) ).list()
a=A290986_list(50); a[6:] # G. C. Greubel, Apr 12 2023

a(n) = A049858(n-2) - (n-2).

cp's OEIS Frontend

A049864 a(n) = Sum_{k=0,1,2,...,n-4,n-2,n-1} a(k); a(n-3) is not a summand, with a(0)=a(1)=a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290986 Expansion of x^6/((1 - x)^2(1 - 2x + x^3 - x^4)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

cp's OEIS Frontend

A049864 a(n) = Sum_{k=0,1,2,...,n-4,n-2,n-1} a(k); a(n-3) is not a summand, with a(0)=a(1)=a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A049856 a(n) = (Sum{k=0..n-1} a(k)) - a(n-3), with a(0)=0, a(1)=0, a(2)=1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290986 Expansion of x^6/((1 - x)^2*(1 - 2*x + x^3 - x^4)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A290986 Expansion of x^6/((1 - x)^2(1 - 2x + x^3 - x^4)).