A306315 Number of binary words of length n such that the difference between the number of 1's and the number of 0's is in the interval [-2,3] for every prefix and in the interval [-3,2] for every suffix.

1, 2, 4, 6, 12, 18, 35, 54, 103, 162, 307, 486, 926, 1458, 2823, 4374, 8688, 13122, 26962, 39366, 84285, 118098, 265147, 354294, 838625, 1062882, 2664636, 3188646, 8499263, 9565938, 27197074, 28697814, 87261592, 86093442, 280596321, 258280326, 903916589

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..3911

Index entries for linear recurrences with constant coefficients, signature (0,11,0,-46,0,90,0,-81,0,28,0,-3)

Formula

G.f.: -(2*x^11-18*x^9+9*x^8+48*x^7+3*x^6-44*x^5-14*x^4+16*x^3+7*x^2-2*x-1) / ((3*x^2-1) *(x^2+x-1) *(x^2-x-1) *(x^3-2*x^2-x+1) *(x^3+2*x^2-x-1)).

Example

a(3) = 6: 001, 010, 011, 100, 101, 110.
a(4) = 12: 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101, 1110.
a(5) = 18: 00101, 00110, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 11000, 11001, 11010, 11100.
a(6) = 35: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 011000, 011001, 011010, 011100, 100010, 100011, 100100, 100101, 100110, 101000, 101001, 101010, 101011, 101100, 101101, 101110, 110001, 110010, 110011, 110100, 110101, 110110, 111000, 111001, 111010.

Mathematica

LinearRecurrence[{0, 11, 0, -46, 0, 90, 0, -81, 0, 28, 0, -3}, {1, 2, 4, 6, 12, 18, 35, 54, 103, 162, 307, 486}, 40] (* Harvey P. Dale, Sep 17 2019 *)

Crossrefs

Odd bisection gives A008776.

Cf. A306293, A306306.

Sequence in context: A331933 A052823 A063516 * A104352 A370584 A133488

Adjacent sequences: A306312 A306313 A306314 * A306316 A306317 A306318

Keyword

nonn,easy

Author

Alois P. Heinz, Feb 06 2019

Status

approved