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
KEYWORD
nonn
AUTHOR
Josh Speckman, Feb 11 2016
EXTENSIONS
More terms from Alois P. Heinz, Feb 11 2016
STATUS
approved