A164137 - OEIS

%I #25 Nov 05 2025 15:22:17

%S 1,2,4,6,11,19,35,61,111,200,369,676,1256,2337,4392,8273,15686,29837,

%T 57038,109362,210448,406029,785573,1523217,2959853,5761671,11234619,

%U 21937768,42894822,83969696,164552423,322773812,633679446,1245032098,2447951456,4816241573

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

%H R. H. Hardin, <a href="/A164137/b164137.txt">Table of n, a(n) for n=0..500</a>

%H Shalosh B. Ekhad and Doron Zeilberger, <a href="https://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 From _Robert P. P. McKone_, Apr 03 2024: (Start)

%F a(n) = 2^n - A371662(n) - A371682(n).

%F 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 (End)

%e From _Robert P. P. McKone_, Apr 03 2024: (Start)

%e a(3) = 6: 010, 011, 100, 101, 110, 111.

%e a(4) = 11: 0001, 0100, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111.

%e a(5) = 19: 00010, 00011, 01010, 01011, 01100, 01101, 01110, 01111, 10001, 10100, 10101, 10110, 10111, 11010, 11011, 11100, 11101, 11110, 11111.

%e (End)

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

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

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

%t a[n_] := 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}]}] (* _Robert P. P. McKone_, Apr 03 2024 *)

%Y Cf. A371662 (more 000 than 001), A371682 (more 001 than 000).

%Y Cf. A163493 (equal 00 and 01).

%K nonn

%O 0,2

%A _R. H. Hardin_, Aug 11 2009