A260668 - OEIS

%I #18 Sep 16 2023 12:02:12

%S 1,2,4,7,13,24,45,84,158,298,566,1079,2066,3966,7635,14730,28484,

%T 55188,107130,208294,405594,790812,1543766,3016923,5901858,11556244,

%U 22647431,44418613,87182680,171234318,336532357,661788956,1302124526,2563365624,5048704640

%N Number of binary words of length n such that for every prefix the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.

%H Alois P. Heinz, <a href="/A260668/b260668.txt">Table of n, a(n) for n = 0..1000</a>

%e a(5) = 2^5 - 8 = 24: 00000, 00001, 00011, 00110, 00111, 01100, 01101, 01110, 01111, 10000, 10001, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111. These 8 words are not counted: 00010, 00100, 00101, 01000, 01001, 01010, 01011, 10010.

%p b:= proc(n, t, c) option remember; `if`(c<0, 0, `if`(n=0, 1,

%p       b(n-1, [2, 4, 6, 4, 6, 4, 6][t], c-`if`(t=5, 1, 0))+

%p       b(n-1, [3, 5, 7, 5, 7, 5, 7][t], c+`if`(t=6, 1, 0))))

%p     end:

%p a:= n-> b(n, 1, 0):

%p seq(a(n), n=0..40);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<6, [1, 2, 4, 7, 13, 24][n+1],

%p       ((680+1441*n-444*n^2+35*n^3)        *a(n-1)

%p        -(4*(-112+625*n-179*n^2+14*n^3))   *a(n-2)

%p        +(2*(1521-656*n+63*n^2))           *a(n-3)

%p        +(2*(-9442+5295*n-947*n^2+56*n^3)) *a(n-4)

%p        -(4*(-6721+3413*n-591*n^2+35*n^3)) *a(n-5)

%p        +(4*(2*n-11))*(7*n^2-79*n+254)     *a(n-6)

%p         )/((n+1)*(7*n^2-93*n+340)))

%p     end:

%p seq(a(n), n=0..40);

%t b[n_, t_, c_] := b[n, t, c] = If[c < 0, 0, If[n == 0, 1,

%t    b[n - 1, {2, 4, 6, 4, 6, 4, 6}[[t]], c - If[t == 5, 1, 0]] +

%t    b[n - 1, {3, 5, 7, 5, 7, 5, 7}[[t]], c + If[t == 6, 1, 0]]]];

%t a[n_] := b[n, 1, 0];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Sep 16 2023, after _Alois P. Heinz_ *)

%Y Cf. A118430, A164146, A255386, A260505, A260697, A303430.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Nov 14 2015