A177795 Number of length n binary words that have at least one maximal run of 1's having length two.

0, 1, 2, 5, 11, 25, 55, 120, 258, 550, 1163, 2444, 5108, 10627, 22021, 45474, 93621, 192232, 393779, 804947, 1642355, 3345307, 6803734, 13818636, 28031472, 56798821, 114971348, 232507076, 469801235, 948538807, 1913759614, 3858660525, 7775454390, 15659429797

Offset

1,3

Comments

For bit strings of length 1,2,3,.. the sequence gives the number of strings of that length that contain at least one '11' not flanked by 1's; i.e., an occurrence of '0110' is OK; an occurrence of '0111' does not count. Thus the strings '0110011' and '0110111' are counted but '0111000' is not because '11' does not occur by itself.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..3321

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

Formula

a(n) = 2*a(n-1) + 2^n-3 - a(n-3) - 2^n-4 + a(n-4).

a(n) = 2^n - A049856(n+3) = Sum_{k>=1} A218196(n+1,k).

G.f.: (1 - x)^2*x^2/((1-2*x)*(1 - 2*x + x^3 -x^4)). - Geoffrey Critzer, Jan 23 2014

Example

a(5) = 11 because we have: 00011, 00110, 01011, 01100, 01101, 10011, 10110, 11000, 11001, 11010, 11011. - Geoffrey Critzer, Jan 23 2014

Mathematica

nn=30; r=Solve[{s==1+x s+x c+x a, a==x s, b==x a, c==x b+x c, d==x b+2x d}, {s, a, b, c, d}]; Drop[Flatten[CoefficientList[Series[b+d/.r, {x, 0, nn}], x]], 1] (* Geoffrey Critzer, Jan 23 2014 *)

Crossrefs

Sequence in context: A291552 A208739 A291737 * A092685 A172481 A151529

Adjacent sequences: A177792 A177793 A177794 * A177796 A177797 A177798

Keyword

easy,nonn

Author

Oskars Rieksts (rieksts(AT)kutztown.edu), May 13 2010

Extensions

Better name and more terms from Geoffrey Critzer, Jan 23 2014

Status

approved