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

Author

Frank Ellermann, Dec 02 2001

Keywords

• nonn

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

Examples

			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.
		

Links

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

Crossrefs

If reversals are counted as distinct then we obtain A000126.

A007931 (binary strings represented by ternary numbers),

Cf. A035615 (binary "same game").

Programs

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 *)

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

Extensions

More terms from Harvey P. Dale, Jun 15 2011