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,2

Links

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

Example

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.

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

Crossrefs

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

Sequence in context: A059633 A088353 A192654 * A371789 A018184 A192675

Adjacent sequences: A260665 A260666 A260667 * A260669 A260670 A260671

Keyword

nonn

Author

Alois P. Heinz, Nov 14 2015

Status

approved