Count domino tiling in 4xn board
You have a 4 × n board. Count the number of distinct ways to tile it using 2 × 1 dominoes (rotation allowed).
Problem
Given an integer n >= 1, compute the number of different tilings of a 4 × n board using 2 × 1 dominoes. Dominoes may be placed horizontally or vertically; all tiles must fully cover the board without overlap.
Examples
Example 1
Input: n = 1
Output: 1
Explanation: Only a single vertical column of four vertical dominoes fits.
Example 2
Input: n = 2
Output: 5
Explanation: There are five tilings of a 4×2 board — all-vertical, and four patterns with two horizontal dominoes occupying one of the two rows (symmetries accounted for). Small enumeration:
1) All vertical dominoes (one per column)
2) Two horizontals covering top two cells and two verticals below
3) Two horizontals covering second row, verticals elsewhere
4) Two horizontals covering third row, verticals elsewhere
5) Two horizontals covering bottom row, verticals elsewhere
(Total = 5)
Example 3
Input: n = 4
Output: 36
Explanation: There are 36 distinct tilings of a 4×4 board with 2×1 dominoes.
Solution
We present a concise derivation of the standard linear recurrence for f(n) (the number of tilings) and two practical algorithms: a linear DP and a fast matrix-exponentiation method for large n.
Method 1 — Recurrence derivation (combinatorial decomposition)
Intuition
Look at how a tiling of the 4 × n board can begin at the leftmost columns. There are a fixed set of local starting patterns (eight canonical types). Group tilings by their starting pattern and relate f(n) to values f(k) for smaller k by removing covered columns; this yields a linear recurrence.
Approach (high level)
-
Let
f(n)be the number of tilings of a4 × nboard. Handle smallnby inspection:f(1) = 1,f(2) = 5,f(3) = 11,f(4) = 36.
-
Enumerate the distinct ways a valid tiling can occupy the leftmost 1–4 columns (these are the eight starting types A..H in the classical derivation).
-
Count contributions from each type and express
f(n)in terms off(n-1),f(n-2),f(n-3), andf(n-4). -
Simplifying the combinatorial bookkeeping gives the recurrence
f(n) = f(n-1) + 5*f(n-2) + f(n-3) - f(n-4)with base values listed above.
This recurrence is classical; a clear derivation follows by grouping types and using inclusion/exclusion on the dependent patterns (see references in source_links).
Code
Below are two practical ways to compute f(n): a straightforward DP (Method 2) and a fast method using matrix exponentiation (Method 3).
Method 2 — Dynamic programming (tabulation)
Intuition
Use the recurrence directly. Compute f(1..n) iteratively from the base cases.
Approach
- If
n <= 4return precomputed base values. - Allocate an array
fof lengthn+1and initialize base cases. - For
ifrom 5..ncomputef[i] = f[i-1] + 5*f[i-2] + f[i-3] - f[i-4](apply modulo if required). - Return
f[n].
Edge cases: n small (<=4) handled by base values. For very large n use Method 3.
Code
C++
class Solution {
public:
long long fillingBlocks(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 5;
if (n == 3) return 11;
if (n == 4) return 36;
const long long MOD = 1000000007LL;
std::vector<long long> f(n+1);
f[1]=1; f[2]=5; f[3]=11; f[4]=36;
for (int i=5;i<=n;++i) {
f[i] = (f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]) % MOD;
if (f[i] < 0) f[i] += MOD;
}
return f[n];
}
};
Go
package main
func fillingBlocks(n int) int64 {
if n <= 0 { return 0 }
if n == 1 { return 1 }
if n == 2 { return 5 }
if n == 3 { return 11 }
if n == 4 { return 36 }
const MOD int64 = 1000000007
f := make([]int64, n+1)
f[1], f[2], f[3], f[4] = 1, 5, 11, 36
for i := 5; i <= n; i++ {
v := f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]
v %= MOD
if v < 0 { v += MOD }
f[i] = v
}
return f[n]
}
Java
class Solution {
public long fillingBlocks(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 5;
if (n == 3) return 11;
if (n == 4) return 36;
final long MOD = 1_000_000_007L;
long[] f = new long[n+1];
f[1]=1; f[2]=5; f[3]=11; f[4]=36;
for (int i = 5; i <= n; ++i) {
long v = (f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]) % MOD;
if (v < 0) v += MOD;
f[i] = v;
}
return f[n];
}
}
Python
from typing import List
class Solution:
def filling_blocks(self, n: int) -> int:
if n <= 0: return 0
if n == 1: return 1
if n == 2: return 5
if n == 3: return 11
if n == 4: return 36
MOD = 10**9+7
f = [0] * (n+1)
f[1], f[2], f[3], f[4] = 1, 5, 11, 36
for i in range(5, n+1):
v = f[i-1] + 5*f[i-2] + f[i-3] - f[i-4]
v %= MOD
f[i] = v
return f[n]
Complexity
- ⏰ Time complexity:
O(n)— single loop computingf[i]from previous four values. - 🧺 Space complexity:
O(n)— the DP array; can be reduced toO(1)by keeping only the last four values.
Method 3 — Fast exponentiation via linear recurrence (matrix power)
Intuition
The recurrence is linear with constant coefficients of order 4. We can express the state vector S(i) = [f(i), f(i-1), f(i-2), f(i-3)]^T and a fixed 4×4 transition matrix M such that S(i+1) = M * S(i). Then S(n) = M^{n-4} * S(4) and we can compute M^{n} in O(log n) matrix multiplications.
Approach
- Build the 4×4 transition matrix
Mcorresponding to the recurrencef(i) = f(i-1) + 5f(i-2) + f(i-3) - f(i-4). - Use fast exponentiation to compute
M^{k}inO(log k)matrix multiplications (each multiplication isO(4^3)=O(1)constant work). - Multiply
M^{n-4}byS(4) = [f(4), f(3), f(2), f(1)]^Tto getf(n).
Code
C++
class Solution {
public:
using ll = long long;
const ll MOD = 1000000007LL;
vector<vector<ll>> mul(const vector<vector<ll>>& A, const vector<vector<ll>>& B) {
int m = 4;
vector<vector<ll>> C(m, vector<ll>(m));
for (int i = 0; i < m; ++i)
for (int k = 0; k < m; ++k)
for (int j = 0; j < m; ++j)
C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD;
return C;
}
vector<vector<ll>> mpow(vector<vector<ll>> base, long long e) {
int m = 4;
vector<vector<ll>> res(m, vector<ll>(m));
for (int i = 0; i < m; ++i) res[i][i] = 1;
while (e > 0) {
if (e & 1) res = mul(res, base);
base = mul(base, base);
e >>= 1;
}
return res;
}
long long fillingBlocksFast(long long n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 5;
if (n == 3) return 11;
if (n == 4) return 36;
vector<vector<ll>> M = {
{1,5,1,MOD-1},
{1,0,0,0},
{0,1,0,0},
{0,0,1,0}
};
auto P = mpow(M, n-4);
vector<ll> S4 = {36,11,5,1};
ll ans = 0;
for (int j = 0; j < 4; ++j) ans = (ans + P[0][j]*S4[j]) % MOD;
return ans;
}
};
Python (concise matrix power)
from typing import List
class Solution:
MOD = 10**9+7
def mat_mul(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
m = 4
C = [[0]*m for _ in range(m)]
for i in range(m):
for k in range(m):
for j in range(m):
C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % self.MOD
return C
def mat_pow(self, base: List[List[int]], e: int) -> List[List[int]]:
m = 4
res = [[0]*m for _ in range(m)]
for i in range(m): res[i][i] = 1
while e > 0:
if e & 1:
res = self.mat_mul(res, base)
base = self.mat_mul(base, base)
e >>= 1
return res
def filling_blocks_fast(self, n: int) -> int:
if n <= 0: return 0
if n == 1: return 1
if n == 2: return 5
if n == 3: return 11
if n == 4: return 36
M = [
[1,5,1,(self.MOD-1)],
[1,0,0,0],
[0,1,0,0],
[0,0,1,0]
]
P = self.mat_pow(M, n-4)
S4 = [36,11,5,1]
ans = 0
for j in range(4):
ans = (ans + P[0][j]*S4[j]) % self.MOD
return ans
Complexity
- ⏰ Time complexity:
O(log n)for the matrix-exponentiation method (each multiplication is constant-sized 4×4 work, exponentiation takesO(log n)steps). - 🧺 Space complexity:
O(1)(constant extra space for matrices) beyond input/output.