カタラン数
なんかインドの雰囲気を感じる…と思ったけどベルギーの数学者、ウジェーヌ・カタランが由来らしい。
https://gyazo.com/2631edd61fdfcc346b4da00dfdc05843
この人
カタラン数はよく出てくる漸化式の解、ということにしてフィボナッチ数とかと同じ扱いにするのが良さそう。https://gyazo.com/a9c4e00061ac057362e2fe5a26503636
手書きでこういう風に求めることもできます。計算式的には
$ \large C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}こうなります。
$ {}_{2n} \mathrm{C} _nが$ n×nのマス目を端から端まで最短距離で行く組み合わせなのでそれをn+1(何故)で割る、というイメージ。