A260697 Number of binary words w of length n with equal numbers of 010 and 101 subwords such that for every prefix of w the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.
1, 2, 4, 6, 11, 18, 32, 54, 95, 164, 291, 514, 923, 1656, 3000, 5442, 9942, 18216, 33564, 62040, 115167, 214404, 400497, 750070, 1408734, 2652088, 5004833, 9464616, 17935137, 34049044, 64754844, 123351410, 235335966, 449632300, 860241606, 1647932000
Offset: 0
Keywords
Examples
a(3) = 6: 000, 001, 011, 100, 110, 111. a(4) = 11: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1010, 1100, 1110, 1111. a(5) = 18: 00000, 00001, 00011, 00110, 00111, 01100, 01110, 01111, 10000, 10001, 10011, 10100, 11000, 11001, 11010, 11100, 11110, 11111. a(10) = 291: 0000000000, 0000000001, 0000000011, ..., 0110101010, 1010101000, 1010101001, 1010101010, 1101010100, 1110101010, ..., 1111111100, 1111111110, 1111111111.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
Programs
-
Maple
b:= proc(n, t, c) option remember; `if`(c<0, 0, `if`(n=0, `if`(c=0, 1, 0), 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<7, [1, 2, 4, 6, 11, 18, 32][n+1], ((n+3)*(307*n^2-2357*n+196) *a(n-1) -(19280-3372*n-5181*n^2+719*n^3) *a(n-2) +(2*(6582+268*n^3-2857*n^2+6959*n)) *a(n-3) +(2*(-3307*n^2+1151*n+384*n^3+9052)) *a(n-4) -(2*(1016*n^3-12133*n^2+38927*n-28304)) *a(n-5) +(4*(27387*n+431*n^3-38420-6108*n^2)) *a(n-6) -(4*(n-7))*(67*n-236)*(2*n-11) *a(n-7) )/((2*(n+4))*(24*n^2-148*n-279))) end: seq(a(n), n=0..40); -
Mathematica
b[n_, t_, c_] := b[n, t, c] = If[c < 0, 0, If[n == 0, If[c == 0, 1, 0], 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, Mar 02 2022, after Alois P. Heinz *)