OFFSET
1,4
COMMENTS
The Fibonacci square spiral tiling is the pattern formed by tiling the plane using squares with side-lengths of successive Fibonacci numbers (so the k-th square is of size F(k)), in a spiral pattern.
The Fibonacci square spiral tiling for 6 squares:
_____ ___ _______________
| | | |
| |_ _| |
|_____|_|_| |
| | |
| | |
| | |
| | |
|_________|_______________|
In a 4-coloring of the Fibonacci square spiral tiling, the square k cannot be the same color as squares k-4, k-3, or k-1. When k-1 is the same color as k-3, k can be colored in 2 different ways.
The first 3 squares must be colored ABC but for k>3 square k can be the same color as square k-2.
LINKS
Michael C. Case, Table of n, a(n) for n = 1..200 [a(192) corrected by Georg Fischer, Apr 15 2020]
Wikipedia, Fibonacci number
Index entries for linear recurrences with constant coefficients, signature (1, -1, 2).
FORMULA
a(n) = a(n-1) - a(n-2) + 2*a(n-3) for n >= 7.
G.f.: x*(1 + x)*(1 - x + 2*x^2 - 2*x^3 + 2*x^4)/(1 - x + x^2 - 2*x^3).
a(n)/a(n-1) approaches the only real solution of x^3 - x^2 + x - 2 = 0, x = (1 - 2*(2/(47 + 3*sqrt(249)))^(1/3) + ((47 + 3*sqrt(249))/2)^(1/3))/3 = 1.35320996419932... .
EXAMPLE
There are 3 ways to 4-color a Fibonacci square spiral tiling of 5 squares:
_____ ___ _____ ___ _____ ___
| | C | | | C | | | C |
| B |_ _| | B |_ _| | D |_ _|
|_____|A|B| |_____|A|B| |_____|A|B|
| | | | | |
| | | | | |
| C | | D | | C |
| | | | | |
|_________| |_________| |_________| so a(5)=3.
There are 7 ways to 4-color a Fibonacci square spiral tiling of 8 squares (ABCBCADA, ABCBCDAD, ABCBDADA, ABCBDADC, ABCDCABA, ABCDCDAB, ABCDCDBA), so a(7) = 8.
MATHEMATICA
Rest@ CoefficientList[Series[x (1 + x) (1 - x + 2 x^2 - 2 x^3 + 2 x^4)/(1 - x + x^2 - 2 x^3), {x, 0, 42}], x] (* Michael De Vlieger, Jan 31 2020 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Michael C. Case, Jan 15 2020
STATUS
approved