カタラン数　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る

　数学セミナー（２００９　８月号）の特集で、寺尾宏明氏（北大・理）がカタラン数のことを取
り上げておられる。２００６オープンキャンパスで高校生や一般の方を対象に話されたもの
ということで興味深く読ませていただいた。

　その中で、実は当HPで既に、「三角形分割」や「最短経路問題」で、「カタラン数」のことに
触れているということに気づかされた。

　何でも、「カタラン数」の解釈の仕方にはいろいろあって、２００９年４月３日現在、１７０通
りもあるそうである。

　「カタラン数」という名は、ベルギーの数学者 Ｅ．Ｃ．Ｃａｔａｌａｎ(1814～1894) の名に由来す
るという。

　ｎ 番目のカタラン数は、「Ｃｎ」と記される。

　カタラン数の解釈として、私的には「トーナメント（勝ち抜き戦）表の場合の数」が一番分か
りやすいような気がする。

例　題　　ｍ チームがトーナメント戦を行う。各試合に引き分けはないものとすると、

　優勝チームが決まるまで全部で ｍ－１ 試合が必要であることは自明だろう。

　それではその試合のやり方は何通りあるのだろうか。ただし、ｍ≧２ とする。

　いま、　Ｃｎ ： ｎ＋１ チームによるトーナメント表の場合の数　とする。

（イ）　ｍ＝２　のとき、

　　

で、１種類しかない。　このとき、　Ｃ1＝１　となる。

（ロ）　ｍ＝３　のとき、

　　　　　　　　

で、２種類しかない。　このとき、　Ｃ2＝２　となる。

（ハ）　ｍ＝４　のとき、

　 　 　 　

で、５種類しかない。　このとき、　Ｃ3＝５　となる。


　ところで、上図の（イ）（ロ）（ハ）を眺めていると、演算の結合法則が関係していそうな雰囲
気が漂ってくる！実のところ、カタランの当初の考え方と聞く。

　すなわち、（イ）の（１）は、「 ａ に ｂ を掛ける」とも理解される。（もちろん「足す」と考えてもよい。）

このことを、「（ａｂ）」　と書くことにすると、

（ロ）の（１）は、（（ａｂ）ｃ）　だし、　（ロ）の（２）は、（ａ（ｂｃ））　という意味になる。

また、（ハ）の（１）は、（（（ａｂ）ｃ）ｄ）　だし、（ハ）の（２）は、（（ａ（ｂｃ））ｄ）　となり、

（ハ）の（３）は、（（ａｂ）（ｃｄ））　で、（ハ）の（４）は、（ａ（（ｂｃ）ｄ））　となり、

（ハ）の（５）は、（ａ（ｂ（ｃｄ）））　であるものと解釈できる。

　この解釈は、さらに次のように考えると、道順の問題に翻訳される。

すなわち、「　（ａｂ）　」は、「 ａ に ｂ を掛ける」ということなので、「　ａｂ×　」と書くことにする。

このとき、　（（ａｂ）ｃ）　は、　ａｂ×ｃ×　、（ａ（ｂｃ））　は、　ａｂｃ××　と書ける。

また、（（（ａｂ）ｃ）ｄ）　は、　ａｂ×ｃ×ｄ×　、（（ａ（ｂｃ））ｄ）　は、　ａｂｃ××ｄ×　、

　（（ａｂ）（ｃｄ））　は、　ａｂ×ｃｄ××　、（ａ（（ｂｃ）ｄ））　は、　ａｂｃ×ｄ××　、

　（ａ（ｂ（ｃｄ）））　は、　ａｂｃｄ×××　と書ける。

　以下では、（ハ）の場合について、道順の場合の数との対応を考えよう。

　そこで、次のような３×３の格子状の道を準備する。

　

　点Ａを出発し、点Ｂに至る道を考える。ただし、

　ａｂ×ｃ×ｄ×などの順列の２番目以降において、

　文字（ｂ、ｃ、ｄ）ならば、「－」（横に移動）、　掛け算「×」ならば、「｜」（縦に移動）

するものとする。このとき、

ａｂ×ｃ×ｄ× ａｂｃ××ｄ× ａｂ×ｃｄ××
　
ａｂｃ×ｄ×× ａｂｃｄ×××


　　　　上記の道順の方法は、ちょうど左図のような街路の最短

　　　経路の場合の数に等しい。

　　　　その場合の数は、「最短経路問題」によれば、

　　　　　　4Ｃ2－１＝５（通り）

　　　で、上記の結果と一致する。

　一般に、ｎ＋１ チームによるトーナメント表を考え、それを道順の問題に翻訳すると、下図
の街路の点Ａから点Ｂまでの最短経路の場合の数が、カタラン数　Ｃｎ　となる。

　


　このとき、下図のような補助の街路を考えることにより、Ｃｎ が求められる。

　　　左図より、

　　　Ｃｎ＝2ｎ-2Ｃｎ-1－2ｎ-2Ｃｎ-3

　　で、上式の右辺をさらに計算すると、

　　２（２ｎ－１）！/｛（ｎ＋１）！（ｎ－１）！｝

　　すなわち、
　　　　　　　　　

　　という公式が得られる。

　この公式により、カタラン数を全て求めることが出来る。

ｎ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ ・・・
Ｃｎ １ ２ ５ １４ ４２ １３２ ４２９ １４３０ ４８６２ １６７９６ ・・・

　ところで、カタラン数と組合せの式の関係と言えば、巷間では、

　

が広く知れ渡っているようである。これは、下図のような補助街路を用いて、最短経路を求
めることにより得られる。

　　　左図より、

　　　Ｃｎ＝2ｎＣｎ－2ｎＣｎ-1

　で、何れも、
　　　　　　　　　

　となるので等しいのは当然だが、素朴

　な疑問で、どちらの方が覚えやすいの

　かな？

　上記では、最短経路問題として、　Ｃｎ＝2ｎＣｎ－2ｎＣｎ-1　を導いたが、別な視点で、こ
の公式の意味づけを考えてみよう。

例　５００円硬貨を持つ人が ｎ 人、千円札を持つ人が ｎ 人の計 ２ｎ 人が一列に並ぶ。
　　各自より、５００円を集金するとき、集金する人がおつりを用意しなくても済むような並び
　　方は何通りあるか。

　この問題で、例えば、ｎ＝３　とし、５００円硬貨を持つ人を○、千円札を持つ人を●で表し、
実際に並び方を書いてみよう。

　まず、おつりのことを考えずに、並び方の全てを書きだしてみると、

○○○●●● ○○●○●● ○○●●○● ○○●●●○ ○●○○●●
○●○●○● ○●○●●○ ○●●○○● ○●●○●○ ○●●●○○
●○○○●● ●○○●○● ●○○●●○ ●○●○○● ●○●○●○
●○●●○○ ●●○○○● ●●○○●○ ●●○●○○ ●●●○○○

の　6Ｃ3＝２０ 通りある。このうち、おつりを用意せずに済む並び方は、次の５通りである。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（上記の表の内の青色部分）

○○○●●● ○○●○●● ○○●●○● ○●○○●● ○●○●○●

　問題は、おつりが不足する場合の数の数え方である。次の１５通りが該当する。

○○●●●○ ○●○●●○ ○●●○○● ○●●○●○ ○●●●○○
●○○○●● ●○○●○● ●○○●●○ ●○●○○● ●○●○●○
●○●●○○ ●●○○○● ●●○○●○ ●●○●○○ ●●●○○○

　上記の１５通りの内、おつり不足が最初に発生する位置は、それぞれ赤色の部分である。

この場合の数を数えるために、●までの○と●を入れかえる。

　この操作により、●の直前までは、○と●は同数なので、必ず、○が１個増え、●が１個
減る。

●●○○○○ ●○●○○○ ●○○○○● ●○○○●○ ●○○●○○
○○○○●● ○○○●○● ○○○●●○ ○○●○○● ○○●○●○
○○●●○○ ○●○○○● ○●○○●○ ○●○●○○ ○●●○○○

　このとき、上記の場合の数は、○４個と●２個の順列の総数に等しいので、

6Ｃ2＝１５ 通りである。

　よって、求める場合の数は、　6Ｃ3－6Ｃ2＝５　（通り）　である。

　上記の考え方を一般化すると、

　まず、５００円硬貨を持つ人が ｎ 人、千円札を持つ人が ｎ 人の計 ２ｎ 人が一列に並ぶ

場合の数は、　2ｎＣｎ　通りある。このとき、あるところでおつり不足が発生する場合の数は、

５００円硬貨を持つ人が ｎ＋１ 人、千円札を持つ人が ｎ－１ 人の計 ２ｎ 人が一列に並ぶ

場合の数に等しいので、　2ｎＣｎ-1　通りある。

　よって、求める場合の数は、　2ｎＣｎ－2ｎＣｎ-1　通りある。

（コメント）　背景に最短経路問題を意識したので、ちょっとスッキリしないような意味づけで
　　　　　　した。読者の方で、「これは！」という意味づけをお持ちの方は是非ご教示下さい。


　平成２１年８月１１日付けで、ＨＮ「凡人」さんよりカタラン数の漸化式の話題をいただいた。

　トーナメント戦の考え方において、次のように考えると、カタラン数についての漸化式が得
られる。

　「ｎ＋１ チームによるトーナメント戦の決勝の相手は、

　ｎ チームによるトーナメント戦の優勝チームと、残り １ チーム

　ｎ－１ チームによるトーナメント戦の優勝チームと、
　　残り ２ チームによるトーナメント戦の優勝チーム

　ｎ－２ チームによるトーナメント戦の優勝チームと、
　　残り ３ チームによるトーナメント戦の優勝チーム

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　２ チームによるトーナメント戦の優勝チームと、
　　残り ｎ－１ チームによるトーナメント戦の優勝チーム

　１ チームと、残り ｎ チームによるトーナメント戦の優勝チーム

の各場合が考えられるので、 Ｃ0＝１　として、

　Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1

が成り立つ。


（コメント）　凡人さん、ありがとうございます。とても分かりやすい導き方ですね！でも、この
　　　　　　漸化式を解くことは可能なのでしょうか？解はもう分かっているので、漸化式とい
　　　　　　うよりも、一つの性質ととらえておけばいいのかな？

　カタラン数 Ｃｎ はまた、凸 （ｎ＋２）角形の三角形分割の個数としてもとらえられる。

　次のように考えればよい。（　→　参考：「三角形分割」）

　左辺以外の辺に時計回りに、ａ、ｂ、ｃ、・・・　と文字を割り当て、三角形の第３の辺に、他
の２辺の積を割り当てる。

例　三角形の場合

　　　　この場合、　Ｃ1＝１　となる。

例　四角形の場合

　　　　　　　

となり、演算結果　（（ａｂ）ｃ）　、（ａ（ｂｃ））　と三角形分割の方法とが関連づけられる。

　この場合、　Ｃ2＝２　となる。

　「三角形分割」において、次のことを示した。

　凸 ｎ 角形（ ｎ≧３ ）において、三角形分割の方法の数が、Ｆ(ｎ) 通りあるものとする。

明らかに、Ｆ(３)＝１　である。　いま、ｎ≧４　とする。 ３＜ｋ＜ｎ　において、凸 ｎ 角形は、

３つの部分に分割される。

　　Ｆ(ｎ) の定義より、

　Ｆ(ｎ) ＝１・Ｆ(ｎ－１)＋Ｆ(３)・Ｆ(ｎ－２)＋・・・

　　　　　＋ Ｆ(ｋ－１)・Ｆ(ｎ－ｋ＋２) ＋・・・

　　　　　＋ Ｆ(ｎ－２)・Ｆ(３) ＋Ｆ(ｎ－１)・１

　　が成り立つ。

　この公式を用いて、カタラン数 Ｃｎ を計算してみよう。

　Ｃ1＝Ｆ(３)＝１

　Ｃ2＝Ｆ(４)＝１・Ｆ(３)＋Ｆ(３)・１＝２

　Ｃ3＝Ｆ(５)＝１・Ｆ(４)＋Ｆ(３)・Ｆ(３)＋Ｆ(４)・１＝２＋１＋２＝５

　Ｃ4＝Ｆ(６)＝１・Ｆ(５)＋Ｆ(３)・Ｆ(４)＋ Ｆ(４)・Ｆ(３) ＋Ｆ(５)・１＝５＋２＋２＋５＝１４

　　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　ここで、　Ｃ0＝１　とすれば、例えば、Ｃ4 は、

　Ｃ4＝Ｃ0・Ｃ3＋Ｃ1・Ｃ2＋ Ｃ2・Ｃ1 ＋Ｃ3・Ｃ0

と書き直せるように、一般のカタラン数 Ｃｎ に関する漸化式

　Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1

の成り立つことが、Ｆ(ｎ) に関する漸化式より分かる。

　「三角形分割」において、Ｆ(ｎ) に関する漸化式の一般項

　

を求めることができた。　Ｃｎ ＝ Ｆ(ｎ＋２)　という関係から、Ｃｎ の一般項

　

が直ちに得られる。この式と最短経路の問題で得られた Ｃｎ の式

　

は、当然同じ値になる。（すなわち、　2ｎＣｎ-1＝2ｎＣｎ+1 より明らか！）


（コメント）　上記の話で、ＨＮ「凡人」さんの疑問に答えられたでしょうか．．．？


　平成２１年８月１７日付けで、「凡人」さんがカタラン数の漸化式の解釈に取り組まれた。
（一部文言等を修正させていただきました！）

　

より、Ｆ(ｎ＋２)＝2ｎＣｎ-1/ｎ＝Ｃｎ

一方、Ｆ(ｎ＋３)＝2ｎ+2Ｃｎ/（ｎ＋１）　なので、

　Ｆ(ｎ＋３)/Ｆ(ｎ＋２)＝ｎ・2ｎ+2Ｃｎ/｛（ｎ＋１）・2ｎＣｎ-1｝＝２（２ｎ＋１）/（ｎ＋２）

よって、　Ｃｎ ＝ Ｆ(ｎ＋２)　より、

　（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ

が成り立つ。この式は、三角形分割の個数 Ｆ(ｎ) から得られたが、最初から、

　（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ

という漸化式が導けないかというのが「凡人」さんの意図するところであろう。

例　４・Ｃ3＝１０・Ｃ2　の解釈を考えてみよう。

　Ｃ2＝２　は、次の２通りであった。

　　　　　　　　

　このうちの１通り、例えば、

　

に、新しい１チームを加えるために新しい試合を追加する方法を考える。

　　　　　　　　　　

　 　　　　　　

　上記の通り、１０通りある。同様にして、

　

に、新しい１チームを加えるために新しい試合を追加する方法を考えると、

　　　　　　　　　　

　 　　　　　　

で、これも１０通りある。これらを、Ｃ3＝５　の場合

　　　　　　　　

と比較すると、上記の２０通りの中には、４通りずつ同じものが出現していることが分かる。
（トーナメント表の番号が同じものは、同じトーナメント表！）

　以上から、漸化式　４・Ｃ3＝１０・Ｃ2　の成り立つことが分かる。

　上記のことを一般化して、「凡人」さんは軽妙に次のように考えられた。

　１．（ｎ＋１）チームによるトーナメント表の縦線の本数は「試合数×２＋１」本であるが、試
　　合数は、ｎ　であるので、２ｎ＋１（本）の縦線がある。
　　　このトーナメント表に新たに １チームを加えるには、２ｎ＋１（本）の縦線のうちの １ 本
　　から横に線を出して張り出しのような形で １ チーム分の試合を追加する。

　２．横線は左右どちらにも出す事ができて、それらは区別されるので、計 ２（２ｎ＋１）通り
　　の増やし方がある。

　３．（ｎ＋１）チームでの全てのトーナメント表で同じことを行うと、２（２ｎ＋１）・Ｃｎ 通りにな
　　る。

　４．ところで、（ｎ＋２）チームのトーナメント表で、新しく加えられた １ チームの入る場所を
　　区別して考えると、（ｎ＋２）・Ｃｎ+1 通りのトーナメント表が得られる。

　５．上述の ３．と４．のトーナメント表の数は一致するので、漸化式

　　　（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ

　　が得られる。


（コメント）　「凡人」さんの非凡さに感動しました！　このような経験をさせていただいた「凡
　　　　　　人」さんに感謝します。この考え方をすれば、何も三角形分割を持ち出すことなく、
　　　　　　漸化式が作れますね。

　漸化式　（ｎ＋２）・Ｃｎ+1＝２（２ｎ＋１）・Ｃｎ　より、

　　（ｎ＋１）・Ｃｎ＝２（２ｎ－１）・Ｃｎ-1

　　　ｎ・Ｃｎ-1＝２（２ｎ－３）・Ｃｎ-2

　　（ｎ－１）・Ｃｎ-2＝２（２ｎ－５）・Ｃｎ-3

　　　　・・・・・・・・・・・・・・・・・・・・・

　　４・Ｃ3＝１０・Ｃ2

　　３・Ｃ2＝６・Ｃ1

これらを辺々かけて、

　（ｎ＋１）！・Ｃｎ/２＝２ｎ－1・（２ｎ－１）！/｛２ｎ－1・（ｎ－１）！｝＝（２ｎ－１）！/（ｎ－１）！

よって、Ｃｎ＝２（２ｎ－１）！/｛（ｎ＋１）！（ｎ－１）！｝

　すなわち、

　

が得られる。


　上記で、三角形分割と演算の順番の関係を見たが、円周上の互いに交差しない弦の引
き方にも関係することを以下に見てみよう。

　円周上に ２ｎ 個の点があるものとする。

例　ｎ＝１　のとき

　　　これは、　（ａｂ）　に相当し、括弧のつけ方に注目すれば、

　　　　　　　　　　　　　　　（　）

　　で、その場合の数は、カタラン数 Ｃ1＝１　と一致する。

例　ｎ＝２　のとき

　　　　　

　これらは、ａ を省いて考えると、　（ｂ（ｃｄ））　や　（（ｂｃ）ｄ）　となり、３文字 Ａ、Ｂ、Ｃ　の場

合の演算の結合の仕方：　（Ａ（ＢＣ））　や　（（ＡＢ）Ｃ）　の場合の数に一致するので、カタラ

ン数 Ｃ2＝２　となる。

例　ｎ＝３　のとき

　　　　　　　

　　　　

　これらは、ａ を省いて考えると、

　（ｂ（ｃｄ）（ｅｆ））　、（ｂ（ｃ（ｄｅ）ｆ））　、（（ｂｃ）ｄ（ｅｆ））　、　（（ｂ（ｃｄ）ｅ）ｆ）　、　（（ｂｃ）（ｄｅ）ｆ）

となり、さらに、ｂ を省いて、括弧のつけ方を考慮すると、４文字 Ａ、Ｂ、Ｃ、Ｄ　の場合の演

算の結合の仕方

（（ＡＢ）（ＣＤ））　、（（Ａ（ＢＣ））Ｄ）　、（Ａ（Ｂ（ＣＤ）））　、（（（ＡＢ）Ｃ）Ｄ）　、（Ａ（（ＢＣ）Ｄ））

の場合にそれぞれ対応するので、カタラン数 Ｃ3＝５　と一致する。

　これらのことを一般化して、次の事実が成り立つ。

　円周上の ２ｎ 個の点を互いに交差しない弦で結ぶ方法の数は、カタラン数 Ｃｎ

（証明）
 　　　円周上の ２ｎ 個の点を互いに交差しない弦で結ぶ方
　　法の数を Ｆ（ｎ）とおく。

　　　点 １ と点 ｋ を結ぶ弦で、円周上の ２ｎ 個の点を２つ
　　のグループに分ける。点 ｋ は、点 １ と同じグループに
　　入るものとする。

　　　このとき、題意より、ｋ の値が奇数になることはない。

　　ｋ＝２、４、６、・・・、２ｎ－２、２ｎ　と場合分けして考える。

ｋ＝２　のとき、　　円周上 ２ｎ－２ 個の点を互いに交差しない弦で結ぶ方法の数は、
　Ｆ（ｎ－１）通りで、その１通りに対して、残りの２点の弦の引き方は、１通り。

　よって、この場合の数は、　１・Ｆ（ｎ－１）　通り

ｋ＝４　のとき、　　円周上 ２ｎ－４ 個の点を互いに交差しない弦で結ぶ方法の数は、
　Ｆ（ｎ－２）通りで、その１通りに対して、点 １ と点 ４ を除いた残りの２点の弦の引き方は、
Ｆ（１）通り。

　よって、この場合の数は、　Ｆ（１）・Ｆ（ｎ－２）　通り

　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

ｋ＝２ｎ－２　のとき、　　点 １ と点 ２ｎ－２ を除いた残りの２点の弦の引き方は、Ｆ（１）通り
　で、その１通りに対して、円周上 ２ｎ－４ 個の点を互いに交差しない弦で結ぶ方法の数は、
Ｆ（ｎ－２）通り。

　よって、この場合の数は、　Ｆ（ｎ－２）・Ｆ（１）　通り。

ｋ＝２ｎ　のとき、　　　　点 １ と点 ２ｎ の弦の引き方は、１通りで、その１通りに対して、円
　周上、２ｎ－２ 個の点を互いに交差しない弦で結ぶ方法の数は、Ｆ（ｎ－１）通り。

　よって、この場合の数は、　Ｆ（ｎ－１）・１　通り

　以上から、求める場合の数 Ｆ（ｎ）は、

　Ｆ(ｎ) ＝１・Ｆ(ｎ－１)＋Ｆ(１)・Ｆ(ｎ－２)＋・・・＋ Ｆ(ｎ－２)・Ｆ(１) ＋Ｆ(ｎ－１)・１

となる。これは、カタラン数 Ｃｎ の漸化式

　Ｃｎ＝１・Ｃｎ-1＋Ｃ1・Ｃｎ-2・＋・・・＋Ｃ1・Ｃｎ-2・＋Ｃｎ-1・Ｃ0

に一致するので、Ｆ（ｎ）は、カタラン数 Ｃｎ に一致する。　（証終）


　当ＨＰがいつもお世話になっているＳ（Ｈ）さんが、平成２１年３月２１日付けで、数学的帰納
法の練習問題として、次のような問題を提起された。

集金問題　　ある劇場の入場料は、５千円とする。５千円札しかもっていない ｎ(≧ １)人と、
　　　　　　　１万円札しかもっていない ｎ 人の合計 ２ｎ 人が劇場前の広場で勝手に円形の
　　　　　　　輪を作って開場を待っているとする。

　このとき、劇場の入口の受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不
足することがないようにできることを示せ。

（この集金問題が必ず可能であることは、カタラン数 Ｃｎ≧１　から明らかだろう。
→　参考：「集金問題」）

命題　Ｐ ： 全ての自然数 ｎ に対して、劇場の入口の受付人は、ある適当な人から時計回
　りに集金すれば、釣り銭に不足することがないようにできる

（証明）　数学的帰納法による。

ｎ＝１　のとき、　５千円札しかもっていない人と、１万円札しかもっていない人の合計 ２人
　が劇場前の広場で待っているので、５千円札しかもっていない人から、５千円札を受け取り、
　次に、１万円札しかもっていない人から１万円札を受け取り、５千円札を渡せばよい。
　よって、ｎ＝１　のとき成り立つ。

ｎ＝ｋ（ｋ≧１）のとき、命題 Ｐ が成り立つと仮定する。

　すなわち、５千円札しかもっていない ｋ(≧ １)人と、１万円札しかもっていない ｋ 人の合計
　２ｋ 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、劇場の入口の受付
　人は、ある適当な人から時計回りに集金すれば、釣り銭に不足することがないようにできる。

　今、５千円札しかもっていない ｋ＋１人と１万円札しかもっていない ｋ＋１人の合計２ｋ＋２
　人が劇場前の広場で勝手に円形の輪を作って開場を待っているものとする。

　この中には、５千円札しかもっていない人がいて、しかも、時計回りで隣の人が、１万円札
　しかもっていない人である組合わせが必ず存在する。

　この２人を除くと、残りは、５千円札しかもっていない ｋ(≧ １)人と、１万円札しかもっていな
　い ｋ 人の合計 ２ｋ 人が劇場前の広場で勝手に円形の輪を作って開場を待っていて、劇場
　の入口の受付人は、ある適当な人から時計回りに集金すれば、釣り銭に不足することがな
　いようにできる。途中で、最初に見つけた２人からは、５千円札しかもっていない人から、５
　千円札を受け取り、次に、１万円札しかもっていない人から１万円札を受け取り、５千円札
　を渡せばよい。

　よって、　ｎ＝ｋ＋１　のときも、命題 Ｐ は成り立つ。

　　以上から、全ての自然数 ｎ に対して、劇場の入口の受付人は、ある適当な人から時計
　回りに集金すれば、釣り銭に不足することがないようにできることが示された。　（証終）

　さて、次は、カタラン数の生成関数の話題に移ろう。

　カタラン数については、上記の計算で、

ｎ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ ・・・
Ｃｎ １ ２ ５ １４ ４２ １３２ ４２９ １４３０ ４８６２ １６７９６ ・・・

であることを見た。そこでは、カタラン数そのものは、バラバラな感じであったが、これら全て
のカタラン数を係数とする１つの多項式を考え、カタラン数の持つ性質を追究しようというの
が、生成関数の考え方である。

　生成関数には、カタラン数に関する情報が全て含まれると言っても過言ではないだろう。

　カタラン数 Ｃｎ の生成関数とは、　Ｃ0＝１　として、

　Ｆ（ｘ）＝Ｃ0＋Ｃ1・ｘ＋Ｃ2・ｘ2＋Ｃ3・ｘ3＋・・・＋Ｃｎ・ｘｎ＋・・・

と書けるものを言う。

　具体的には、　　Ｆ（ｘ）＝１＋ｘ＋２ｘ2＋５ｘ3＋１４ｘ4＋・・・　という多項式である。

ここで、　Ｃｎ＝Ｃｎ-1・Ｃ0＋Ｃｎ-2・Ｃ1＋Ｃｎ-3・Ｃ2＋・・・＋Ｃ0・Ｃｎ-1　から、

　Ｆ（ｘ）2＝Ｃ02＋（Ｃ1・Ｃ0＋Ｃ0・Ｃ1）ｘ＋（Ｃ2・Ｃ0＋Ｃ1・Ｃ1＋Ｃ0・Ｃ2）ｘ2＋・・・

　＝Ｃ1＋Ｃ2ｘ＋Ｃ3ｘ2＋・・・

なので、　１＋ｘ・Ｆ（ｘ）2＝Ｃ0＋Ｃ1・ｘ＋Ｃ2・ｘ2＋Ｃ3・ｘ3＋・・・＝Ｆ（ｘ）　であると言える。

　すなわち、　Ｆ（ｘ）は、等式　ｘ・Ｆ（ｘ）2－Ｆ（ｘ）＋１＝０　を満たす。

これを、Ｆ（ｘ）に関する２次方程式と考えれば、その解は、

　

となるが、Ｆ（０）＝１　なので、

　

と書ける。これが、カタラン数 Ｃｎ の生成関数となる。

ここで、Ｔａｙｌｏｒ 展開のことを考えれば、Ｃｎ＝Ｆ(ｎ)（０）/ｎ！　が成り立つ。

例
　

なので、　Ｆ’（０）＝１　より、　Ｃ1＝Ｆ’（０）/１！＝１　となる。


　２項定理というと、（ａ＋ｂ）ｎ の展開公式だが、実は、ｎ の値は自然数に限らず任意の実
数においても成り立つことが知られている。
（　→　参考「超越数を手計算で求める」における二項級数の項）

　を二項級数に展開して、ｘｎ+1 の項を求めると、

　

となる。したがって、

　

を二項級数に展開したときの ｘｎ の項は、

　

となる。よって、カタラン数 Ｃｎ の値は、

　

すなわち、

　

となる。


（追記）　平成２５年５月１８日付け

　私の代数学の恩師　土井先生が勤められていた立命館大学の文学部・産業社会学部
Ａ方式（２０１３年）でカタラン数を題材とする問題が出題された。

　

【図１】
【図２】

　上図で東西、南北それぞれ６本の線分は道であるが、対角線ＡＢは道ではないとする。

（１）　【図１】において、ＡからＥを通ってＢへ行く最短経路は何通りあるか。（１０５通り）
　　（２）　左図は、（１）の経路において、ＥからＢへ行く経路

　　　　を、図の点線を軸に対称移動させたものであり、Ｂは

　　　　Ｃに移る。この図において、ＡからＥを通ってＣへ行く

　　　　最短経路は何通りあるか。（１０５通り）

（３）　【図２】において、対角線ＡＢより南側を通らないで、ＡからＢへ行く最短経路は何通り

　　あるかを考える。

　（イ）　（２）の図のような考え方を用いて、ＡからＢへ行く最短経路のうち、対角線ＡＢより

　　南側を通る最短経路は何通りあるか。（２１０通り）

　（ロ）　対角線ＡＢより南側を通らないで、ＡからＢへ行く最短経路は何通りあるか。（４２通り）

（４）　東西、南北それぞれｎ＋１本の線分を道とし、対角線ＡＢは道ではないとする。このとき、

　　対角線ＡＢより南側を通らないで、ＡからＢへ行く最短経路は何通りあるか。

　　（（２ｎ）！/（ｎ！（ｎ＋１）！）通り）


（コメント）　上記では、紙面の都合で説明を大幅に省略してあるが、実際の本文では、経路
　　　　　　を数える手順が図を用いて丁寧に導かれている。ただ、説明が長すぎて、受験生
　　　　　　が試験時間内に対応できたかはちょっと不明．．．。

　（４）はまさに、カタラン数 Ｃｎ である。


（追記）　「カタラン数から派生した疑問」と題して、当ＨＰがいつもお世話になっているＨＮ
　　　　「ｍｏｏｎｌｉｇｈｔ」さんからご投稿いただきました。（令和４年１月１５日付け）

　先日ネタが切れて、そういえばと、「カタラン数」知らんかもと紹介を兼ねて、こんな問題を
投げてみました。

　下図のように円周上に10個の点があり、10個の点を2点ずつの組にして線分で結ぶ。
但し、線分は交差しないものとする。全部で、何通りの結び方があるか。

　　

　ごく平凡なカタラン数の問題なのですが、その後で、ついつい、「10個の点は等間隔だから
回したり裏返して同じパターンになるものが沢山あるよなぁ」と...。

　そこで、「回転させたり裏返したりして同じ結び方になる（見える）ものは1通りと数えると全
部で何通りあるか」と訊いてみようとして... えっと、どう説明できるか... と思い止まってしまし
ました。若い頃なら勢いで訊いていたところでしょう。歳をとってしまいました。

　で、何通りあるかはどのように考えれば要領が良いでしょうか。もちろん点の数が、2nの
場合であれば、とても有難いのですが... （いつも質問ばかりで申し訳ない）。


　らすかるさんからのコメントです。（令和４年１月１５日付け）

　回答ではないのですが、もしかして、「A006082」の数列ですか？違ったらごめんなさい。
# 要領のよい数え方は今のところわかっていません。


　ｍｏｏｎｌｉｇｈｔ さんからのコメントです。（令和４年１月１５日付け）

　どうでしょうか。ちょっと眺めただけではよく分かりません。集中力が欠けてきたのかも...。
Rubyでプログラムを書いて、確認してみました。10項までは合致したので、同じものかもしれ
ません。


　らすかるさんからのコメントです。（令和４年１月１６日付け）

　私も確認しました。手作業では、「1，2，3，6，12，27」までで音を上げてしまったので、特定
できませんでしたが、プログラムを作って、次の「65」まで確認すると、「1，2，3，6，12，27，65」
を含む数列は、この一つしかないですね。

　ということで、やはりこの数列で正しそうです。
（プログラムでは490まで確認しました）

　このページに非常に複雑な計算式がありますが、もし要領よく数えられるとしたら、その要
領に従って計算式ももう少し簡単になっても良さそうなものですので、要領よく数えるうまい
方法はなさそうな気がします。


（コメント）　ｍｏｎｌｉｇｈｔ さんの問題設定は、「カタラン数」の問題設定と微妙に違うんですね！
　　　　　　回転や裏返しで重なるものは同一視するというのは、「カタラン数」の計算にはない
　　　　　　設定です。

　らすかるさんが手作業で「1，2，3，6，12，27」までを確認された由、私もらすかるさんに倣っ
て挑戦しようと思い立ちましたが、ｎ＝５までで心が折れ力尽きました。大変な計算ですね。

ｎ＝１のとき、　１通り

　　　

ｎ＝２のとき、　１通り

　　　

ｎ＝３のとき、　２通り

　　　　　　　

ｎ＝４のとき、　３通り

　　　　　　　　　　　　

ｎ＝５のとき、　６通り

　　　　　　　　　　　　

　　　　　　　　　　　


　ＧＡＩ さんからのコメントです。（令和４年１月１８日付け）

　 # 要領のよい数え方は今のところわかっていません。

　サイト「A006082」でのリングを頼りにプログラム化（PARI/GP)したら、

gp > p(n)=binomial(2*n,n)/(n+1)+sumdiv(n,d,eulerphi(n/d)*binomial(2*d,d))
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　-binomial(2*n,n)+n*binomial(n,floor(n/2))
gp > q(n)=binomial(2*n,n)/(n+1)+binomial(n+1,(n+1)/2)
　　　　　+sumdiv(n,d,eulerphi(n/d)*binomial(2*d,d))-binomial(2*n,n)+n*binomial(n,floor(n/2))

と組んで、nの奇遇に分けて使い分けるといいようです。

gp > for(n=1,30,if(n%2==0,print1(p(n)/(4*n)","),print1(q(n)/(4*n)",")))

1,1,2,3,6,12,27,65,175,490,1473,4588,14782,48678,163414,555885,1913334,6646728,23278989,
82100014,291361744,1039758962,3729276257,13437206032,48620868106,
176611864312,643834562075,2354902813742,8640039835974,31791594259244,

　一方、「A006082」(ただし、n=1,2,3,･･･)

1, 1, 2, 3, 6, 12, 27, 65, 175, 490, 1473, 4588, 14782, 48678, 163414, 555885, 1913334,
6646728, 23278989, 82100014,291361744, 1039758962, 3729276257, 13437206032,
48620868106, 176611864312, 643834562075, 2354902813742, 8640039835974,
31791594259244


　らすかるさんからのコメントです。（令和４年１月１８日付け）

　プログラムの高速化をあれこれ考えているうちに、「要領のよい数え方」がわかってきまし
た。

　結ぶ点を A、B、C、…　として、最短：(A,B) (AとBを結ぶという意味)・・・これを「1」とします。

AとDを結ぶ場合は、BとCを結ぶ必要があります。

つまり、(A,D)(B,C)・・・このAとDのように、３つ離れた点を結ぶものを「2」とします。

AとFを結ぶ場合は、B～Eは、(A,F)(B,E)(C,D)　または、(A,F)(B,C)(D,E)　の２通りがあります。
・・・このAとFのように、5つ離れた点を結ぶものを「3」とします。

　点が10個のとき、最も離れていて「3」です。

　「1」「2」「3」で足して5になる順列を考えます。ただし、回転は同一視しますので、3+2と2+3
は同じです。

　3+2：「3」が2通り、「2」が1通りなので2×1=2通り

　3+1+1：同様に、2通り

　ただし、3+2と3+1+1で一つ重複が発生（このように対角を結ぶ場合は重複に注意が必要）

　2+2+1：1×1×1=1通り

　2+1+1+1：同様に1通り

　1+1+1+1+1：同様に1通り

　従って、n=10 の場合は、2+2-1+1+1+1=6（通り）　となります。

　n=12の場合は、合計6を考えます。

　3+3：一つ目の「3」と二つ目の「3」で異なるパターンにする場合が重複しますので、
　　2×2-1=3通りです。

　3+2+1：2×1×1=2通り

　3+1+1+1：2×1×1×1=2通り

　2+2+2：1×1×1=1通り

　2+2+1+1：1通り

　2+1+2+1：1通り

　2+1+1+1+1：1通り

　1+1+1+1+1+1：1通り　　　以上、合計12通り

　ｎが14以上になると、「4」が必要になりますが、「4」は非対称の形が出現しますので少し
面倒になります。


　ｍｏｏｎｌｉｇｈｔ さんからのコメントです。（令和４年１月１８日付け）

　らすかるさんの、このアイデアは面白いです。なるほど！そう数える手があったかと。


　当ＨＰ読者のＨＮ「Copyソル」さんからのコメントです。（令和５年６月２日付け）

　Ｃｎ をｎ番目のカタラン数としたとき、

　Ｃｎ＝Σ[k=1,floor((n+1)/2)] (-1)^(k-1)*Ｃｎ-k*n+1-kＣk
　　　　(floor(x)は床関数で、nＣk は二項係数)

の等号が成立することを、証明することは可能でしょうか？

　一応、コンピュータで、ｎ＝100 まで成り立つことは検証済みです。偶然、上記の成立しそう
な関係を見つけたのですが、証明する手立ても実力もなく、軽く調べた限り、このような総和
で記した文献が見当たらなかったため、質問した次第です。（→　参照：「Catalan Number」）


（コメント）　いくつか試算してみた。 Ｃ1=１、Ｃ2＝２、Ｃ3＝５、・・・　に注意して、

　Ｃ2＝Ｃ1・2Ｃ1＝１・２＝２　、Ｃ3＝Ｃ2・3Ｃ1－Ｃ1・2Ｃ2＝２・３－１・１＝６－１＝５　、・・・

　なるほど．．．！


　ＧＡＩ さんからのコメントです。（令和５年６月２日付け）

　カタラン数Ｃｎの再帰的漸化式として、(ただし、Ｃ0＝１ とする)

Ｃｎ＝∑[k=0,n-1] Ｃk*Ｃｎ-1-k

Ｃｎ＝∑[k=0,n-1] n-1Ｃ2k*2^(n-1-2*k)*Ｃk

Ｃｎ＝∑[k=1,floor((n+1)/2)] (-1)^(k-1)*Ｃｎ-k*n+1-kＣk

などがあるようです。（→　参考：「A000108」のFORMULAの部分）

（→　第３式の at さんによる証明）


　DD++ さんからのコメントです。（令和５年６月３日付け）

　「A000108」に掲載されているということは正しいということなんでしょうけど、OEIS には証明
までは載っていませんね。

　カタラン数が関係するなら組み合わせで証明したいところですが、(-1)^k が入った式で、そ
れやるの、難しいんですよねえ。

　式の意味を無視して式変形でやるなら、カタラン数も二項係数も階乗に直す方針になるん
でしょうか？まだやってみていませんけど．．．。


　ＧＡＩ さんからのコメントです。（令和５年６月６日付け）

　カタラン数C(n)に関して、一般には、n×n の格子路に対して、(0,0)から(n,n)までを(0,0)､(n,n)
を結ぶ対角線より上方へははみ出さない部分で行ける経路の数を与えるものと紹介される例
をよく見る。

　そこで、正方形の格子路を改め、n×mでの長方形の格子路を考え、x 軸方向へは、ｎ、y
軸方向へは、ｍとし、(0,0)、(n,m)を結ぶ対角線を引き、この直線より上方へは立ち入らずに
(0,0)から格子点を通過しながら(n,m)地点に辿り着けるカタラン路が何通りあるかを考えるこ
とにする。

　この求めたい総数を、C(n,m) と記して、式を構成しようと頑張ってみたのだが、意外とｎに
よって構造が異なってしまうので、まだ、一つの式で表すものに辿り着けていません。

　どなたか、関心を寄せられましたら是非、C(3,m)とC(4,m)に対して、どんな式（もしくはプロ
グラムで算出できるコード等）を発見されるのか、お示し願えれば有難いです。


　らすかるさんからのコメントです。（令和５年６月６日付け）

　私の解釈が間違っていなければ、

　C(3,m)は、m=0～100に対して、

1,1,2,5,5,7,12,12,15,22,22,26,35,35,40,51,51,57,70,70,77,92,92,100,117,117,126,145,145,155,176,
176,187,210,210,222,247,247,260,287,287,301,330,330,345,376,376,392,425,425,442,477,477,
495,532,532,551,590,590,610,651,651,672,715,715,737,782,782,805,852,852,876,925,925,950,
1001,1001,1027,1080,1080,1107,1162,1162,1190,1247,1247,1276,1335,1335,1365,1426,1426,
1457,1520,1520,1552,1617,1617,1650,1717,1717

　C(4,m)は、m=0～100に対して、

1,1,3,5,14,14,23,30,55,55,76,91,140,140,178,204,285,285,345,385,506,506,593,650,819,819,938,
1015,1240,1240,1396,1496,1785,1785,1983,2109,2470,2470,2715,2870,3311,3311,3608,3795,
4324,4324,4678,4900,5525,5525,5941,6201,6930,6930,7413,7714,8555,8555,9110,9455,10416,
10416,11048,11440,12529,12529,13243,13685,14910,14910,15711,16206,17575,17575,18468,
19019,20540,20540,21530,22140,23821,23821,24913,25585,27434,27434,28633,29370,31395,
31395,32706,33511,35720,35720,37148,38024,40425,40425,41975,42925,45526

のようになり、この値から式を作ると、

　C(3,m)=[(m+3)/3]^2+[(m+1)/3][(m+4)/3]/2

　C(4,m)=[(m+4)/4](4[(m+4)/4]^2-1)/3+[(m+1)/4][(m+5)/4]^2/2+[(m+2)/4][(m+6)/4](5[(m+2)/4]+1)/6

という式で表されそうです。


　ＧＡＩ さんからのコメントです。（令和５年６月６日付け）

　自分では、この求めるべき経路数を一つずつ作図しながら求めていたものですから、mが
100までのデータは考えられもしませんでした。

　nが3の時の数の並びの変化の状態から、k=m\3 (mを3で割ったときの商をk)、L=3*k+1
として置けば、通常の3×mの格子路での全経路数S=(3+m)!/(3!*m!)に対する比率が、m%3
の値に依存していることが起こりそうだと思われた。

　つまり、

m%3==0 ==>C(3,m)=S/L
m%3==1 ==>C(3,m)=S/(L+3)
m%3==2 ==>C(3,m)=S/(L+4)

　これに従い、プログラムを組んで並べて行き、m=20　位までぐらいを確認していました。
（なにせ手作業で図を描いてやっと経路数を見つけていたものですから）

　これで上手く行きそうだと思ってしまったので、n=4も、k=m\4 (mを4で割ったときの商をk)
L=4*k+1　として置けば、通常の4×mの格子路での全経路数S=(4+m)!/(4!*m!)に対する比
率がm%4の値に依存していることが起こりそうだと思われた。

　つまり、

m%4==0 ==>C(4,m)=S/L
m%4==1 ==>C(4,m)=S/(L+4)
m%4==2 ==>C(4,m)=S/(L+5)
m%4==3 ==>C(4,m)=S/(L+6)

　ところがどっこい、実際に起こる経路数が、m%4==2　の場合、分数の値を返してきて反映
してくれない。

　何とかSの値は利用したかったので、実際に起こる経路数と一致させるための調整が

　m%4==2 ==>C(4,m)=(S-k*(k+1)*(4*k+5)/6)/(L+4)

へ辿り着きました。

　Sから除くパターンの部分が、なぜか「A016061」に繋がっているのが不思議でした。

　これを元にプログラムを組んで、やはり m=20 辺り位までしか確認していませんでした。
それでらすかるさんの値と比較し、m=98==2(mod 4)　でも一致できていたので安心しました。

　しかしこれを一つの式で表せられるなんて思ってもいませんでした。感じとしては、nが素数
である時は、例の規則で行けそうですが、nが合成数になると、途端に厄介になりそうです。

　今、n=6に挑戦していますが、図を描いて正解数を求めるしか手がないので、らすかるさん、
前もってその配列数をm=100までを教えて貰えませんか？


　らすかるさんからのコメントです。（令和５年６月６日付け）

　C(6,m) なら、m=0～100 に対して、

1,1,4,12,23,42,132,132,227,377,525,728,1428,1428,2010,2803,3504,4389,7084,7084,9097,11654,
13793,16380,23751,23751,28931,35246,40356,46376,62832,62832,73950,87143,97584,109668,
141778,141778,162883,187453,206591,228459,285384,285384,322046,364124,396510,433160,
527085,527085,586638,654240,705789,763686,910252,910252,1002037,1105317,1183487,
1270752,1489488,1489488,1625096,1776599,1890570,2017169,2331924,2331924,2525439,
2740354,2901207,3079140,3518515,3518515,3786757,4083170,4304066,4547556,5145336,
5145336,5508104,5907251,6203610,6529292,7324878,7324878,7805193,8331713,8721393,
9148503,10187344,10187344,10811692,11493880,11997356,12547920,13881945,13881945,
14680520,15550580,16191123

のようになると思います。

（追記）　Ｗｅｂサイト：「道順の場合の数を求めるテクニック」の「書き込み方式」に従って、
　　　　プログラミングすると簡単ですよ。

　対角線を越える点をカウントしないようにするだけですから、

・(幅+1)×(長さ以上)の配列を作る(幅は3,4,6など、100まで出すなら「長さ以上」は101以上)
・配列全体を0にして(0,0)要素だけ1にする
・y=0～(長さ)まで以下の処理を行う
・x=0～(幅)まで以下の処理を行う（ただしy=0のときのみx=1から）
・(長さ)×x＞(幅)×yのときxのループを抜ける（対角線を越える格子点）
・配列の(x-1,y)要素と(x,y-1)要素の和を(x,y)要素の値とする（ただしx-1やy-1が負のとき0）

　これで最終的に(幅,長さ)要素に格納された値が答えです。


　ＧＡＩ さんからのコメントです。（令和５年６月６日付け）

　ヒントをもらったので、PARIのソフトで挑戦してみました。配列がmatrixの道具しかなく、成分
は[1,1]から取ってあるので、微妙に取り方をずらしながら組んでみました。

F(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M

　これより

gp > F(6,10)
%813 =
[1 0 0 0 0 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0 0 0 0]
[1 2 2 2 0 0 0 0 0 0 0]
[1 3 5 7 7 7 0 0 0 0 0]
[1 4 9 16 23 30 30 0 0 0 0]
[1 5 14 30 53 83 113 113 113 0 0]
[1 6 20 50 103 186 299 412 525 525 525]

gp > F(6,18)
%818 =
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 2 3 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0]
[1 3 6 10 14 18 22 22 22 22 0 0 0 0 0 0 0 0 0]
[1 4 10 20 34 52 74 96 118 140 140 140 140 0 0 0 0 0 0]
[1 5 15 35 69 121 195 291 409 549 689 829 969 969 969 969 0 0 0]
[1 6 21 56 125 246 441 732 1141 1690 2379 3208 4177 5146 6115 7084 7084 7084 7084]

　あの手作業が夢のようです。

　また、nが素数の場合は予想が当たるか確認してみた。n=7でやってみると、

F7(m)={k=m\7;L=7*k+1;S=(7+m)!/(m!*7!);}\
if(m%7==0,print(m";"S/L),m%7==1,print(m";"S/(L+7)),\
m%7==2,print(m";"S/(L+8)),m%7==3,print(m";"S/(L+9)),\
m%7==4,print(m";"S/(L+10)),m%7==5,print(m";"S/(L+11)),\
m%7==6,print(m";"S/(L+12)))

と組んで走らせると、

gp > for(m=1,50,F7(m))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890		 　 21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117		 　  41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

　一方、

G(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M[n+1,m+1]

から、

gp > for(m=1,50,print(m";"G(7,m)))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890		 　 21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117		 　  41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

　予想大当たり！！！

　しかし、n=6の場合は、S=(6+m)!/(6!*m!)　の数値から導くのは困難でした。
（未だに解決できずです。）


　ａｔ さんが、

　Ｃｎ＝∑[k=1,floor((n+1)/2)] (-1)^(k-1)*Ｃｎ-k*n+1-kＣk

の証明に取り組まれました。（令和５年６月７日付け）

　∑[k=0,floor((n+1)/2)] (-1)^(k-1)*Ｃｎ-k*n+1-kＣk=0

を示せばよいですね。

　t の関数 f(t) をべき級数展開したときの t^n の係数を [t^n]f(t) と書くことにします。

Σ[k=0,floor((n+1)/2)] (-1)^(k-1)*Ｃｎ-k*n+1-kＣk
=Σ[p=n-floor((n+1)/2),n] (-1)^(n-p-1)*Cp*p+1Ｃn-p
=Σ[p=0,∞] (-1)^(n-p-1)*Cp*p+1Ｃn-p
=Σ[p=0,∞] (-1)^(n-p-1)*Cp*[t^n]( (1+t)*(t*(1+t))^p)
=(-1)^(n-1)*[t^n]( (1+t)*Σ[p=0,∞] Cp*(-t*(1+t))^p)
=(-1)^(n-1)*[t^n]( (1+t)*(1-sqrt(1-4*(-t*(1+t))))/(2*(-t*(1+t))) )
=(-1)^(n-1)*[t^n]( (1-sqrt((1+2*t)^2))/(2*(-t)) )
=(-1)^(n-1)*[t^n](1)
=(-1)^(n-1)*0
=0.


　DD++ さんからのコメントです。（令和５年６月７日付け）

　なるほど、カタラン数は母関数で扱う方針がありましたか。


（コメント）　素晴らしいです！ａｔ さんに感謝します。DD++ さんには証明を若干修正していた
　　　　　　だきました。DD++ さんに感謝します。


　ａｔ さんからのコメントです。（令和５年６月８日付け）

　DD++ さん、ご指摘ありがとうございます。Σ[p=ceil((n-1)/2)～n] と書かなければいけない
ところを、間違って、Σ[p=floor((n-1)/2)～n]　と書いてしまっていましたね。失礼しました。



　　　以下、工事中