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