A306315 -id:A306315 - cp's OEIS frontend

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

Alois P. Heinz, Feb 04 2019

All terms with index n > 0 are even.

			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.

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

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

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

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

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

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

Original entry on oeis.org

1, 2, 4, 7, 12, 21, 35, 62, 102, 184, 299, 551, 882, 1666, 2615, 5085, 7782, 15658, 23219, 48603, 69402, 151945, 207695, 477987, 622062, 1511741, 1864139, 4803125, 5588322, 15319484, 16756775, 49018968, 50253942, 157270414, 150729059, 505697248, 452121642

Offset: 0

Alois P. Heinz, Feb 05 2019

			a(3) = 7: 001, 010, 011, 100, 101, 110, 111.
a(4) = 12: 0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110.
a(5) = 21: 00101, 00110, 00111, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101.
a(6) = 35: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 010111, 011001, 011010, 011011, 011100, 011101, 011110, 100011, 100101, 100110, 100111, 101001, 101010, 101011, 101100, 101101, 101110, 110001, 110010, 110011, 110100, 110101, 110110, 111001, 111010.
a(7) = 62: 0010101, 0010110, 0010111, ..., 1110010, 1110011, 1110100, 1110101.

Alois P. Heinz, Table of n, a(n) for n = 0..3912
Index entries for linear recurrences with constant coefficients, signature (0,14,0,-81,0,250,0,-443,0,451,0,-249,0,65,0,-6)

Cf. A306293, A306315.

G.f.: -(x^16 -10*x^14 +31*x^12 +54*x^11 -27*x^10 -153*x^9 -27*x^8 +165*x^7 +59*x^6 -85*x^5 -37*x^4 +21*x^3 +10*x^2 -2*x-1) / ((x-1) *(x+1) *(3*x^2-1) *(2*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)).

a(n) >= A306293(n).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula