login
Number of binary strings of length n which have more 01 than 00 substrings.
4

%I #34 May 01 2024 11:29:00

%S 0,0,1,3,6,13,28,56,113,231,464,930,1875,3766,7547,15151,30398,60917,

%T 122116,244786,490435,982544,1968413,3942649,7896116,15813268,

%U 31665423,63403245,126945244,254152625,508798604,1018538560,2038870881,4081149015,8168806568

%N Number of binary strings of length n which have more 01 than 00 substrings.

%F a(n) = 2^n - A163493(n) - A371358(n).

%F a(n) = (1 - 8*(n-4)*a(n-5) + 4*(3*n-10)*a(n-4) + 2*(8-3*n)*a(n-3) + (5*n-12)*a(n-2) + (7-4*n)*a(n-1))/(1-n) for n>=5.

%F For n >= 2, a(n) = 2*a(n-1) - A163493(n) + A163493(n-1) + A163493(n-2) + A370048(n-2). - _Max Alekseyev_, May 01 2024

%F G.f.: ((1-3*x+2*x^2)^(-1) - (1-2*x+x^2-4*x^3+4*x^4)^(-1/2)) * x / 2. - _Max Alekseyev_, Apr 30 2024

%e a(4) = 6: 0101, 0110, 0111, 1010, 1011, 1101.

%e a(5) = 13: 0010, 0100, 0101, 0101, 0110, 0111, 0111, 1010, 1011, 1011, 1101, 1101, 1110.

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

%p add(b(n-1, i, t-`if`(l=0, (-1)^i, 0)), i=0..1)))

%p end:

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

%p seq(a(n), n=0..34); # _Alois P. Heinz_, Mar 27 2024

%t tup[n_] := Tuples[{0, 1}, n];

%t cou[lst_List] := Count[lst, {0, 1}] > Count[lst, {0, 0}];

%t par[lst_List] := Partition[lst, 2, 1];

%t a[n_] := Map[cou, Map[par, tup[n]]] // Boole // Total;

%t Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

%Y Cf. A163493 (equal 00 and 01), A371358 (more 00 than 01), A090129 (equal 01 and 10), A182027 (equal 00 and 11), A370048 (one more 00 than 01).

%Y Cf. A000079(n-2) (more 01 than 10, for n>=2).

%K nonn

%O 0,4

%A _Robert P. P. McKone_, Mar 27 2024