以直向、横向、斜向磁砖铺满mn矩形的研究.PDFVIP

以直向 、橫 向 、斜 向磁磚鋪滿 × 矩形的研究 台北市立建國高級 中學 江誠敏 指導老師 沈朋裕 摘摘摘要要要 我們的主題是研究使用直 向 、橫 向與斜 向磁磚不交疊地鋪滿 × 的長方形的方法總 數 磁磚總共有如下圖中間所列 出的四種 （其 中著上藍色和綠色兩者統稱為 「斜 向的」 磁磚 ） 並且斜 向磁磚不能 有最右圖所顯示的交疊的情形 在 年的論文 中給 出了只使用直 向 、橫 向磁磚鋪滿 × 的長方形的方法數的 一個漂亮的公式 而 年的論文以一個較簡單的方法證明了這個結果 ( ) ∏ ∏ 而我們先從 固定 尋找遞迴式的方法 出發 接著用 的結果推 出 最後期望能找 出與論文一樣的一個漂亮的一般通式 研研研究究究簡簡簡介介介 研研研究究究動動動機機機 原本研究動機其實是從一個遊戲轉化而成了一個鋪磁磚的問題 一般我們都只使用直向與 橫 向兩種磁磚來鋪 但如果加上其他種類的磁磚 會發生甚麼事呢 這觸發了我們對於 以 下推廣問題的研究 如果除了使用直 向 、橫 向的磁磚 再加上 「斜 向的」磁磚來鋪滿一個 矩形 會與只使用直向 、橫 向的磁磚的鋪法有哪些方面的相同或相異 此次研究的內容 與矩陣 、遞迴數列相關 研研研究究究 目目目的的的 找 出鋪磁磚的方法數與矩形的長度 、寬度的關聯 研研研究究究內內內容容容轉轉轉移移移矩矩矩陣陣陣方方方法法法 符符符號號號說說說明明明 我們用 表示 × 的矩形區域 在討論鋪磁磚的過程 中 我們 由左至右依序鋪上磁磚 此時我們定義一個 「狀態」 當我 們 由左至右依序鋪上磁磚後 若恰好將前面 行完全鋪滿了 即 行上的所有格子 都被磁磚所覆蓋時 我們就稱 目前 行上的格子是否被磁磚填滿 的狀況為一個 「狀 態」 如上圖所示為撲滿第 行的情況 而此時的狀態如下圖所示 為了方便我們將給每種狀態一個標號的方式 對於一個狀態 我們從上到下如果格子已被 填滿則記為 否則為 這樣每一個狀態會對應到一個 字串 我們把這個 字串的值 當作狀態的編號 n m 如上圖為例 這個狀態對應到的 字串為 而後面會用字串的 進位值來排序 的的的遞遞遞迴迴迴關關關係係係 我們先計算 的遞迴關係 詳細的計算過程如下 注意到狀態 中如果 出現連續的 由於狀態的定義 不容許用直的磁磚排 因此我們可以 列 出如下的轉移矩陣