A005253 Number of binary words of length n in which the ones occur only in blocks of length at least 4.
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
Examples
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
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- 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).
Programs
-
Mathematica
LinearRecurrence[{2,-1,0,0,1},{1,1,1,1,2},50] (* Harvey P. Dale, Mar 14 2018 *)
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
Extensions
More terms from Harvey P. Dale, Mar 14 2018
Name clarified by Jinyuan Wang, Jan 20 2025