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

Table of n, a(n) for n=0..42.

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

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

R. 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 C. 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-2x+x^2-x^5). - Simon Plouffe in his 1992 dissertation.

a(n-1) = Sum_{k=0..floor(n/5)} binomial(n-3k, 2k). - 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 *)

Crossrefs

Sequence in context: A062433 A317910 A065095 * A212364 A320591 A129339

Adjacent sequences: A005250 A005251 A005252 * A005254 A005255 A005256

Keyword

nonn,easy,changed

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