A098574 a(n) = Sum_{k=0..floor(n/7)} C(n-5*k,2*k).

1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 38, 51, 71, 102, 149, 218, 316, 452, 639, 897, 1257, 1766, 2493, 3536, 5031, 7165, 10196, 14484, 20538, 29085, 41168, 58282, 82561, 117036, 165995, 235492, 334074, 473824, 671856, 952449, 1350078, 1913702

Offset

0,8

Comments

For n>=1, a(n) is the number of binary strings of length n-1 which are devoid of runs of ones of length <=5. For example, there are a(8)=4 binary strings of length 7 devoid of runs of length <=5: 0000000, 0111111, 1111110, and 1111111. - Félix Balado, Sep 09 2025

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Richard Austin and Richard K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 24.

V. C. Harris and Carolyn C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,5,2).

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

Formula

G.f.: (1-x)/(1-2*x+x^2-x^7).

Mathematica

CoefficientList[Series[(1-x)/(1-2*x+x^2-x^7), {x, 0, 50}], x] (* G. C. Greubel, Feb 03 2018 *)

Prog

(PARI) a(n) = sum(k=0, n\7, binomial(n-5*k, 2*k)); \\ Michel Marcus, Sep 06 2017
(PARI) my(x='x+O('x^50)); Vec((1-x)/(1-2*x+x^2-x^7)) \\ G. C. Greubel, Feb 03 2018
(Magma) Q:=Rationals(); R<x>:=PowerSeriesRing(Q, 40); Coefficients(R!((1-x)/(1-2*x+x^2-x^7))); // G. C. Greubel, Feb 03 2018

Crossrefs

Cf. A005251, A005252, A005253, A005689.

Sequence in context: A212367 A225088 A175777 * A212366 A309838 A334251

Adjacent sequences: A098571 A098572 A098573 * A098575 A098576 A098577

Keyword

easy,nonn

Author

Paul Barry, Sep 16 2004

Status

approved