A268691 Number of n-digit binary strings such that for all 2 <= k <= n, the string formed by the first k digits of the original string is composed of at least one-quarter 1's and one-quarter 0's.

1, 2, 2, 4, 8, 12, 24, 48, 96, 180, 360, 720, 1440, 2820, 5640, 11280, 22560, 44760, 89520, 179040, 358080, 713760, 1427520, 2855040, 5710080, 11403060, 22806120, 45612240, 91224480, 182321460, 364642920, 729285840, 1458571680, 2916160800, 5832321600

Offset

0,2

Links

Alois P. Heinz and Charles R Greathouse IV, Table of n, a(n) for n = 0..3323 (0-1000 from Heinz)

Formula

For all n > 2 not equivalent to 1 mod 4, a(n) = 2a(n-1).

Example

For n=2, the strings are 01 and 10. For n=3, they are 010, 011, 100, 101.

Maple

b:= proc(n, i, j) option remember; `if`(n=0, 1, (t->
      `if`(t>=2 and 4*j<t, 0, b(n-1, sort([j, i+1])[]))+
      `if`(t>=2 and 4*i<t, 0, b(n-1, sort([i, j+1])[])))(i+j+1))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 11 2016

Mathematica

b[n_, i_, j_] := b[n, i, j] = If[n == 0, 1, Function[t,
    If[t >= 2 && 4j < t, 0, b[n-1, Sequence @@ Sort[{j, i+1}]]]+
    If[t >= 2 && 4i < t, 0, b[n-1, Sequence @@ Sort[{i, j+1}]]]][i+j+1]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 50] (* Jean-François Alcover, Nov 27 2020, after Alois P. Heinz *)

Prog

(PARI) a(n)=if(n<2, return(n+1)); my(u, v=vector((3*n+1)\4), mx, mn); v[1]=2; for(i=3, n, mn=(i+3)\4; mx=i-mn; u=vector(#v, j, if(j<mn||j>mx, 0, if(j>1, v[j-1])+v[j])); v=u); vecsum(v) \\ Charles R Greathouse IV, Feb 11 2016
(PARI) first(n)=if(n<2, return(n+1)); my(u, v=vector((3*n+1)\4), w=vector(n+1), mx, mn); w[1]=1; w[2]=w[3]=v[1]=2; for(i=3, n, mn=(i+3)\4; mx=i-mn; u=vector(#v, j, if(j<mn||j>mx, 0, if(j>1, v[j-1])+v[j])); w[i+1]=vecsum(v=u)); w \\ Charles R Greathouse IV, Feb 11 2016

Crossrefs

Sequence in context: A244781 A052907 A048114 * A102456 A032067 A337361

Adjacent sequences: A268688 A268689 A268690 * A268692 A268693 A268694

Keyword

nonn

Author

Josh Speckman, Feb 11 2016

Extensions

More terms from Alois P. Heinz, Feb 11 2016

Status

approved