login
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].
3

%I #14 Feb 06 2019 15:13:16

%S 1,2,4,7,12,21,35,62,102,184,299,551,882,1666,2615,5085,7782,15658,

%T 23219,48603,69402,151945,207695,477987,622062,1511741,1864139,

%U 4803125,5588322,15319484,16756775,49018968,50253942,157270414,150729059,505697248,452121642

%N 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].

%H Alois P. Heinz, <a href="/A306306/b306306.txt">Table of n, a(n) for n = 0..3912</a>

%H <a href="/index/Rec#order_16">Index entries for linear recurrences with constant coefficients</a>, signature (0,14,0,-81,0,250,0,-443,0,451,0,-249,0,65,0,-6)

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

%F a(n) >= A306293(n).

%e a(3) = 7: 001, 010, 011, 100, 101, 110, 111.

%e a(4) = 12: 0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110.

%e a(5) = 21: 00101, 00110, 00111, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101.

%e 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.

%e a(7) = 62: 0010101, 0010110, 0010111, ..., 1110010, 1110011, 1110100, 1110101.

%Y Cf. A306293, A306315.

%K nonn,easy

%O 0,2

%A _Alois P. Heinz_, Feb 05 2019