#029 カタラン数

問題

　10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないように握手する仕方は全部で何通りあるか？

イズミの解答への道

　パズル的に解くことで小学生が解くことができる問題だが、実は大学入試の整数問題にも出題されることのあるテーマが隠されている。そのような意味で高校生にもチャレンジしていただきたい。

解答

　k人（kは偶数）のとき、握手の仕方が a_k 通りあるとする。いま求めるのは a₁₀ である。
　いま、10人をそれぞれ1番から10番と名付ける。そして、1番がだれと手を握手をするかで分けて考える。

1番が2番と握手する場合、残り8人の手のつなぎ方を考えればよく、これは a₈ 通りである。これは、1番と10番が握手する場合も同じである。
1番が4番と握手する場合、2番は3番と手をつなぐしかなく、残り6人の手のつなぎ方を考えればよく、これは a₆ 通りである。1番と8番が握手する場合も同じである。
1番が6番と握手する場合、2番?5番のグループの4人、7番?10番のグループ4人の手のつなぎ方をそれぞれ考えればよく、これはどちらも a₄ 通りである。

　よって、求める値 a₁₀ は、
　　a₁₀ = 2a₈ + 2a₆ + ( a₄ )²
である。
　
　次に、 a₄ , a₆ , a₈ の値をそれぞれ求めよう。
　
　a₄ を求める。4人を1番から4番とすると、それは（1番と2番、3番と4番）または（1番と4番、2番と3番）の2通りだけである。よって、
　　a₄ = 2
である。
　
　a₆ を求めよう。6人を1番から6番とする。
　1番が2番と手を結ぶ場合は、残り4人の握手の仕方を考えればよく、それは a₄ 通りである。1番と6番が手を結ぶ場合も同じ。
　1番が4番と手を結ぶ場合は、2番は3番と、5番は6番と手を結ぶしかないので、結局
　　　a₆ = 2a₄ + 1 = 5
となる。
　
　a₈ を求めよう。8人を1番から8番とする。
　1番が2番または8番と握手する場合は、残り6人の握手の仕方を考えればよく、それは a₆ 通りである。
　1番が4番と握手する場合は、2番と3番の握手の仕方は決まるので、5番から8番の4人の握手の仕方を考えればよく、それは a₄ 通りである。1番と6番が握手する場合も同じである。よって、
　　a₈ = 2a₆ + 2a₄ = 14
となる。
　
　以上より、
　　a₁₀ = 2a₈ + 2a₆ + ( a₄ )²
　　　　= 2×14 + 2×5 + 22 = 42通り
である。

研究

カタラン数とは

　実は上で定義した a_k について、k = 2n としたものを改めて C_n と定義する（すなわち、C₁ = a₂ , C₂ = a₄ , … である）。このように定義した C_n を、カタラン数と呼ぶ。カタラン数は今見たように、
　　　1 , 2 , 5 , 14 , 42 , …
と続く。

　カタラン数を用いて表されるものの例として以下の様なものがある。

チケット売り場に 2n 人の人が並んでいます。このうち、 n 人は500円玉を持っており残りの n 人は1000円札しか持っていない。この売り場では1枚500円のチケットを売っており、はじめ売り場にはお金がない（つまり、おつりを用意していない）。このとき、おつりが不足することなく、全員にチケットを販売できる並び方は Cn 通り。
n組の ( ) を“正しく”並べる方法は Cn である。
たとえば、3組の ( ) を正しく並べる場合の数は、
　　　( ( ( ) ) ) , ( ) ( ( ) ) , ( ) ( ) ( ) , ( ( ) ) ( ) , ( ( ) ( ) )
の5通りで、 ( ) ) ( ) ) や ) ( ( ) ( ) といった形は ( ) を“正しく”並べていないため数えない。（上のチケットの問題と意味として同じ。）
2n 人が円になって手を交差させないで握手をする場合の数は Cn である（実は上の括弧の問題と同じように考えられる。握手相手は括弧でいうところの自分に対応する括弧である。互い違わないことは、手が交わらないことを示す）。
n×nの格子があるとき、対角線を跨がずに格子点を通って、向かい合った格子の左下から右上を最短距離でつなぐ道順の総数は C_n である（これも、考え直すとチケットや括弧の問題と同様である。）

などがある。また、カタラン数には、

$C_n = \frac{1}{n+1} {}_{2n} \text{C}_n = \frac{(2n)!}{(n+1)!n!}$