320
00000
重要 例題 17 nの式で表される順列
文字 aとbをいくつか並べた列のうちで、6が隣り合わないものだけを考える。
文字がn個並んだものを 「長さnの列」 と呼ぶとき
(1) 長さ3の列, 長さ4の列はそれぞれ何通りあるか。
(2) 長さ5の列で,a で始まる列は何通りあるか。また、長さ5の列で, b で始ま
る列は何通りあるか。
(3) 長さnの列の個数をf(n) とするとき, f(n+2)=f(n+1)+f(n)が成り立
[津田塾大]
つことを示せ。
基本6
指針 (1) 辞書式配列法を利用し、 条件を満たす列を書き上げる。
(2) 辞書式配列法の利用も列が長くなると大変。そこで (3) との関連もあり、(1) の長さ3
の列と長さ4の列を利用することを考える。
+3+04
(3)
(23)の問題 解法をまねる
ことも有効。 (2) と同じようにして, nの場合
(一般の場合) を考える。
解答
(1) 長さ3の列はaaa, aab, aba, baa, bab
したがって
5通り
長さ4の列は
f(n)
f(n+1)
baaa, baab, baba
したがって
8通り
(2) α で始まる長さ5の列は, 長さ4の列の前にαを付ければ
よいから, (1) より
8通り
また で始まる長さ5の列は,長さ3の列の前に ba を付
ければよいから (1) より
5通り
である。
したがって
(3) 長さ (+2) の列のうち,
αで始まる列は, 長さ (n+1) の列の前に αを付けたもの
で始まる列は,長さnの列の前に ba を付けたもの
f(n+2)=f(n+1)+f(n)
練習
17
bα を追加
αを追加
J*3
aaab, aaba, abaa, ababbが連続するものを除く。
aaaa,
-
辞書式配列で、条件に適す
るものを書き上げる。
⇒f(n+2)
1-5
αで始まる列は,αの次の
文字は α bどちらでもよ
い。
文字はα
(2)の一般化。
で始まる列は、あの本の
01
先頭車両から順に1からnまでの番号の付いたn両編成の列車がある。ただし、
n≧2 とする。 各車両を赤色, 青色,黄色のいずれか1色で塗るとき, 隣り合った
