login
A331394
Number of ways of 4-coloring the Fibonacci square spiral tiling of n squares with colors introduced in order.
1
1, 1, 1, 2, 3, 5, 6, 7, 11, 16, 19, 25, 38, 51, 63, 88, 127, 165, 214, 303, 419, 544, 731, 1025, 1382, 1819, 2487, 3432, 4583, 6125, 8406, 11447, 15291, 20656, 28259, 38185, 51238, 69571, 94703, 127608, 172047, 233845
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
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