OFFSET
0,2
COMMENTS
The alternating coloring function assigns one of the values {-1, 0, 1} to strings over the alphabet {0, 1}. The strings to which the value 0 is assigned are said to be non-colorable.
The alternating coloring function psi is defined as follows:
Let w be a word of length n over the alphabet {0, 1}. If n > 0, let l be the left and r the right subword of length n-1, respectively. psi(w) = (xi(w))^n * phi(w) where xi(w) = 0 if n = 0, xi(w) = 1 if n is even and w of the form 010...1, xi(w) = -1 if n is even and w of the form 101...0, x(w) = sgn(xi(l) + xi(r)) otherwise; phi(w) = 0 if n = 0, phi(w) = -1 if n is odd and w consists of zeros only, phi(w) = 1 if n is odd and w consists of ones only, phi(w) = sgn(phi(r) - phi(l)) otherwise; sgn is the signum function.
In fact, psi(w) = 0 if and only if xi(w) = 0.
LINKS
Paolo Xausa, Table of n, a(n) for n = 0..1000
Jonathan Garbe, An alternating colouring function on strings, arXiv:2411.00562 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).
FORMULA
a(n) = (2^n + 8) / 6 for even n >= 2.
a(n) = (2^n + 16) / 6 for odd n >= 3.
a(n) = 2 * (A001045(n-2) + 1) for n >= 2.
a(n) = 4 * A005578(n-3) for n >= 3.
G.f.: (1 - 3*x^2 - 2*x^4)/((1 - x)*(1 + x)*(1 - 2*x)). - Stefano Spezia, Nov 24 2024
E.g.f.: (8*cosh(x) + cosh(2*x) + 16*sinh(x) + sinh(2*x) - 3 - 6*x)/6. - Stefano Spezia, Jan 28 2025
EXAMPLE
a(3) = 4 because there are 4 non-colorable strings of length 3: {000, 010, 101, 111}.
MATHEMATICA
LinearRecurrence[{2, 1, -2}, {1, 2, 2, 4, 4}, 50] (* Paolo Xausa, Jan 28 2025 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Jonathan Garbe, Nov 16 2024
STATUS
approved