Problem 843: Periodic Tilings

Mathematical Analysis

Kasteleyn’s Formula

Theorem (Kasteleyn, 1961; Temperley-Fisher). The number of domino tilings of an $m \times n$ grid is:

Proof sketch. Represent the grid as a planar bipartite graph. The number of perfect matchings equals $|\text{Pf}(A)| = \sqrt{\det(A)}$ where $A$ is the Kasteleyn-signed adjacency matrix. The determinant factors over the eigenvalues of the Laplacian, yielding the product formula. $\square$

Transfer Matrix Method

Definition. A profile for column $j$ is a binary string of length $m$ indicating which cells are already covered by a horizontal domino extending from column $j-1$.

Theorem. $T(m, n) = \mathbf{e}^T \cdot M^n \cdot \mathbf{e}_0$ where $M$ is the $2^m \times 2^m$ transfer matrix encoding valid transitions between column profiles, and $\mathbf{e}_0, \mathbf{e}$ are the zero and terminal profile vectors.

The transfer matrix has entries $M[s][t] = 1$ if profile $s$ can transition to profile $t$ by placing vertical and horizontal dominoes in one column.

Recurrence Relations

For small $m$:

• $T(1, n) = [n \text{ even}]$ (only horizontal dominoes fit)
• $T(2, n) = F_{n+1}$ (Fibonacci numbers)
• $T(3, n) = [n \text{ even}] \cdot a_{n/2}$ where $a_k = 4a_{k-1} - a_{k-2}$, $a_0 = 1, a_1 = 3$

Proof for $m=2$. The recurrence $T(2, n) = T(2, n-1) + T(2, n-2)$ arises because: the rightmost column is either covered by a vertical domino (leaving $T(2,n-1)$) or two horizontal dominoes (leaving $T(2,n-2)$). With $T(2,0)=1, T(2,1)=1$, this is Fibonacci. $\square$

Concrete Examples

Verification for $T(2,3) = 3$: The three tilings are: (1) three horizontal pairs stacked, (2) left vertical + right horizontal pair, (3) right vertical + left horizontal pair. Actually for $2 \times 3$: we need 3 dominoes. The tilings are: HHH (all horizontal, impossible since 2x3 has 6 cells needing 3 dominoes), VHH, HVH, HHV where V means vertical and H means a horizontal pair. Specifically: 3 tilings confirmed.

Parity Constraint

Lemma. $T(m, n) = 0$ whenever $mn$ is odd, since each domino covers exactly 2 cells and $mn$ cells cannot be covered.

Asymptotic Growth

Theorem. For fixed $m$, $T(m, n) \sim C_m \cdot \lambda_m^n$ where $\lambda_m$ is the largest eigenvalue of the transfer matrix. For the $m \to \infty$ limit:

where $G = \sum_{k=0}^{\infty} (-1)^k/(2k+1)^2 = 0.91597\ldots$ is Catalan’s constant.

Complexity Analysis

• Kasteleyn formula: $O(mn)$ arithmetic operations (floating point, so not exact for modular answers).
• Transfer matrix: $O(4^m \cdot n)$ time, $O(4^m)$ space. Practical for $m \le 15$.
• Transfer matrix with exponentiation: $O(4^m \cdot m \cdot \log n)$ for very large $n$.
• Profile DP: $O(2^m \cdot n)$ time, $O(2^m)$ space. Practical for $m \le 20$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 843: Periodic Tilings
 *
 * Count domino tilings of m x n grid via profile DP.
 * Profile = bitmask of m bits showing which cells extend to next column.
 */

typedef long long ll;

int M, N;

void fill_column(int profile_in, int profile_out, int row,
                 vector<pair<int,int>>& transitions) {
    if (row == M) {
        transitions.push_back({profile_in, profile_out});
        return;
    }
    if ((profile_in >> row) & 1) {
        fill_column(profile_in, profile_out, row + 1, transitions);
    } else {
        // Horizontal domino
        fill_column(profile_in, profile_out | (1 << row), row + 1, transitions);
        // Vertical domino
        if (row + 1 < M && !((profile_in >> (row + 1)) & 1)) {
            fill_column(profile_in, profile_out, row + 2, transitions);
        }
    }
}

ll solve(int m, int n) {
    if ((ll)m * n % 2 == 1) return 0;
    M = m; N = n;
    if (M > N) swap(M, N);

    // Build all valid transitions
    vector<pair<int,int>> transitions;
    for (int mask = 0; mask < (1 << M); mask++) {
        fill_column(mask, 0, 0, transitions);
    }

    // DP
    vector<ll> dp(1 << M, 0);
    dp[0] = 1;
    for (int col = 0; col < N; col++) {
        vector<ll> ndp(1 << M, 0);
        for (auto [from, to] : transitions) {
            ndp[to] += dp[from];
        }
        dp = ndp;
    }
    return dp[0];
}

int main() {
    // Verify known values
    assert(solve(2, 3) == 3);
    assert(solve(4, 4) == 36);
    assert(solve(2, 10) == 89);
    assert(solve(8, 8) == 12988816);

    cout << solve(8, 8) << endl;
    return 0;
}

"""
Problem 843: Periodic Tilings

Count domino tilings of an m x n grid.
Methods: Transfer matrix DP, Kasteleyn formula, Fibonacci recurrence (m=2).
"""

from math import cos, pi, sqrt
from functools import lru_cache

# --- Method 1: Transfer matrix DP ---
def tilings_dp(m: int, n: int):
    """Count tilings via profile DP. Profile = bitmask of m bits."""
    if m * n % 2 == 1:
        return 0
    if m > n:
        m, n = n, m  # ensure m <= n for efficiency

    def fill_column(profile_in, profile_out, row, m):
        """Recursively fill one column given incoming profile."""
        if row == m:
            yield profile_out
            return
        if (profile_in >> row) & 1:
            # Cell already filled by horizontal domino from previous column
            yield from fill_column(profile_in, profile_out, row + 1, m)
        else:
            # Place horizontal domino (extends to next column)
            yield from fill_column(profile_in, profile_out | (1 << row), row + 1, m)
            # Place vertical domino (if next row available and not filled)
            if row + 1 < m and not ((profile_in >> (row + 1)) & 1):
                yield from fill_column(profile_in, profile_out, row + 2, m)

    # DP over columns
    dp = {0: 1}  # profile -> count
    for col in range(n):
        new_dp = {}
        for profile_in, count in dp.items():
            for profile_out in fill_column(profile_in, 0, 0, m):
                new_dp[profile_out] = new_dp.get(profile_out, 0) + count
        dp = new_dp

    return dp.get(0, 0)

# --- Method 2: Kasteleyn formula ---
def tilings_kasteleyn(m: int, n: int):
    """Kasteleyn's closed-form product formula."""
    if m * n % 2 == 1:
        return 0
    product = 1.0
    for j in range(1, m // 2 + 1 + (m % 2)):
        for k in range(1, n // 2 + 1 + (n % 2)):
            val = 4 * cos(pi * j / (m + 1))**2 + 4 * cos(pi * k / (n + 1))**2
            product *= val
    return round(product)

# --- Method 3: Fibonacci for m=2 ---
def tilings_fib(n: int):
    """T(2, n) = F_{n+1}."""
    if n == 0:
        return 1
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

# --- Verify ---
# m=2 cases
for n in range(1, 15):
    dp_val = tilings_dp(2, n)
    fib_val = tilings_fib(n)
    assert dp_val == fib_val, f"m=2, n={n}: DP={dp_val}, Fib={fib_val}"

# General cases
test_cases = [(2, 2, 2), (2, 3, 3), (2, 4, 5), (3, 4, 11), (4, 4, 36), (4, 6, 281)]
for m, n, expected in test_cases:
    dp_val = tilings_dp(m, n)
    assert dp_val == expected, f"T({m},{n}): got {dp_val}, expected {expected}"
    kast_val = tilings_kasteleyn(m, n)
    assert kast_val == expected, f"Kasteleyn T({m},{n}): got {kast_val}, expected {expected}"

print("All verification passed!")

answer = tilings_dp(8, 8)
print(f"T(8,8) = {answer}")