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,2

Comments

All terms with index n > 0 are even.

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

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

Example

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.

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

Crossrefs

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

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

Sequence in context: A364580 A128588 A023613 * A307795 A065795 A293077

Adjacent sequences: A306290 A306291 A306292 * A306294 A306295 A306296

Keyword

nonn,easy

Author

Alois P. Heinz, Feb 04 2019

Status

approved