返回题库

多米诺铺砖计数

How many ways are there to tile dominos

专题
Brainteaser / 脑筋急转弯
难度
L6

题目详情

用 2×12\times 1 的多米诺骨牌铺满一个 2×n2\times n 的棋盘，有多少种铺法？

铺满一个 3×2n3\times 2n 的棋盘，有多少种铺法？

英文原题

How many ways are there to tile dominos (with size 2×12\times 1 ) on a grid of 2×n2\times n ? How about on a grid of 3×2n3\times 2n ?

解析

(1) 2×n2\times n

设 fnf_n 为 2×n2\times n 的铺法数。

  • 若最左列竖放一块，则剩余 2×(n−1)2\times(n-1)：fn−1f_{n-1} 种；
  • 若最左两列横放两块，则剩余 2×(n−2)2\times(n-2)：fn−2f_{n-2} 种。

因此

fn=fn−1+fn−2,f0=1, f1=1,f_n=f_{n-1}+f_{n-2},\quad f_0=1,\ f_1=1,

所以 fn=Fn+1f_n=F_{n+1}（斐波那契数）。

(2) 3×2n3\times 2n

设 ana_n 为 3×2n3\times 2n 的铺法数。经典结果满足递推

an=4an−1−an−2,a0=1, a1=3.a_n=4a_{n-1}-a_{n-2},\quad a_0=1,\ a_1=3.

由此可依次算出 a2=11,a3=41,…a_2=11,a_3=41,\ldots。

英文解析

(1) 2×n2\times n

Let fnf_n be the number of ways to tile a 2×n2\times n rectangle.

  • If the leftmost column is covered by a vertical domino, the remaining area is 2×(n−1)2\times(n-1), giving fn−1f_{n-1}ways;
  • If the leftmost two columns are covered by two horizontal dominoes, the remaining area is 2×(n−2)2\times(n-2), giving fn−2f_{n-2}ways.

Therefore,

fn=fn−1+fn−2,f0=1, f1=1,f_n=f_{n-1}+f_{n-2},\quad f_0=1,\ f_1=1,

so fn=Fn+1f_n=F_{n+1} (the Fibonacci numbers).

(2) 3×2n3\times 2n

Let ana_n be the number of ways to tile a 3×2n3\times 2n rectangle. The classical result satisfies the recurrence

an=4an−1−an−2,a0=1, a1=3.a_n=4a_{n-1}-a_{n-2},\quad a_0=1,\ a_1=3.

From this, we can compute a2=11,a3=41,…a_2=11, a_3=41, \ldots sequentially.