A235996 Number of length n binary words that contain at least one pair of consecutive 0's followed by (at some point in the word) at least one pair of consecutive 1's.

0, 0, 0, 0, 1, 4, 13, 36, 92, 222, 515, 1160, 2555, 5530, 11804, 24916, 52117, 108204, 223273, 458368, 937020, 1908730, 3876615, 7853840, 15878391, 32045814, 64580028, 129983856, 261354937, 525042292, 1054000645, 2114567580, 4240131740, 8498658390, 17028054539

Offset

0,6

Links

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

Index entries for linear recurrences with constant coefficients, signature (4,-3,-4,3,2).

Formula

G.f.: x^4/((1 - 2*x)*(1 - x - x^2)^2).

a(n) -2*a(n-1) = A001629(n-2). - R. J. Mathar, May 06 2016

Example

a(5) = 4 because we have: 00011, 00110, 00111, 10011.
We also note that words such as 001011 are included in this enumeration because the pair of consecutive 1's need not immediately follow the pair of consecutive 0's.

Mathematica

nn=30; r=Solve[{s==1+x a+x s, a==x s, b==x a+x b+x c, c==x b, d==x c + 2x d}, {s, a, b, c, d}]; CoefficientList[Series[d/.r, {x, 0, nn}], x]
CoefficientList[ Series[ x^4/((1 - 2x)(1 - x - x^2)^2), {x, 0, 34}], x] (* Robert G. Wilson v, Feb 01 2015 *)
LinearRecurrence[{4, -3, -4, 3, 2}, {0, 0, 0, 0, 1}, 40] (* Harvey P. Dale, Jun 23 2017 *)

Crossrefs

Sequence in context: A079922 A053563 A221882 * A036636 A036643 A000299

Adjacent sequences: A235993 A235994 A235995 * A235997 A235998 A235999

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 18 2014

Status

approved