|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|