A164139 Number of binary strings of length n with equal numbers of 000 and 011 substrings.

1, 2, 4, 6, 9, 14, 22, 38, 66, 120, 222, 416, 792, 1512, 2909, 5610, 10851, 21042, 40864, 79514, 154911, 302210, 590251, 1154012, 2258488, 4423856, 8672541, 17014530, 33404100, 65624480, 129002143, 253733246, 499333096, 983154996, 1936685718

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

a:= proc(n) a(n):= `if`(n<8, [1, 2, 4, 6, 9, 14, 22, 38][n+1],
       ((32*n^2-136*n+18)*a(n-1) +(8*n^2-66*n+52)*a(n-2)
        -(46*n^2-225*n+11)*a(n-3) -2*(n-3)*(4*n-25)*a(n-4)
        +(72*n^2-448*n+400)*a(n-5) -(69*n^2-445*n+464)*a(n-6)
        -(4*n^2-54*n-78)*a(n-7) +4*(7*n-4)*(n-6)*a(n-8))/
        (n*(13*n-56)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 29 2014

Mathematica

a[n_] := If[n < 8, {1, 2, 4, 6, 9, 14, 22, 38}[[n + 1]], (1/(n*(13*n - 56)))*(a*(-(4*n^2 - 54*n - 78))*(n - 7) - (69*n^2 - 445*n + 464)*a[n - 6] + (72*n^2 - 448*n + 400)*a[n - 5] - (46*n^2 - 225*n + 11)*a[n - 3] + (8*n^2 - 66*n + 52)*a[n - 2] + (32*n^2 - 136*n + 18)*a[n - 1] + 4*(n - 6)*(7*n - 4)*a[n - 8] - 2*(n - 3)*(4*n - 25)*a[n - 4])];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 11 2017, after Alois P. Heinz *)

Crossrefs

Sequence in context: A042942 A256968 A005687 * A218605 A024849 A323227

Adjacent sequences: A164136 A164137 A164138 * A164140 A164141 A164142

Keyword

nonn,easy

Author

R. H. Hardin, Aug 11 2009

Status

approved