A164147 Number of binary strings of length n with equal numbers of 0000 and 0001 substrings.

1, 2, 4, 8, 14, 27, 51, 96, 183, 345, 655, 1244, 2363, 4500, 8570, 16347, 31218, 59678, 114236, 218905, 419979, 806693, 1551247, 2986469, 5756025, 11106397, 21453737, 41486062, 80309039, 155625030, 301882458, 586178231, 1139315438, 2216511306

Offset: 0

Author

R. H. Hardin, Aug 11 2009

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3327 (first 501 terms from R. H. Hardin)
• Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, 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]

Crossrefs

Cf. A163493 (equal 00 and 01), A164137 (equal 000 and 001), A164178 (equal 00000 and 00001).

Programs

Mathematica

tup[n_] := Tuples[{0, 1}, n];
cou[lst_List] := Count[lst, {0, 0, 0, 0}] == Count[lst, {0, 0, 0, 1}];
par[lst_List] := Partition[lst, 4, 1];
a[n_] := a[n] = Map[cou, Map[par, tup[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}] (* Robert P. P. McKone, Apr 03 2024 *)