A331394 Number of ways of 4-coloring the Fibonacci square spiral tiling of n squares with colors introduced in order.
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
Keywords
Examples
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.
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).
Programs
-
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 *)
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... .
Comments