◆広島県 清川 育男さんからの解答。
カタラン数になることが予想されます。
最初は５００円硬貨を持った生徒から集金します。
ｎ＝１→１
ｎ＝２→２
ｎ＝３→５
ｎ＝４→１４
| 2nＣn ―――― ｎ＋１ | ＝ | ２ｎ！ ―――――――― ｎ！×（ｎ＋１）！ |
「三角形に分けると」と同じ問題になるのが不思議です。
証明がまだ出来ません。
算チャレメーリングリストでもカタラン数が話題になっています。
【コメント】
うーむ、するどい。
証明は書こうと思うと結構大変ですが、ぜひお願いします。
私も「三角形に分けると」と同じというのは不思議です。
◆広島県 清川 育男さんからの解答。
５００円玉を持っている生徒ｎ人、１０００札を持っている生徒ｎ人を１列に並べる。
その場合の数は、2nＣn 通りです。
何番目でもいいが、仮にｍ番目の千円札を持っている生徒でつり銭が出せない場合を考える。
つり銭が出せない場合の数は、2nＣn-1通りです。
したがって、つり銭がいらないで、２ｎ人の生徒から集金が出来る場合の数は、
2nＣn−2nＣn-1
| ＝ | 2nＣn ―――― ｎ＋１ |
| ＝ | ２ｎ！ ―――――――― ｎ！×（ｎ＋１）！ |
カタラン数を考えるとき、本質的でかつシンプルで非常に良い問題だと思います。
【コメント】
これは分かりやすい計算ですね。
「三角形に分けると」の解答の中の回帰的な公式を使って示しても、面白いのではないでしょうか。
◆広島県 清川 育男さんからの解答。
| ２ｎ！ ――――――――― ｎ！×（ｎ＋１）！ |
数学的帰納法により証明する。
ｎ＝１ のとき ５００，１０００ の１通り。
| ２！ ――――――――― １！×（１＋１）！ | ＝１ |
ｎ＝ｋ のとき
| χ＝ | ２ｋ！ ――――――――― ｋ！×（ｋ＋１）！ |
ｎ＝ｋ＋１ のとき
（２ｋ＋２）番目、即ち最後の生徒は１０００円札を持った生徒になる。
５００円玉を持った生徒の列に入ることのできる場所は、（２ｋ＋１）箇所。
この列はつり銭なしに集金できる。
またこの列の２ｋ番目の生徒と（２ｋ＋１）番目の生徒を入れ替えた列も、つり銭なしに集金できる。
このことはどの列に対しても言える。
（χ×（２ｋ＋１）×２）は、実際に可能な列のＹ倍になっている。
Ｙ＝(k+1)+1Ｃ1＝k+2Ｃ1＝ｋ＋２。
したがって求める列の場合の数は、
| ２ｋ！ ――――――――― ｋ！×(ｋ＋１)！ | × | (２ｋ＋１)×２ ――――――――― ｋ＋２ |
| ＝ | ２ｋ！×(４ｋ＋２) ――――――――― ｋ！×(ｋ＋２)！ |
分子、分母に（ｋ＋１）を掛ける。
| ＝ | (ｋ＋１)×(４ｋ＋２)×２ｋ！ ―――――――――――――― (ｋ＋１)×ｋ！×(ｋ＋２)！ |
| ＝ | (２ｋ＋２)×(２ｋ＋１)×２ｋ！ ――――――――――――――― (ｋ＋１)！×(ｋ＋２)！ |
| ＝ | (２(ｋ＋１))！ ――――――――――――――― (ｋ＋１)！×((ｋ＋１)＋１))！ |
上式は ｎ＝ｋ＋１ のときも成り立つことを表わしている。
以上です。
カタラン数の漸化式の一つとして、
| Ａn+1＝ | ４ｎ＋２ ―――――― ｎ＋２ |
×Ａn |
◆石川県 数学好き さんからの解答。
解答ではないのですが、ようやく問題の意味が分かりました。
五百円玉を●、千円札を○で表すと、
・ｎ＝１の時、
・ｎ＝３の時、
◆出題者の 水の流れ さんの解答。
問題の中で、500円玉を払うのをＡ，1000円玉を払うのをＢとします。
釣り銭がないので、常にＡの数がＢの数より等しいか大きければよいのです。
ｎ＝１のとき、ＡＢ の１通り
ｎ＝２のとき、ＡＡＢＢ，ＡＢＡＢ の２通り
ｎ＝３のとき、
ＡＡＡＢＢＢ，
ＡＡＢＡＢＢ，
ＡＡＢＢＡＢ，
ＡＢＡＡＢＢ，
ＡＢＡＢＡＢ の５通り
ここで、考え方を変えて、これをＡを→、Ｂを↑と表せば、
→がｎ個、↑ がｎ個の同じものを一列に並べる方法と考えられます。
だから、碁盤の目をした最短経路の問題に変化していきます。
分かり易くするために、求める数をＫ(n)とすると、
Ｋ(１)＝１，Ｋ(２)＝２，Ｋ(３)＝５
は図を書いて、分かるとします。
このＫ(n)の数列をカタラン数と言います。
ｎ＝４のときを描きます。
図のような△ＡＢＣの最短経路の道筋がＫ(４)になります。
＜考え方からの副産物＞
Ｋ(４)を求めるのに、
(@)Ｂ１を通るとき、Ａから Ｂ１を通り、△Ｂ１ＤＢの最短経路Ｋ(３)の道筋
(A)Ｂ１を通らず、Ｂ2を通るとき、
△GHLの最短経路Ｋ(１)から、道路ＬＢ２を通り、△Ｂ２ＥＢの最短経路Ｋ(２)の道筋
(B)Ｂ１、Ｂ２を通らず、Ｂ３を通るとき、
△ＧＩＭの最短経路Ｋ(２)から、道路ＭＢ３を通り、△Ｂ３ＦＢの最短経路Ｋ(１)の道筋
(C) 最後に、Ｂ１，Ｂ２、Ｂ３を通らず、Ｂに行く場合は
△ＧＣＦの最短経路Ｋ(３) に等しい。
よって、
Ｋ(４)
＝ Ｋ(３)＋Ｋ(１)Ｋ(２)＋Ｋ(２)Ｋ(１)＋ Ｋ(３)
＝５＋１×２＋２×１＋５＝１４ になります。
これは、一般に Ｋ(０)＝１と決めておけば、
K(ｎ)＝K(0)K(n−1)＋K(1)K(n−2)＋K(2)K(n−3) ＋・・・＋K(n−1)K(0)という、漸化式が成り立ちます。
また、こんな数え方(書き込み方式)もできます。
14Ｂ ↑ ５→14Ｆ ↑ ↑ ２→５→９Ｅ ↑ ↑ ↑ １→２→３→４Ｄ ↑ ↑ ↑ ↑ Ａ→１→１→１→１Ｃさらに、斜めの線に関しての対称性に気がつけば、
K(４)＝ １×１＋３×３＋２×２＝１４したがって、カタラン数Ｋ(ｎ)は何個かの平方数の和でできています。
K(５)＝ １×１＋４×４＋５×５＝４２
K(６)＝ １×１＋５×５＋９×９＋５×５＝１３２
さて、本題に入ります。ｎ＝４で描きます。
□ＤＡＣＢの最短経路の道筋は、階乗の記号を使えば、
(４＋４)！÷(４！×４！)＝７０ 通り あります。
ここから、対角線ＡＢと交わる経路が不適ですから、この不適な経路を求めます。
例えば、図の太線の経路は不適ですが、これを直線Ｔ１Ｔ４について対称移動します。
ただし、直線Ｔ１Ｔ４に始めて出会った点から後の部分のみを対称に曲げて図の太い波線を考えると、全ての不適な経路は□ＡＥＦＧの最短経路の数に等しくなります。
これは、 (５＋３)！÷(５！×３！)＝５６ 通りとなり、
求めるカタラン数Ｋ(４)は、組合わせの記号をＣ(ｎ，ｒ)とすれば、
K(４) ＝Ｃ(８，４) −Ｃ(８，３)＝７０−５６＝１４ になります。
一般に、
K(ｎ)
＝Ｃ(２ｎ，ｎ) −Ｃ(２ｎ，ｎ−１)
＝Ｃ(２ｎ，ｎ)÷(ｎ＋１)
となります。
そこで、また、問題です。
次の台形ＡＢＣＤの最短経路は何通りありますか。
研究 カタランの問題の原典
いくつかの数の積は、２つずつの数の積の計算を繰り返して行っている。
だから、どの２つずつの積を作っていく方法の数はどうなるかという問題(カタランの問題)が、１８３８年にカタランによって論じられた。
ｎ個の数の順序が変わらない積の総数をＣ(ｎ)とし、
ｎ個の数の順序を変えても良い積の総数をＲ(ｎ)とする。
具体例をｎ＝１，２，３，４で見ます。
(1) ｎ＝１のとき、Ｃ(１)＝１、Ｒ(１)＝１と考えておく。
(2) ｎ＝２のとき、数をａ，ｂと書くと、積は ａｂ，ｂａ の２通りで、
Ｃ(２)＝１、Ｒ(２)＝２ となる。
(3) ｎ＝３のとき、数をａ，ｂ，ｃと書くと、積は
(ａｂ)ｃ，ａ(ｂｃ)，(ａｃ)ｂ，ａ(ｃｂ)，
(ｂａ)ｃ，ｂ(ａｃ)，(ｂｃ)ａ，ｂ(ｃａ)，
(ｃａ)ｂ，ｃ(ａｂ)，(ｃｂ)ａ，ｃ(ｂａ)
１２通りで、Ｃ(３)＝２、Ｒ(３)＝１２ だとわかる。
(4) ｎ＝４のとき、数をａ，ｂ，ｃ，ｄと書くと、数の順序がａ，ｂ，ｃ，ｄとなる積は
((ａｂ)ｃ)ｄ，(ａｂ)(ｃｄ)，(ａ(ｂｃ))ｄ，
ａ((ｂｃ)ｄ)，ａ(ｂ(ｃｄ))
の５通りなので、
Ｃ(４)＝５、Ｒ(４)＝Ｃ(４)×(４！)＝５×２４＝１２０。
＊注：前述のｋ(ｎ)とＣ(ｎ)の関係は
Ｃ(ｎ)＝Ｋ(ｎ−１) です。
＊参考：ｎ≧２のとき、次の性質があります。
| 
| 
| 
| 
|
＊注： E(n)＝C(n−1)＝K(n−2)の関係となる。
参考：1758年にセニェールが発見した漸化式
E(n)＝E(2)E(n−1)＋E(3)E(n−2)＋E(4)E(n−3)・・・＋E(n−1)E(2)最後に、カタラン数列を書きます。
なぜ、日常生活のこれらの現象が１つの数列として、見なされるか不思議です。