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

1, 2, 4, 7, 13, 24, 45, 84, 158, 298, 566, 1079, 2066, 3966, 7635, 14730, 28484, 55188, 107130, 208294, 405594, 790812, 1543766, 3016923, 5901858, 11556244, 22647431, 44418613, 87182680, 171234318, 336532357, 661788956, 1302124526, 2563365624, 5048704640

Offset: 0

Author

Alois P. Heinz, Nov 14 2015

Keywords

• nonn

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

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

Programs

Maple

b:= proc(n, t, c) option remember; `if`(c<0, 0, `if`(n=0, 1,
      b(n-1, [2, 4, 6, 4, 6, 4, 6][t], c-`if`(t=5, 1, 0))+
      b(n-1, [3, 5, 7, 5, 7, 5, 7][t], c+`if`(t=6, 1, 0))))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<6, [1, 2, 4, 7, 13, 24][n+1],
      ((680+1441*n-444*n^2+35*n^3)        *a(n-1)
       -(4*(-112+625*n-179*n^2+14*n^3))   *a(n-2)
       +(2*(1521-656*n+63*n^2))           *a(n-3)
       +(2*(-9442+5295*n-947*n^2+56*n^3)) *a(n-4)
       -(4*(-6721+3413*n-591*n^2+35*n^3)) *a(n-5)
       +(4*(2*n-11))*(7*n^2-79*n+254)     *a(n-6)
        )/((n+1)*(7*n^2-93*n+340)))
    end:
seq(a(n), n=0..40);

Mathematica

b[n_, t_, c_] := b[n, t, c] = If[c < 0, 0, If[n == 0, 1,
   b[n - 1, {2, 4, 6, 4, 6, 4, 6}[[t]], c - If[t == 5, 1, 0]] +
   b[n - 1, {3, 5, 7, 5, 7, 5, 7}[[t]], c + If[t == 6, 1, 0]]]];
a[n_] := b[n, 1, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Sep 16 2023, after Alois P. Heinz *)