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,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

Cf. A000045, A216790, A077951.

Sequence in context: A369635 A362455 A062084 * A273524 A098959 A071251

Adjacent sequences: A331391 A331392 A331393 * A331395 A331396 A331397

Keyword

nonn

Author

Michael C. Case, Jan 15 2020

Status

approved