n の式で表される順列
320
重要 例題17
文字がn個並んだものを「長さnの列」 と呼ぶとき
(1) 長さ3の列,長さ4の列はそれぞれ何通りあるか。
る列は何通りあるか。
(3) 長さnの列の個数をf(n)とするとき,f(n+2)=Df(n+1)+f(n) がゆ。
つことを示せ。
a
(津田塾大)
基本6
(2) 辞書式配列法 の利用も列が長くなると大変。そこで (3) との関連もあり, (1)の長さ。
の列と長さ4の列を利用することを考える。
① (1), (2) [, (3)]の問題 解法をまねる
ことも有効。(2)と同じようにして, nの場合
(一般の場合)を考える。
指針> (1) 辞書式配列法 を利用し, 条件を満たす列を書き上げる。
ba を追加
f(n)
$f(n+2)
aを追加
解答
(1) 長さ3の列は aaa, aab, aba, baa, bab
5通り
(辞書式配列で,条件に適す
るものを書き上げる。
したがって
長さ4の列は aaaa, aaab, aaba, abaa, abab,
baaa, baab, baba
わが連続するものを除く。
金
したがって
8通り
(2) aで始まる長さ5の列は, 長さ4の列の前にaを付ければ
よいから,(1)より
また, bで始まる長さ5の列は, 長さ3の列の前に baを付
ければよいから,(1)より
(3) 長さ(n+2)の列のうち,
aで始まる列は,長さ (n+1)の列の前にaを付けたもの,
bで始まる列は,長さnの列の前にba を付けたもの
である。
(aで始まる列は, aの次の
文字は a, bどちらでもよ
8通り
い。
くbで始まる列は, bの次の
文字は a。
(2)の一般化。
5通り
したがって
f(n+2)=f(n+1)+f(n)
和の法則
S@