A005253 Number of binary words not containing ..01110... (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

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

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, 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

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

Author

N. J. A. Sloane.

Extensions

More terms from Harvey P. Dale, Mar 14 2018

Status

approved