%I #18 Jun 13 2015 00:49:07
%S 1,2,4,8,14,26,44,78,130,224,370,626,1028,1718,2810,4656,7594,12506,
%T 20356,33374,54242,88640,143906,234594,380548,619238,1003882,1631312,
%U 2643386,4291082,6950852,11274702,18258322,29598560
%N Number of 3-balanced strings of length n: let d(S)= #(1)'s in S - #(0)'s, then S is k-balanced if every substring T has -k<=d(T)<=k; here k=3.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-2,-2).
%F a(n) = a(n-1) + 3a(n-2) - 2a(n-3) - 2a(n-4); g.f. (1+x-x^2) / (1-x-x^2)(1-2x^2).
%F a(n) = 2*A000045(n+3) - 2^floor((n+2)/2) - 2^floor((n+1)/2). - _Max Alekseyev_, Jun 02 2005
%t LinearRecurrence[{1,3,-2,-2},{1,2,4,8},40] (* _Harvey P. Dale_, Feb 01 2012 *)
%o (PARI) a(n) = 2*fibonacci(n+3) - 2^((n+2)\2) - 2^((n+1)\2) /* _Max Alekseyev_ */
%K nonn
%O 0,2
%A _R. K. Guy_, _David Callan_