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

Author

Alois P. Heinz, Feb 06 2019

Keywords

• nonn
• easy

Examples

			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.
		

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)

Crossrefs

Odd bisection gives A008776.

Cf. A306293, A306306.

Programs

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

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