A005253 Number of binary words of length n in which the ones occur only in blocks of length at least 4. (Formerly M1044)

1, 1, 1, 1, 2, 4, 7, 11, 16, 23, 34, 52, 81, 126, 194, 296, 450, 685, 1046, 1601, 2452, 3753, 5739, 8771, 13404, 20489, 31327, 47904, 73252, 112004, 171245, 261813, 400285, 612009, 935737, 1430710, 2187496, 3344567, 5113647, 7818464, 11953991, 18277014, 27944604

Offset

0,5

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Andrew Howroyd, 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.

Russ Chamberlain, Sam Ginsburg and Chi Zhang, Generating Functions and Wilf-equivalence on Theta_k-embeddings, University of Wisconsin, April 2012.

Richard K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]

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

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

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 425

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

Formula

G.f.: (1-x+x^4)/(1-2*x+x^2-x^5). - Simon Plouffe in his 1992 dissertation.

a(n-1) = Sum_{k=0..floor(n/5)} binomial(n-3*k, 2*k). - Paul Barry, Sep 16 2004

Example

a(6)=7 because 7 binary words of length 6 in which the ones occur only in blocks of length at least 4: 000000, 001111, 011110, 011111, 111100, 111110, 111111. - Jinyuan Wang, Jan 20 2025

Mathematica

LinearRecurrence[{2, -1, 0, 0, 1}, {1, 1, 1, 1, 2}, 50] (* Harvey P. Dale, Mar 14 2018 *)

Prog

(PARI) a(n) = sum(k=0, (n+1)\5, binomial(n+1-3*k, 2*k)) \\ Andrew Howroyd, Sep 19 2025
(Python)
from sympy import Matrix
def A005253(n):
    A = Matrix([[2, -1, 0, 0, 1], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]])
    return (A**(n-4)*Matrix([2, 1, 1, 1, 1]))[0] # Chai Wah Wu, Jun 11 2026

Crossrefs

Column 4 of A388146.

Sequence in context: A062433 A317910 A065095 * A212364 A320591 A129339

Adjacent sequences: A005250 A005251 A005252 * A005254 A005255 A005256

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from Harvey P. Dale, Mar 14 2018

Name clarified by Jinyuan Wang, Jan 20 2025

Status

approved