A164163 Number of binary strings of length n with equal numbers of 0001 and 1010 substrings.

1, 2, 4, 8, 14, 24, 41, 72, 129, 234, 431, 804, 1512, 2864, 5459, 10452, 20086, 38728, 74871, 145068, 281646, 547764, 1066943, 2081060, 4064097, 7945534, 15549613, 30459088, 59714564, 117160356, 230034585, 451954208, 888513601, 1747769154

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (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]

Maple

b:= proc(n, t) option remember; `if`(n=0, 1, expand(
      b(n-1, [2, 3, 4$2, 6, 3, 6][t])*`if`(t=7, 1/x, 1)+
      b(n-1, `if`(t=6, 7, 5))*`if`(t=4, x, 1)))
    end:
a:= n-> coeff(b(n, 1), x, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 28 2014
# second Maple program:
a:= proc(n) option remember; `if`(n<6, [1, 2, 4, 8, 14, 24][n+1],
     ((166*n^3-719*n^2-4319*n+6834) *a(n-1)
     +(162*n^3-4025*n^2+23078*n-21720) *a(n-2)
     +(58*n^3+459*n^2-10135*n+32226) *a(n-3)
     -6*(n-6)*(10*n^2+611*n-4579) *a(n-4)
     -4*(n-7)*(218*n^2-3243*n+10692) *a(n-5)
     +8*(n-7)*(n-8)*(82*n-339) *a(n-6))/
     (n*(110*n^2-1067*n+1938)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 28 2014

Mathematica

a[n_] := a[n] = If[n < 6, {1, 2, 4, 8, 14, 24}[[n + 1]], (1/(n*(110*n^2 - 1067*n + 1938)))*(-(4*(n - 7)*(218*n^2 - 3243*n + 10692)*a[n - 5]) - 6*(n - 6)*(10*n^2 + 611*n - 4579)*a[n - 4] + (58*n^3 + 459*n^2 - 10135*n + 32226)*a[n - 3] + (162*n^3 - 4025*n^2 + 23078*n - 21720)*a[n - 2] + (166*n^3 - 719*n^2 - 4319*n + 6834)*a[n - 1] + 8*(82*n - 339)*(n - 8)*(n - 7)*a[n - 6])];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 11 2017, after Alois P. Heinz *)

Crossrefs

Sequence in context: A164396 A164400 A164405 * A164395 A164160 A164394

Adjacent sequences: A164160 A164161 A164162 * A164164 A164165 A164166

Keyword

nonn

Author

R. H. Hardin, Aug 11 2009

Status

approved