SRM363 Div1 250 (カタラン数)
問題
n人(nは偶数)が円になって手を交差させないで握手をする場合，何通り方法があるか．
考え方
メモ付き再帰した．
0番目の人と他の人が手をつないだ場合，交差させてはだめなので，繋ぐ時は偶数人ずつにわかれるように手をつながないといけない．なので2つに分けてそれぞれを再帰的に計算して両方のパターン数を掛け合わせればいい．
反省
これはまんまカタラン数だった．
カタラン数は，
- n組の「()」を正しく並べる組み合わせの数
- n本の内部ノードを持つ2分木に(n+1)の葉をつける方法の総数
- 縦横(n+1)本の正方形のグリッドを左下から右上に行くとき，対角線を超えないように移動する道の総数
- ２n人が円になって手を交差させないで握手をする場合の数はCn(まんまこれ)
噂のカタラン数は.
