A306306 -id:A306306 - 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).

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.

Original entry on oeis.org

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

Alois P. Heinz, Feb 06 2019

			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.

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)

Odd bisection gives A008776.

Cf. A306293, A306306.

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

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

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