A007800 From a problem in AI planning: a(n) = 4+a(n-1)+a(n-2)+a(n-3)+a(n-4)-a(n-5)-a(n-6)-a(n-7), n>7.

1, 2, 4, 8, 16, 31, 59, 111, 207, 384, 710, 1310, 2414, 4445, 8181, 15053, 27693, 50942, 93704, 172356, 317020, 583099, 1072495, 1972635, 3628251, 6673404, 12274314, 22575994, 41523738, 76374073, 140473833, 258371673, 475219609, 874065146

Offset: 1

Author

Peter Jonsson [ petej(AT)ida.liu.se ]

Keywords

• nonn
• easy

Comments

The number of length n binary words with fewer than 3 zeros between any pair of consecutive ones. - Jeffrey Liese, Dec 23 2010

Links

• Robert Israel, Table of n, a(n) for n = 1..3397
• 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 (3,-2,0,-1,1).

Crossrefs

Cf. A062544.

Programs

Maple

for n from 1 to 5 do a[n]:= [1,2,4,8,16][n] od:
for n from 6 to 100 do a[n]:= 3*a[n-1]-2*a[n-2]-a[n-4]+a[n-5] od:
seq(a[n],n=1..100); # Robert Israel, Aug 19 2014

Mathematica

LinearRecurrence[{3,-2,0,-1,1},{1,2,4,8,16},40] (* Harvey P. Dale, Apr 24 2013 *)

PARI

Vec(-x*(x^4-x+1)/((x-1)^2*(x^3+x^2+x-1)) + O(x^100)) \\ Colin Barker, Aug 18 2014

Formula

a(1)=1, a(2)=2, a(3)=4, a(4)=8, a(5)=16, a(n)=3*a(n-1)-2*a(n-2)+0*a(n-3)- a(n-4)+ a(n-5). - Harvey P. Dale, Apr 24 2013

G.f.: -x*(x^4-x+1) / ((x-1)^2*(x^3+x^2+x-1)). - Colin Barker, Aug 18 2014

2*a(n) = A001590(n+4)-n. - R. J. Mathar, Aug 16 2017