cp's OEIS Frontend

A331394 Number of ways of 4-coloring the Fibonacci square spiral tiling of n squares with colors introduced in order.

%I A331394 #26 Jul 04 2023 14:16:03
%S A331394 1,1,1,2,3,5,6,7,11,16,19,25,38,51,63,88,127,165,214,303,419,544,731,
%T A331394 1025,1382,1819,2487,3432,4583,6125,8406,11447,15291,20656,28259,
%U A331394 38185,51238,69571,94703,127608,172047,233845
%N A331394 Number of ways of 4-coloring the Fibonacci square spiral tiling of n squares with colors introduced in order.
%C A331394 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.
%C A331394 The Fibonacci square spiral tiling for 6 squares:
%C A331394    _____ ___ _______________
%C A331394   |     |   |               |
%C A331394   |     |_ _|               |
%C A331394   |_____|_|_|               |
%C A331394   |         |               |
%C A331394   |         |               |
%C A331394   |         |               |
%C A331394   |         |               |
%C A331394   |_________|_______________|
%C A331394 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.
%C A331394 The first 3 squares must be colored ABC but for k>3 square k can be the same color as square k-2.
%H A331394 Michael C. Case, <a href="/A331394/b331394.txt">Table of n, a(n) for n = 1..200</a> [a(192) corrected by _Georg Fischer_, Apr 15 2020]
%H A331394 Wikipedia, <a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>
%H A331394 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1, -1, 2).
%F A331394 a(n) = a(n-1) - a(n-2) + 2*a(n-3) for n >= 7.
%F A331394 G.f.: x*(1 + x)*(1 - x + 2*x^2 - 2*x^3 + 2*x^4)/(1 - x + x^2 - 2*x^3).
%F A331394 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... .
%e A331394 There are 3 ways to 4-color a Fibonacci square spiral tiling of 5 squares:
%e A331394    _____ ___   _____ ___   _____ ___
%e A331394   |     | C | |     | C | |     | C |
%e A331394   |  B  |_ _| |  B  |_ _| |  D  |_ _|
%e A331394   |_____|A|B| |_____|A|B| |_____|A|B|
%e A331394   |         | |         | |         |
%e A331394   |         | |         | |         |
%e A331394   |    C    | |    D    | |    C    |
%e A331394   |         | |         | |         |
%e A331394   |_________| |_________| |_________| so a(5)=3.
%e A331394 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.
%t A331394 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 *)
%Y A331394 Cf. A000045, A216790, A077951.
%K A331394 nonn
%O A331394 1,4
%A A331394 _Michael C. Case_, Jan 15 2020