在M×N的地面上，用1×2的長方形進行覆蓋，能不能完全覆蓋？
基本介紹
- 中文名：組合鋪磚問題
在組合數學中，鋪磚問題可以通過求解遞推方程求解。
求用1×2的長方形覆蓋2×M的地面有幾種方式？
設用1×2的長方形覆蓋2×M的地面有
種方式，其中F為M的函式
我們知道第一塊長方形的放法，要么是豎著放，要么是橫著放。
當第一塊長方形豎著放的時候，問題轉換成求用1×2的長方形覆蓋剩下的2×(M-1)的方式，即
。
當第一塊長方形橫著放的時候，必有另一塊長方形放在其正下方，問題轉換成求用1×2的長方形覆蓋剩下的2×(M-2)的方式，即
。
在求和時，由於第一列地面的覆蓋方式已經不同，種覆蓋方式和中覆蓋方式沒有重疊，故
，其中，
。
