未菜実さんから教えていただいた問題です。
数理パズル入門というホームページを開いているそうなので、興味のある方はどうぞ。
【問題】
今、上段にａ1〜ａnまで、
下段に逆順でａn〜ａ1まで文字が書いてあります。
この上段下段の同じ文字どうしが結ばれるあみだくじを作ります。
横線を最小本数で結ぶ場合のその横線の本数と、その本数で作れるあみだくじの数を求めるのが問題です。
ｎ=３の時の例を示すと、
図のように横線３本で２種類出来ます。
【問題１−１】
ｎ=４の時の横線の本数を求めてください。
【問題１−２】
ｎ=４の時の、出来るあみだくじの種類は何通りでしょうか。
【問題２−１】
ｎ=５の時の横線の本数を求めてください。
【問題２−２】
ｎ=５の時の、出来るあみだくじの種類は何通りでしょうか。
【問題３】
ｎ＝ｋ の時の横線の本数と出来るあみだくじの種類を求めてください。
東京都 合屋さんからの問題です。
あみだくじには次のような法則があります。
何故このようになるのでしょうか？
なお、以下の法則Tはあみだくじの種類に関係なく成り立ちます。
法則U，Vは問題と同じ条件
（横線を最小本数でａ1〜ａnをａn〜ａ1に並べ変える）
のあみだくじとします。
◆法則T
全てのルートを上から下までたどるとあみだくじの全ての線を１回以上通る。
（実際には縦線を１回、横線は右からと左からの２回）
◆法則U
ｎ本目の縦線とｎ＋１本目の縦線の間に引く横線の数を
Ｂnで表すことにする。
Ｋ本のあみだくじではＢnの最小値は
ｎ と Ｋ−ｎ の小さい方となる。
例えばＫ＝５の時
Ｂ1〜Ｂ4の最小値は１，２，２，１
Ｋ＝６の時
Ｂ1〜Ｂ5の最小値は１，２，３，２，１
◆法則V
Ｋ本のあみだくじではどのルートでも上から下までたどると
Ｋ−１本の横線を通る。
東京都 建築家 さんからの追加問題です。
【追加問題１】
平面上にどの３つも交わらずどの２つも平行でないｎ本の直線がある。
そのうち一つは赤く方向がついていて、他の(n-1)本の直線は黒いものとする。
このｎ本の直線が平面を分割する分割の仕方をH[ｎ]種類とする。
ただし直線と交点の関係を変えずに動かして一致するものは同型とみなす。
例えば
H[1]＝１、H[2]＝１、H[3]＝２
である。
横線を最小本数で結ぶ場合の、その本数で作れるあみだくじの数の種類をK[ｎ]個とする。
（１）H[4]＝K[4]となることを確かめよ。
（２）あみだの最小の横線の本数はnＣ2本であることを確かめよ
（３）H[ｎ]＝K[ｎ]となることを証明せよ。
【追加問題２】
H[n+1] ≧ H[n](nC2+1) を証明して下さい。
まず交点がnC2個あります。
そのうちのある一つの交点と同じ直線（２本）に乗っていないものは
n-2C2個あります。
このようなペアは全部で{nC2×n-2C2/2}個あります。
これらの点と始めの１点はあみだで言えば未菜実のコメントにあるようなy1,y2の関係になる可能性があります。
実際、確率で言えばだいたい４つに一つがそのようになります。
（n=4 の時の８通り全てを図に書いてみるとわかりやすいと思います。
３ペア×８通りのうち６つがそのようになっています。
それがn=5以上の場合も特別な場合を除きそれぞれのペアについて成り立ちます。）
そのそれぞれについて上の数え方だと１個づつ足りなくなりますので、その分足してみればおよそ
H[n+1] 〜 H[n]{nC2+1+(nC2×n-2C2)/(2×4)}
＝ H[n]{n(n-1)(n2-5n+22)/32 + 1}
となります。
（ちなみに上の数えかたはn本の交点を通る平行線で区切ると
(nC2+1)つの区間ができますので、
その間に(n+1)本めの直線を引くという考え方です。）
H[3] ＝2 から始めてこれを計算していくと、
H[4] ＝ 8
H[5] ＝ 62
H[6] 〜 914
H[7] 〜 24,906
H[8] 〜 1,201,739
H[9] 〜 97,941,728
H[10] 〜 12,879,337,297
H[11] 〜 2,620,945,140,092
H[12] 〜 795,456,850,017,960
（小数点以下は切り下げてます。）
とだいたい近い感じの値がでてるのではと思います。
誰か確かめて頂けると有り難いですが^^;
【追加問題３】
あみだくじでいえば横線が直線の交点となっています。
その横線を上から並べていった時に順番をかえても同型となるような組を数えるのがこの問題の難点です。
上でいう交点のペアのうち１／４がおよそその横線の組である理由と、それが当てはまらないケースを示して下さい。
◆個数を数える問題へもどる
数学の部屋へもどる