A066067 Number of binary strings u of any length with property that length(u) + number of 0's in u <= n (only one of a string and its reversal are counted).

1, 2, 3, 6, 10, 18, 29, 49, 78, 128, 203, 329, 523, 844, 1347, 2172, 3480, 5614, 9023, 14567, 23466, 37910, 61165, 98865, 159677, 258190, 417283, 674890, 1091214, 1765146, 2854793, 4618373, 7470614, 12086436, 19552903, 31635193, 51181367, 82809832

Offset

1,2

Comments

If 0 is replaced by 2 (as in A007931) "length + 0-bits" is simply the total of ternary digits (e.g., 3 for 21 instead of 01).

Links

Table of n, a(n) for n=1..38.

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

Formula

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

Example

a(3) = 3: 0 01 111 (e.g. 01: length 2 + 1 zero = 3).
a(4) = 6: 0 01 00 011 101 1111.
a(5) =10: 0 01 00 011 101 001 010 0111 1011 11111.

Mathematica

CoefficientList[Series[x (-x^7-x^4+3x^3-2x^2-x+1)/((1-x-x^2) (1-x^2-x^4) (1-x)^2), {x, 0, 50}], x] (* Harvey P. Dale, Jun 15 2011 *)

Crossrefs

If reversals are counted as distinct then we obtain A000126.

A007931 (binary strings represented by ternary numbers),

Cf. A035615 (binary "same game").

Sequence in context: A208479 A065441 A075531 * A121364 A347787 A215006

Adjacent sequences: A066064 A066065 A066066 * A066068 A066069 A066070

Keyword

nonn

Author

Frank Ellermann, Dec 02 2001

Extensions

More terms from Harvey P. Dale, Jun 15 2011

Status

approved