参考事項 カタラン数
an個, bn個の計2個を1列に並べるとき, a よりも多くの6が先に並ばない
ような並べ方の総数を カタラン数(*1) という。この数について考えてみよう。
例えば,n=1のときabの1通り; n=2のとき aabb, abab の2通り;
つまり, n番目のカタラン数を C とすると
n=3のとき aaabbb, aababb, aabbab, abaabb, abababの5通り
[図1]
C=1, C2=2,C3=5
しかし, n=4のとき,同じように列を書き出して調べるのは大変。
そこで,αを, b を ↑に対応させると, カタラン数は, [図1] のA
からBに行く最短経路の数と同じになる。(*2)
この数は, 前ページの検討でも説明したように, 各交差点を通過す
る経路の数 ([図1] の数字) を書き込むことによって, 求めることが
できる。 →図から14通り
2
55
12
13
A 111
[図2]
B'
... ①
1
I
また, 練習 30 の検討 (解答編 .265) のように考えてみると,
[図2] のような破線部分の経路があるものと仮定したとき, Aから
Bに行く最短経路は4個 14個の順列と考えて 8C4
更に, A から B' に行く最短経路は3個 15個の順列と考えて
8C3
②
ゆえに、 ①②から
*****
8C4-8C3-70-56=14
証明は省略するが, 同様に考えることにより, Cn=2Cn-2Cn-1 であ
ると推測できる。
ここで
(2n)!
(n-1)!{2n-(n-1)}!
(2n)!
2nCn-2nCn-1=
n!(2n-n)!
(2n)!{(n+1)-n} (2n)!
1
=
=
n!(n+1)!
n!(n+1)! n+1 n!n!
よって, カタラン数 C は次のように表される。
==
A
(2n)!
2n Con
=
n+1
123456
14 B
6
4
7
8
Cn=2nCn-2nCn-1=
2nCn
n+1
カタミンの
n
カタラン数
Cn
12 5 14 42 132429 1430
