今回はカタラン数の話。


そもそもカタラン数とは何か?

定義は特にありませんが…、
○と×がN個ずつあったとして、これらを1列に並べたとき、
常に○の個数が×の個数以上となるように並べる並べ方の総数
と解釈しておくのがいいと思います。

これは次のような最短経路の道順として考えることができます。



このようにして求められる1、2、5、14、42、・・・をカタラン数といいます。
ちなみに、N番目の数は(2N)!/(N!(N+1)!)になります。



そして、このカタラン数、、さまざまな問題に現れる不思議な数列です。代表的なものを3つほど。


例題1

オオカミ3匹とヒツジ5匹を柵の中に1匹ずつ入れます。ヒツジの頭数がオオカミの頭数より多ければオオカミに襲われません。
ヒツジが襲われない入れ方は何通りありますか。


これは、さっきと同じ。



ヒツジが襲われない道を選んで進むと太線以外は通ることができないので、14通り




例題2

六角形を3本の対角線で4つの部分に分けるとき、分け方は何通りありますか。


まず、四角形を三角形2個に分ける分け方は、2通り・・・@
つぎに、五角形を三角形3個に分ける分け方は、@より、2+1+2=5通り・・・A
この繰り返しで、六角形を三角形4個に分ける分け方は、@Aより、5+2+2+5=14通り






例題3

5人でトーナメント戦を行います。各試合に引き分けはないものとして、優勝者が決まるまでの試合の総数は何通りありますか。


まず、少ない場合の4人の場合で考えてみたいと思います。
このとき、各トーナメント表は次のように書き改めることができます。

@→((AB)(CD)
A→(((AB)C)D)
B→((A(BC))D)
C→(A((BC)D))
D→(A(B(CD)))



つまり、4組の()()()()を並べる場合の数として考えればOK
ただし、「(()))(()」などは正しい並べ方ではないことに注意すると、
左から数えて常に「」の個数が「」の個数以上となる並べ方になるので、さっきと同じ。



だから、、問題の5人の場合は5×5マスの格子でやってあげると、42通り
[←戻る]