login
A027559
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.
2
1, 2, 4, 8, 16, 30, 58, 106, 200, 360, 668, 1190, 2182, 3858, 7012, 12328, 22256, 38958, 69962, 122042, 218248, 379656, 676636, 1174390, 2087222, 3615906, 6411716, 11090504, 19627984, 33907134, 59912410, 103385482, 182429768
OFFSET
0,2
COMMENTS
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
FORMULA
a(n) = a(n-1) + 4*a(n-2) - 3*a(n-3) - 3*a(n-4).
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
G.f.: (1+x-2x^2-x^3+x^4) / ((1-x-x^2)(1-3x^2)). - David Callan, Jul 22 2008
MATHEMATICA
Join[{1}, LinearRecurrence[{1, 4, -3, -3}, {2, 4, 8, 16}, 30]] (* Vincenzo Librandi, Apr 30 2017 *)
PROG
(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
CROSSREFS
Sequence in context: A164185 A164180 A164179 * A344614 A337664 A135492
KEYWORD
nonn
AUTHOR
STATUS
approved