| 私のクラスの生徒は教材費に五百円払う必要があります。そこで、五百円玉しか持 っていないｎ人の生徒と、千円札しか持っていないｎ人の合計２ｎ人の生徒がいま 担任の私はつり銭を準備していませんでした。つり銭が不足しないように生徒から もらう方法は全部で何通りありますか。ただし、生徒の２ｎ人に区別しないで、 お金の出し方で考えてください。 |
問題の中で、500円玉を払うのをＡ，1000円玉を払うのをＢとします。釣り銭がない
ので、常にＡの数がＢの数より等しいか大きければよいのです。
ｎ＝１のとき、ＡＢ の１通り
ｎ＝２のとき、ＡＡＢＢ，ＡＢＡＢ の２通り
ｎ＝３のとき、
ＡＡＡＢＢＢ，ＡＡＢＡＢＢ，ＡＡＢＢＡＢ，ＡＢＡＡＢＢ，ＡＢＡＢＡＢ
の５通り ここで、考え方を変えて、
これをＡを→、Ｂを↑と表せば、→がｎ個、↑ がｎ個の同じものを一列に並べる方
法と考えます。だから、碁盤の目をした最短経路の問題に変化していきます。分かり
易くするために、求める数をＫ(n)とすると、Ｋ(１)＝１，Ｋ(２)＝２，Ｋ(３)＝５
は図を書いて、分かるとします。
このＫ(n)の数列をカタラン数と言います。
ｎ＝４のときを描きます。
図のような△ＡＢＣの最短経路の道筋がＫ(４)になります。
＜考え方からの副産物＞
Ｋ(４)を求めるのに、
(@)Ｂ１を通るとき、Ａから Ｂ１を通り、△Ｂ１ＤＢの最短
経路Ｋ(３)の道筋
(A)Ｂ１を通らず、Ｂ2を通るとき、△GHLの最短経路Ｋ(１)か
ら、道路ＬＢ２を通 り、△Ｂ２ＥＢの最短経路Ｋ(２)の道筋
(B)Ｂ１、Ｂ２を通らず、Ｂ３を通るとき、△ＧＩＭの最短経路Ｋ(２)から、
道路ＭＢ３を通り、△Ｂ３ＦＢの最短経路Ｋ(１)の道筋
(C) 最後に、Ｂ１，Ｂ２、Ｂ３を通らず、Ｂに行く場合は
△ＧＣＦの最短経路Ｋ(３) に等しい。
よって、Ｋ(４)＝ Ｋ(３)＋Ｋ(１)Ｋ(２)＋Ｋ(２)Ｋ(１)＋ Ｋ(３)
＝５＋１×２＋２×１＋５＝１４ になります。
これは、一般に Ｋ(０)＝１と決めておけば、
Ｋ(ｎ)＝Ｋ(0)Ｋ(n−1)＋Ｋ(1)Ｋ(n−2)＋Ｋ(2)Ｋ(n−3) ＋・・・＋Ｋ(n−1)Ｋ(0)
という、漸化式が成り立ちます。
また、こんな数え方（書き込み方式）もできます。
14Ｂ
↑
５→14Ｆ
↑ ↑
２→５→９Ｅ
↑ ↑ ↑
１→２→３→４Ｄ
↑ ↑ ↑ ↑
Ａ→１→１→１→１Ｃ
さらに、斜めの線に関しての対称性に気がつけば、
Ｋ(４)＝ １×１＋３×３＋２×２＝１４
Ｋ(５)＝ １×１＋４×４＋５×５＝４２
Ｋ(６)＝ １×１＋５×５＋９×９＋５×５＝１３２
したがって、カタラン数Ｋ(ｎ)は何個かの平方数の和でできています。
さて、本題に入ります。ｎ＝４で描きます。
□ＤＡＣＢの最短経路の道筋は、階乗の記号を使えば、
（４＋４）！÷（４！×４！）＝７０ 通り あります。
ここから、対角線ＡＢと交わる経路が不適ですから、この不適な経路を求めます。
例えば、図の太線の経路は不適ですが、これを直線Ｔ１Ｔ４について対称移動します。
ただし、直線Ｔ１Ｔ４に始めて出会った点から後の部分のみを対称に曲げて図の太い波
線を考えると、全ての不適な経路は□ＡＥＦＧの最短経路の数に等しくなります。
いくつかの数の積は、２つずつの数の積の計算を繰り返して行っている。だから、
どの２つずつの積を作っていく方法の数はどうなるかという問題（カタランの問題）
が、１８３８年にカタランによって論じられた。ｎ個の数の順序が変わらない積の総
をＣ（ｎ）とし、ｎ個の数の順序を変えても良い積の総数をＲ（ｎ）とする。
具体例をｎ＝１，２，３，４で見ます。
@ ｎ＝１のとき、Ｃ（１）＝１、Ｒ（１）＝１と考えておく。
A ｎ＝２のとき、数をａ，ｂと書くと、積は ａｂ，ｂａ の２通りで、
Ｃ（２）＝１、Ｒ（２）＝２ となる。
B ｎ＝３のとき、数をａ，ｂ，ｃと書くと、積は
（ａｂ）ｃ，ａ（ｂｃ），（ａｃ）ｂ，ａ（ｃｂ），（ｂａ）ｃ，ｂ（ａｃ），
（ｂｃ）ａ，ｂ（ｃａ），（ｃａ）ｂ，ｃ（ａｂ），（ｃｂ）ａ，ｃ（ｂａ）
１２通りで、Ｃ（３）＝２、Ｒ（３）＝１２ だとわかる。
C ｎ＝４のとき、数をａ，ｂ，ｃ，ｄと書くと、数の順序がａ，ｂ，ｃ，ｄとなる積は
（（ａｂ）ｃ）ｄ，（ａｂ）（ｃｄ），（ａ（ｂｃ））ｄ，ａ（（ｂｃ）ｄ），ａ（ｂ（ｃｄ））
の５通りなので、Ｃ（４）＝５、Ｒ（４）＝Ｃ（４）×（４！）＝５×２４＝１２０。
＊注：前述のｋ（ｎ）とＣ（ｎ）の関係はＣ（ｎ）＝Ｋ（ｎ−１） です。
＊参考：ｎ≧２のとき、次の性質があります。
１） Ｒ（ｎ＋１）＝（４ｎ−２）Ｒ（ｎ）
２） Ｒ（ｎ）＝２・６・10・14・・・(４ｎ−６）
３） Ｃ（ｎ）＝ Ｒ（ｎ）／ｎ！
４） Ｃ（ｎ＋１）＝｛（４ｎ−２）／（ｎ＋１）｝Ｃ（ｎ）
５） Ｋ（ｎ＋１）＝｛（４ｎ＋２）／（ｎ＋２）｝Ｋ（ｎ）・・・（漸化式の発見）
| 
| 
| 
| 
|
＊注： Ｅ（ｎ）＝Ｃ（ｎ−１）＝Ｋ（ｎ−２）の関係となる。
参考：1758年にセニェールが発見した漸化式
最後に、カタラン数列を書きます。｛１，２，５、１４，４２，１３２，・・・｝ 平成１１年６月２３日 そこで、今日は先日、次のような質問を受けましたので、追加説明します。 「平面上で、凸ｎ角形を対角線において３角形に分割する方法の数Ｅ（ｎ）はどうして、カタラン数に なるのでしょうか。」 凸ｎ角形を三角形に分割する仕方はちょうどカタラン数をなしています。 もちろん、ｎ＝３からスタートしていきましので、Ｅ（ｎ）＝Ｋ（ｎ−２）ずらしてあります。 カタランの漸化式は次になります。 Ｅ(ｎ)＝Ｅ(２)Ｅ(ｎ−１)＋Ｅ(３)Ｅ(ｎ−２)＋Ｅ(４)Ｅ(ｎ−３)＋・・・＋Ｅ(ｎ−１)Ｅ(２) ここで、ｎ＝７の図をみてください。 ７角形Ａ１Ａ２・・・Ａ７を考えてみます。辺Ａ６Ａ７を注目ください。 （１）△Ａ１Ａ６Ａ７を含む分割の仕方は残りの６角形の仕方の数Ｅ（６）に等しい （２）△Ａ２Ａ６Ａ７を含む分割の仕方は残りの３角形と５角形の分割の仕方を組み合わせたもので、 その数はＥ（３）Ｅ（５）である。 （３）△Ａ３Ａ６Ａ７を含む分割の仕方は残りの４角形と４角形の分割の仕方を組み合わせたもので、 その数はＥ（４）Ｅ（４）である。 （４）△Ａ４Ａ６Ａ７を含む分割の仕方は残りの５角形と３角形の分割の仕方を組み合わせたもので、 その数はＥ（５）Ｅ（３）である。 （５）△Ａ５Ａ６Ａ７を含む分割の仕方は残りの６角形の仕方の数Ｅ（６）に等しい ただし、図の中はＥ（ｎ）＝ｆ（ｎ）で表現してあります。 したがって、Ｅ（２）＝１と便宜上して、Ｅ（３）＝１です。 Ｅ(７)＝Ｅ(２)Ｅ(６)＋Ｅ(３)Ｅ(５)＋Ｅ(４)Ｅ(４)＋Ｅ(５)Ｅ(３)＋Ｅ(５)Ｅ(２) そして、一般に、 Ｅ(ｎ)＝Ｅ(２)Ｅ(ｎ−１)＋Ｅ(３)Ｅ(ｎ−２)＋Ｅ(４)Ｅ(ｎ−３)＋・・・＋Ｅ(ｎ−１)Ｅ(２) が成立します。 ここから、この分割がカタラン数をなしていきます。オイラーは偉大ですね。
なぜ、日常生活のこれらの現象が１つの数列として、見なされるか不思議です。
