A005253 - OEIS

%I M1044 #79 Jun 11 2026 01:00:22

%S 1,1,1,1,2,4,7,11,16,23,34,52,81,126,194,296,450,685,1046,1601,2452,

%T 3753,5739,8771,13404,20489,31327,47904,73252,112004,171245,261813,

%U 400285,612009,935737,1430710,2187496,3344567,5113647,7818464,11953991,18277014,27944604

%N Number of binary words of length n in which the ones occur only in blocks of length at least 4.

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

%H Andrew Howroyd, <a href="/A005253/b005253.txt">Table of n, a(n) for n = 0..1000</a>

%H Richard Austin and Richard K. Guy, <a href="https://www.fq.math.ca/Scanned/16-1/austin.pdf">Binary sequences without isolated ones</a>, Fib. Quart., 16 (1978), 84-86.

%H Félix Balado and Guénolé C. M. Silvestre, <a href="https://arxiv.org/abs/2602.10005">Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings</a>, arXiv:2602.10005 [math.CO], 2026. See p. 24.

%H Russ Chamberlain, Sam Ginsburg and Chi Zhang, <a href="http://digital.library.wisc.edu/1793/61870">Generating Functions and Wilf-equivalence on Theta_k-embeddings</a>, University of Wisconsin, April 2012.

%H Richard K. Guy, <a href="/A005251/a005251_1.pdf">Anyone for Twopins?</a>, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]

%H V. C. Harris and Carolyn C. Styles, <a href="https://www.fq.math.ca/Scanned/2-4/harris.pdf">A generalization of Fibonacci numbers</a>, Fib. Quart. 2 (1964) 277-289, sequence u(n,3,2).

%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=425">Encyclopedia of Combinatorial Structures 425</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,0,1).

%F G.f.: (1-x+x^4)/(1-2*x+x^2-x^5). - _Simon Plouffe_ in his 1992 dissertation.

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

%e 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

%t LinearRecurrence[{2,-1,0,0,1},{1,1,1,1,2},50] (* _Harvey P. Dale_, Mar 14 2018 *)

%o (PARI) a(n) = sum(k=0, (n+1)\5, binomial(n+1-3*k, 2*k)) \\ _Andrew Howroyd_, Sep 19 2025

%o (Python)

%o from sympy import Matrix

%o def A005253(n):

%o     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]])

%o     return (A**(n-4)*Matrix([2,1,1,1,1]))[0] # _Chai Wah Wu_, Jun 11 2026

%Y Column 4 of A388146.

%K nonn,easy

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _Harvey P. Dale_, Mar 14 2018

%E Name clarified by _Jinyuan Wang_, Jan 20 2025