131027 初版 131027 更新
問題
50円の飲み物の自動販売機がある。
販売機は50円玉と100円玉しか受け付けない。
50円玉を持っている人が5人、100円玉だけ持っている人が5人いる。
この10人全員が飲み物を１つずつ購入するにはどのように並べばよいか。
ただし、先頭の人が購入するときに販売機にはつり銭はない。
また、50円玉を持っている人はa, 100円玉を持っている人はb として、
50円玉を持っている人どうしの順番は無視するものとする。
100円玉を持っている人どうしも同様である。
50円玉を持っている人を 1, 100円玉しかない人を 0 で表すと
例えば、
1101010010, 1010101001, 1011011000 などがある。
level 5 のカタラン数は
\(\dfrac{8!}{4!\cdot 4!}\) の 70 より小さかった。
ここにある、
8C4 の数表を使う。
t3 の列は 3人目が購入した後の販売機の中にある50円玉の個数を表している。
t1 から t10 の列で 負の数が出てきたときにはカタラン型ではない