A027559 - OEIS

%I #25 Sep 08 2022 08:44:49

%S 1,2,4,8,16,30,58,106,200,360,668,1190,2182,3858,7012,12328,22256,

%T 38958,69962,122042,218248,379656,676636,1174390,2087222,3615906,

%U 6411716,11090504,19627984,33907134,59912410,103385482,182429768

%N Number of 4-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=4.

%C Also the number of strings of length n with the digits 2 and 3 with the property that the sum of the digits of all substrings of uneven length is not divisible by 5. An example with length 8 is 32332333 . - _Herbert Kociemba_, Apr 29 2017

%H Vincenzo Librandi, <a href="/A027559/b027559.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,4,-3,-3).

%F a(n) = a(n-1) + 4*a(n-2) - 3*a(n-3) - 3*a(n-4).

%F a(0) = 1; for n>0 odd, a(n) = 7 * 3^floor(n/2) - F(n+4); for n>0 even, a(n) = 4 * 3^floor(n/2) - F(n+4) where F(n) is the n-th Fibonacci number. - Barry Guiduli (guiduli(AT)gmail.com), Jun 23 2005

%F G.f.: (1+x-2x^2-x^3+x^4) / ((1-x-x^2)(1-3x^2)). - _David Callan_, Jul 22 2008

%t Join[{1}, LinearRecurrence[{1, 4, -3, -3}, {2, 4, 8, 16}, 30]] (* _Vincenzo Librandi_, Apr 30 2017 *)

%o (Magma)  I:=[2,4,8,16]; [1] cat [n le 4 select I[n] else Self(n-1)+4*Self(n-2)-3*Self(n-3)-3*Self(n-4): n in [1..40]]; // _Vincenzo Librandi_, Apr 30 2017

%K nonn

%O 0,2

%A _R. K. Guy_ and _David Callan_