『カタラン数のレポート』解答

◆水の流れさんからいただいたレポートです

問題　＜釣り銭と最短経路＞ 私のクラスの生徒は教材費に五百円払う必要があります。 そこで、五百円玉しか持っていないｎ人の生徒と、千円札しか持っていないｎ人の合計２ｎ人の生徒がいます。 担任の私は釣り銭を準備していませんでした。 釣り銭が不足しないように生徒からもらう方法は全部で何通りありますか。 ただし、生徒の２ｎ人に区別しないで、お金の出し方で考えてください。

コメント　日常的な出来事ですので、興味があります。

解説
　五百円玉を払うのをＡ，千円札を払うのをＢとします。
釣り銭がないので、常にＡの数がＢの数より等しいか多ければよいのです。
まず、ｎ＝１，２，３，のとき、数えてみます。

ｎ＝１のとき、ＡＢの１通り。
ｎ＝２のとき、ＡＡＢＢ，ＡＢＡＢの２通り。
ｎ＝３のとき、
　ＡＡＡＢＢＢ，ＡＡＢＡＢＢ，ＡＡＢＢＡＢ，
　ＡＢＡＡＢＢ，ＡＢＡＢＡＢの５通り。
ここで、考え方を変えてみます。

これをＡを→、Ｂを↑と表せば、→がｎ個、↑がｎ個の同じものを一列に並べる方法と考えます。
だから、基盤の目をした最短経路の問題に変化していきます。

分かり易くするために、求める数をＫ(n)とすると、
Ｋ(１)＝１，Ｋ(２)＝２，Ｋ(３)＝５は図を書いて、分かるとします。
＜参考：このＫ(n)をカタラン数と言います。＞

ｎ＝４のときを描きます。
図のような△ＡＢＣの最短経路の道筋がＫ(４)になります。

Ｋ(４) を求めるのに、

1. Ｂ１を通るとき、ＡＧからＧＢ１を通り、△Ｂ１ＤＢの最短経路Ｋ(３)の道筋。
2. Ｂ１を通らず、Ｂ２を通るとき、△ＧＨＬの最短経路Ｋ(１)から、道路ＬＢ２を通り、△Ｂ２ＥＢの最短経路Ｋ(２)の道筋。
3. Ｂ１，Ｂ２を通らず、Ｂ３を通るとき、△ＧＩＭの最短経路Ｋ(２)から、道路ＭＢ３を通り、△Ｂ３ＦＢの最短経路Ｋ(１)の道筋。
4. 最後に、Ｂ１，Ｂ２，Ｂ３を通らず、Ｂに行く場合は△ＧＣＦの最短経路Ｋ(３)に等しい。

よって、
　Ｋ(４)
＝ Ｋ(３)＋Ｋ(１)Ｋ(２)＋Ｋ(２)Ｋ(１)＋Ｋ(３)
＝ ５＋１×２＋２×１＋５＝１４　になります。

＜副産物＞

これは、一般にＫ(０)＝１と決めておけば、

Ｋ(n)＝Ｋ(0)Ｋ(n−1)＋Ｋ(1)Ｋ(n−2)＋Ｋ(2)Ｋ(n−3)＋・・・＋Ｋ(n−1)Ｋ(0)　

また、こんな数え方（書き込み方式）もできます。
ｎ＝５を求めます。

さらに、斜めの線に関しての対称性に気がつけば、
Ｋ(４)＝１×１＋３×３＋２×２＝１４
Ｋ(５)＝１×１＋４×４＋５×５＝４２
Ｋ(６)＝１×１＋５×５＋９×９＋５×５＝１３２、・・・・・・

したがって、カタラン数Ｋ(ｎ)は何個かの平方数の和として表せます。

さて、本題に入ります。ｎ＝４で描きます。
不適な経路を太線で書いてあります。

四角形ＤＡＣＢの最短経路の道筋は、組合せの記号を使えば、
_８Ｃ_４＝８！÷(４！４！)＝７０通りあります。

ここから、対角線ＡＢと交わる経路が不適ですから、この不適な経路の数を求めます。
例えば、図の太線の経路は不適ですが、これを直線Ｔ１Ｔ４について対称移動します。
ただし、直線Ｔ１Ｔ４に始めて出会った点から後の部分のみを対称に曲げて図の太線を考えると、すべての不適な経路は四角形ＡＥＦＧの最短経路の数に等しくなります。

これは、
　_８Ｃ_３
＝８！÷(３！５！)
＝５６　通りとなり、
そこで、△ＡＢＣの最短経路の方法Ｋ(４)は、

　Ｋ(４)
＝_８Ｃ_４−_８Ｃ_３
＝７０−５
＝１４　として得る。

したがって、釣り銭のいらないもらい方Ｋ(n)は、
　Ｋ(n)
＝_２ｎＣ_ｎ−_２ｎＣ_ｎ−１
＝_２ｎＣ_ｎ÷(ｎ＋１) ・・・(答え）

研究　カタランの問題の原典

いくつかの数の積は、２つずつの数の積の計算を繰り返して行っている。
だから、どの２つずつの積を作っていく方法の数はどうなるかという問題(カタランの問題)が、1838年にカタランによって論じられた。
ｎ個の数の順序が変わらない積の総数をＣ(ｎ)とし、ｎ個の数の順序を変えても良い積の総数をＲ(ｎ)とする。　
具体例をｎ＝１，２，３，４で見ます。

1. ｎ＝１のとき、Ｃ(１)＝１、Ｒ(１)＝１と考えておく。

2. ｎ＝２のとき、数をａ，ｂと書くと、積は　ａｂ，ｂａ　の２通りで、Ｃ(２)＝１、Ｒ(２)＝２　となる。

3. ｎ＝３のとき、数をａ，ｂ，ｃと書くと、積は
   　（ａｂ）ｃ，ａ（ｂｃ），（ａｃ）ｂ，
   　ａ（ｃｂ），（ｂａ）ｃ，ｂ（ａｃ），
   　（ｂｃ）ａ，ｂ（ｃａ），（ｃａ）ｂ，
   　ｃ（ａｂ），（ｃｂ）ａ，ｃ（ｂａ）
   　１２通りで、Ｃ(３)＝２、Ｒ(３)＝１２　だとわかる。

4. ｎ＝４のとき、数をａ，ｂ，ｃ，ｄと書くと、数の順序がａ，ｂ，ｃ，ｄとなる積は
   　（（ａｂ）ｃ）ｄ，（ａｂ）（ｃｄ），
   　（ａ（ｂｃ））ｄ，ａ（（ｂｃ）ｄ），
   　ａ（ｂ（ｃｄ））の５通りなので、
   Ｃ(４)＝５、Ｒ(４)＝Ｃ(４)×(４！)＝５×２４＝１２０。

＊参考：ｎ≧２のとき、次の性質があります。

1. Ｒ(ｎ＋１)＝(４ｎ−２)Ｒ(ｎ)
2. Ｒ(ｎ)＝２・６・10・14・・・(４ｎ−６)
3. Ｃ(ｎ)＝ Ｒ(ｎ)／ｎ！
4. Ｃ(ｎ＋１)＝{(４ｎ−２)／(ｎ＋１)}Ｃ(ｎ)
5. Ｋ(ｎ＋１)＝{(４ｎ＋２)／(ｎ＋２)}Ｋ(ｎ)
   　　　　　・・・（漸化式の発見）

さらに、1751年にオイラーは、ゴルトバッハへ次のような問題を手紙に書いている。
「平面上で、凸ｎ角形を対角線によって３角形に分割する方法の数Ｅ(ｎ)はどうなるでしょう。
ただし、互いに交わらない対角線のみを使用するものとする。」

具体例でｎ＝３，４，５、・・・を考えます。

1. ｎ＝３のとき、Ｅ(３)＝１と都合によって考えます。
2. ｎ＝４のとき、Ｅ(４)＝２は自明
3. ｎ＝５のとき、Ｅ(５)＝５は図を書いてみます。

＊注： Ｅ(ｎ)＝Ｃ(ｎ−１)＝Ｋ(ｎ−２)の関係となる。

参考：1758年にセニェールが発見した漸化式

 Ｅ(ｎ)＝Ｅ(2)Ｅ(n−1)＋Ｅ(3)Ｅ(n−2)＋Ｅ(4)Ｅ(n−3)・・・＋Ｅ(n−1)Ｅ(2)

なぜ、日常生活のこれらの現象が１つの数列として、見なされるか不思議です。

＜追加記述＞

　カタラン数について、下記のような漸化式が成り立つことから、母関数を利用して、一般項 Ｋ(n)をｎを用いて表してみよう。

＜副産物＞ これは、一般にＫ(０)＝１と決めておけば、 Ｋ(n)＝Ｋ(0)Ｋ(n−1)＋Ｋ(1)Ｋ(n−2)＋Ｋ(2)Ｋ(n−3)＋・・・＋Ｋ(n−1)Ｋ(0) という、漸化式が成り立ちます。

数列 Ｋ(0)，Ｋ(1)，Ｋ(2)，Ｋ(3),・・・,Ｋ(n−1) ,Ｋ(n) の母関数を

ｙ＝Ｋ(0)＋Ｋ(1)ｘ＋Ｋ(2)ｘ2＋Ｋ(3)ｘ3＋・・・＋Ｋ(n−1)ｘn-1＋Ｋ(n)ｘn　

ｙ2＝Ｋ(0)Ｋ(0)+{Ｋ(0)Ｋ(1)+Ｋ(1)Ｋ(0)}ｘ+・・+{Ｋ(0)Ｋ(n−1)+Ｋ(1)Ｋ(n−2)+Ｋ(2)Ｋ(n−3)+・・+Ｋ(n−1)Ｋ(0)}ｘn-1+・・　

ｙ2＝Ｋ(1)＋Ｋ(2)ｘ＋Ｋ(3)ｘ2＋Ｋ(4)ｘ3＋・・・＋Ｋ(n)ｘn-1＋ ・・・　

ゆえに、
　ｘｙ²＝ｙ−Ｋ(0) ，
　ｘｙ²−ｙ＋１＝０

これを，ｙについて解の公式から導いて、
ｙ＝(１±(１−４ｘ)^1/2 )÷２ｘ

複号はｘ＝０のとき、ｙ＝１となるように複号を決める。
ただし、分母を払って、２ｘｙ＝１±(１−４ｘ)^1/2の式に代入すること。

したがって、求める母関数は
ｙ＝{１−(１−４ｘ)^1/2}÷２ｘ である。

これを展開した級数のｘⁿ の係数がカタラン数Ｋ(n)である。
さて、(１−４ｘ)^1/2　のｘⁿ 係数をＬ(n) とおくと、
Ｌ(0)＝１で、ｎ≧１のときのＬ(n)は２項定理により、

　Ｌ(n)
＝1/2・(1/2−１)・・・(1/2−ｎ＋１)(−４)ⁿ ／ｎ！
＝(−１)(−３)・・・(３−２ｎ)／２ⁿ ×(−４)ⁿ ／ｎ！
＝１・３・・・・(２ｎ−３)／ｎ！×(−１)^2n-1×２ⁿ
　　 (ｎ≧１)

分子に２，４，・・・，(２ｎ−２)を補って(２ｎ−２)！をつくれば、
　Ｌ(n)
＝−２(２ｎ−２)！／ (ｎ−1)！ｎ！
＝−２／ｎＣ(2n-2,n-1)・・・・・・(1)

＜＊Ｃ(2n-2,n-1)は組み合わせの記号です。＞

よって、

(１−４ｘ)1/2＝１＋ Ｌ(1)ｘ＋Ｌ(2)ｘ2＋・・・＋Ｌ(n＋1)ｘn+1＋・・・　

ｙ＝{−Ｌ(1)ｘ−Ｌ(2)ｘ2−・・・−Ｌ(n＋1)ｘn+1−・・・}÷２ｘ

　＝{−Ｌ(1)−Ｌ(2)ｘ−・・・−Ｌ(n＋1)ｘn−・・・}÷２

ゆえに、(1)を代入して、
Ｋ(n)＝Ｃ(2n,n)／n+1 ・・・・・・（答）
＜＊組み合わせの記号の表現が違うだけ＞

これが、 Ｋ(n) の値を計算する式で、オイラーの公式と呼ばれている。

具体的に求めてみると、

Ｋ(1)＝Ｃ(２，１)／２＝２／２＝１
Ｋ(2)＝Ｃ(４，２)／３＝６／３＝２
Ｋ(3)＝Ｃ(６，３)／４＝２０／４＝５
・・・・・・

以上で、カタラン数のもっている漸化式から、一般項を求めてみました。＜終了＞

＜引用文献＞「数学ひとり旅」：石谷　茂 著　現代数学者

　◆有理数・数列の性質へもどる

　数学の部屋へもどる