A306293 Number of binary words of length n such that in every prefix and in every suffix the number of 0's and the number of 1's differ by at most two.

1, 2, 4, 6, 10, 16, 26, 42, 70, 110, 194, 288, 550, 754, 1586, 1974, 4630, 5168, 13634, 13530, 40390, 35422, 120146, 92736, 358390, 242786, 1071074, 635622, 3205030, 1664080, 9598706, 4356618, 28763350, 11405774, 86224514, 29860704, 258542470, 78176338

Offset: 0

Author

Alois P. Heinz, Feb 04 2019

Keywords

• nonn
• easy

Comments

All terms with index n > 0 are even.

Examples

			a(3) = 6: 001, 010, 011, 100, 101, 110.
a(4) = 10: 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101.
a(5) = 16: 00101, 00110, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 11001, 11010.
a(6) = 26: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 011001, 011010, 011100, 100011, 100101, 100110, 101001, 101010, 101011, 101100, 101101, 110001, 110010, 110011, 110100, 110101.
a(7) = 42: 0010101, 0010110, 0011001, ..., 1100110, 1101001, 1101010.
a(8) = 70: 00101010, ..., 00111100, ..., 11000011, ..., 11010101.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..4193
• Index entries for linear recurrences with constant coefficients, signature (0,8,0,-22,0,23,0,-6).

Crossrefs

Bisections of a(n+2)/2 give: A007689 (even part), A001906(n+2) (odd part).

Cf. A068911, A128588, A303696, A306306, A306315.

Programs

Maple

a:= n-> `if`(n<2, 1+n, 2*(<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,
        <-6|23|-22|8>>^iquo(n-2, 2, 'r').[<<2, 5, 13, 35>>,
        <<3, 8, 21, 55>>][1+r])[1, 1]):
seq(a(n), n=0..50);

Formula

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

a(n) <= A306306(n).