cp's OEIS Frontend

A164137 Number of binary strings of length n with equal numbers of 000 and 001 substrings.

%I A164137 #24 Apr 03 2024 21:38:37
%S A164137 1,2,4,6,11,19,35,61,111,200,369,676,1256,2337,4392,8273,15686,29837,
%T A164137 57038,109362,210448,406029,785573,1523217,2959853,5761671,11234619,
%U A164137 21937768,42894822,83969696,164552423,322773812,633679446,1245032098,2447951456,4816241573
%N A164137 Number of binary strings of length n with equal numbers of 000 and 001 substrings.
%H A164137 R. H. Hardin, <a href="/A164137/b164137.txt">Table of n, a(n) for n=0..500</a>
%H A164137 Shalosh B. Ekhad and Doron Zeilberger, <a href="http://arxiv.org/abs/1112.6207">Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type</a>, arXiv preprint arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]
%F A164137 From _Robert P. P. McKone_, Apr 03 2024: (Start)
%F A164137 a(n) = 2^n - A371662(n) - A371682(n).
%F A164137 Conjecture: a(n) = ((8*n-72)*a(n-10) + (20*n-160)*a(n-9) + (6*n-26)*a(n-8) + (46-5*n)*a(n-7) - 16*a(n-6) + (56-11*n)*a(n-5) + (12-n)*a(n-4) + (n-18)*a(n-3) + n*a(n-2) + 2*n*a(n-1))/n for n>=10.
%F A164137 (End)
%e A164137 From _Robert P. P. McKone_, Apr 03 2024: (Start)
%e A164137 a(3) = 6: 010, 011, 100, 101, 110, 111.
%e A164137 a(4) = 11: 0001, 0100, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111.
%e A164137 a(5) = 19: 00010, 00011, 01010, 01011, 01100, 01101, 01110, 01111, 10001, 10100, 10101, 10110, 10111, 11010, 11011, 11100, 11101, 11110, 11111.
%e A164137 (End)
%t A164137 tup[n_] := Tuples[{0, 1}, n];
%t A164137 cou[lst_List] := Count[lst, {0, 0, 0}] == Count[lst, {0, 0, 1}];
%t A164137 par[lst_List] := Partition[lst, 3, 1];
%t A164137 a[n_] := a[n] = Map[cou, Map[par, tup[n]]] // Boole // Total;
%t A164137 Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}] (* _Robert P. P. McKone_, Apr 03 2024 *)
%Y A164137 Cf. A371662 (more 000 than 001), A371682 (more 001 than 000).
%Y A164137 Cf. A163493 (equal 00 and 01).
%K A164137 nonn
%O A164137 0,2
%A A164137 _R. H. Hardin_, Aug 11 2009