数学A / 場合の数

2×n をタイルで敷き詰める(フィボナッチ数)

実戦編数え上げ漸化式フィボナッチタイル張り単元横断

問題

$2 \times n$ のマス目を $1 \times 2$ のタイル(縦でも横でもよい)で隙間も重なりもなく敷き詰める方法の総数 $a_{n}$ を求めよ。

ヒントを見る

左端をどう埋めるかで場合分け。縦タイル1枚なら残りは $2 \times (n - 1)$ 、横タイル2枚(上下)なら残りは $2 \times (n - 2)$ 。 $a_{n}$ の漸化式は?

解答・解説

方針

一番左の列に注目。縦タイル1枚で埋めると残りは $2 \times (n - 1)$ 、横タイル2枚で埋めると残りは $2 \times (n - 2)$ 。これで漸化式が立つ。

解答

⓪ 発想 — どう考え始めるか。 敷き詰めの総数は、端がどう埋まるかで場合分けすると漸化式が立つ。

一番左の列の埋まり方は2通りしかない: 縦タイル1枚(残りは $2 \times (n - 1)$ )か、横タイル2枚を上下に重ねる(残りは $2 \times (n - 2)$ )。

よって $a_{n} = a_{n - 1} + a_{n - 2}$ — フィボナッチの漸化式だ。 $a_{1} = 1, a_{2} = 2$ から $a_{n} = F_{n + 1}$ 。

① 漸化式を立てる。 左端の埋め方で $a_{n} = 縦 1 枚 a_{n - 1} + 横 2 枚 a_{n - 2} .$

2×4 の敷き詰めの一例(縦1枚・横2枚・横2枚・縦1枚の順)。左端の埋め方で a_n=a_{n-1}+a_{n-2} が立つ。

② 初期値。 $a_{1} = 1$ ( $2 \times 1$ は縦タイル1枚のみ)、 $a_{2} = 2$ ( $2 \times 2$ は縦2枚または横2枚)。

重要

a_{n} = a_{n - 1} + a_{n - 2}

、

a_{1} = 1, a_{2} = 2

はフィボナッチ数列

1, 2, 3, 5, 8, \dots

で、

a_{n} = F_{n + 1}

(

F_{1} = F_{2} = 1

)

③ 結論。 よって $a_{n} = F_{n + 1}$ 。たとえば $a_{3} = 3, a_{4} = 5, a_{5} = 8$ 。

まとめ 「左端の埋め方」で場合分けすると、 $2 \times n$ の敷き詰めは $2 \times (n - 1)$ と $2 \times (n - 2)$ に帰着し、 $a_{n} = a_{n - 1} + a_{n - 2}$ 。フィボナッチ数 $F_{n + 1}$ が現れる。数え上げと漸化式の融合。

発展 — 一歩先へ。 盤を $3 \times n$ に広げると、答えは漸化式 $b_{n} = 4 b_{n - 2} - b_{n - 4}$ (奇数 $n$ では 0)という別の顔になり、 $2 \times n$ のフィボナッチがいかに特別に単純かが分かる。「端の埋まり方で分類 → 漸化式」という設計図自体は盤が変わっても通用する — 状態(端の欠け方)を増やして追いかける、動的計画法の入り口だ。

答

左端の詰め方で場合分けすると $a_{n} = a_{n - 1} + a_{n - 2}$ 、 $a_{1} = 1, a_{2} = 2$ 。よって $a_{n} = F_{n + 1}$ (フィボナッチ数)。

別解

「1段・2段の階段登り」と同一視する(対応で翻訳する)。 敷き詰めを左から読むと、各位置で「縦1枚( $1$ 列消費)」か「横2枚( $2$ 列消費)」のどちらかを選んでいる。

つまり敷き詰めは、 $n$ を $1$ と $2$ の順序つきの和に分解する方法(合成)と1対1対応する:

$n = 4 : 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2 ⟶ 5 通り$

これは「1段か2段ずつで $n$ 段の階段を登る方法」とまったく同じ問題 — 答えが同じフィボナッチ数になるのは当然だった。

漸化式(本解)は答えを計算する装置、対応づけは「見た目の違う問題が同じ構造だ」と見抜く目。数え上げでは、知っている問題への1対1対応が最強の解法になることが多い。

ポイント

一番左の列の埋め方(縦1枚 / 横2枚)で場合分け。
残りが $2 \times (n - 1)$ と $2 \times (n - 2)$ になり $a_{n} = a_{n - 1} + a_{n - 2}$ 。
$a_{1} = 1, a_{2} = 2$ よりフィボナッチ数 $a_{n} = F_{n + 1}$ 。

よくある間違い

左端の場合分けで「横タイル1枚だけ」の埋め方を数える(横1枚では上下どちらかが欠ける。横は必ず2枚セット)。
初期値を $a_{1} = 1, a_{2} = 2$ でなく $a_{0}$ の扱いで混乱する( $a_{0} = 1$ (何も置かない1通り)とすれば漸化式と整合)。
フィボナッチとの対応の添字( $a_{n} = F_{n + 1}$ )を1つずらす。