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