思い通りのあみだくじを作る方法　　　　　　　　　　　　　

　何かを決めるとき、あみだくじのお世話になる時が多い。そんなとき、ズルをして、「自分の
思う通りのあみだくじが作れればいいのになあ〜！！」と考える人は少なからずいると思う。

　例えば、意にそわない仕事の担当を決めるときとか、コンパで席順を決めるとき、意中の
人のそばに座れるようにするとか、その活用例はたくさんあるだろう。

　このページでは、あみだくじの作り方についてまとめてみたい。

　あみだくじは、何本かの垂直な縦線と何本かの横線からなるもので、横線どうしがつなが
らないようなものである。

　まず、任意の縦線の上方からスタートし、横線にぶつかったら、そこで横線の方に進み、
縦線にぶつかったら、そこで縦線を下の方へ進む。順次このような手順で、最下段まで進
み続ける。


（追記）　令和６年５月２５日付け

　上記のような縦線のあみだくじになったのは後世で、当初は、次のようなものだったらしい。

　　

　中央の円内に当たり印（○印や当たりなど）を記入し、お椀等で円内を隠し、何れかの線
を選んでもらう。選び終わったら、お椀を開け、誰が当たりかを見る。

　日本では、未来を神仏に委ねる文化があり、絵柄が阿弥陀如来の後光に似ていることから
「あみだくじ」と呼ばれるようになったらしい。


　あみだくじは、数学的にとらえれば単なる順列である。

右図のあみだくじを例にとると、数字の並び 　　　１　，２　，３　，４　，５　，６ があみだくじにより、 　　　４　，６　，２　，５　，１　，３ に並べかえられたにすぎない。

　数学の世界では、これを置換という。置換は必ず互換の積で表される。横線の１本１本が
互換に相当する。即ち、互換とは、２つのものの交換を意味する。

　ここでは逆に、１，２，３，４，５，６　の並びが、４，６，２，５，１，３　の並びになるようなあみ
だくじを作る手順を考えようということである。


　これができれば、自分の思う通りのあみだくじが作れるということになるわけである。

次のような手順で簡単に作ることができる。

　

一番右側の折れ線を直線に直せば、上図のあみだくじになる。


（追記）　なんとはなしに、子供の書棚にある本を眺めていたら、あみだくじの作り方は、他
　　　　にもあることを知った。それを紹介したい。

　それは、横線を何本か引いて、端の方から一つずつ決めていくやり方である。数字の個
数が多い場合は、この方法のほうが有効だと思う。上記の方法だと、線がこみいって、作
りにくいかもしれない。

同じ置換なのに、このように複数のあみだくじができる。 　　置換は、互換の積で表されるが、その表現は一意でないという 　ことが、この事実からも分かる。 　（参考文献）　秋山　仁著 　　　ワンダー数学ランド（日本放送出版協会）

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

　本日の朝日新聞朝刊で、小島寛之さん（帝京大准教授）のコラム「数学カフェ」があみだく
じの話題を取り上げている。

　横棒が１本もない「素あみだ」に興味を引かれた。

　コラムでは、

　縦棒が４本のあみだくじを一つ作り、さらにこれと同じくじを縦に１２個つなげて新し
いあみだくじを作ると必ず素あみだになる

という。

　コラムの説明は次のようになっていた。（置換の言葉に修正！）

　例えば、巡回置換 （ １ ２ ３ ）　において、

　　　（ １ ２ ３ ）³＝（ １ ２ ３ ）（ １ ２ ３ ）（ １ ２ ３ ）＝ ｅ （恒等置換）

　同様に、巡回置換 （ １ ２ ３ ４ ）　において、

　　　（ １ ２ ３ ４ ）⁴＝（ １ ２ ３ ４ ）（ １ ２ ３ ４ ）（ １ ２ ３ ４ ）（ １ ２ ３ ４ ）＝ ｅ （恒等置換）

となる。したがって、３ と ４ の最小公倍数である １２個つなげば必ず恒等置換になる。

　「ほんとにそうかな〜？」と思って自分なりに根拠を考えてみた。

　あみだくじは基本的に置換であり、置換は必ず偶置換か奇置換に分かれ同数ある。
（ → 参考：「１５ゲームの不可能性の評価」）

したがって、その位数は、４！/２＝１２　であり、任意の置換 σ に対して、　σ¹² ＝ ｅ　が

成り立つ。　（こんな理解でいいのかな？）


（追記）　令和２年８月２４日付け

　上記の「素あみだ」で、逆あみだを繋げれば当然「素あみだ」が作れますよね！

例
　　

に対して、その逆あみだは

　　

で、２つを繋げると素あみだ

　　

になる。


（追記）　「お好みのあみだくじをつくろう」と題して、ＧＡＩ さんからの投稿です。
　　（平成２８年２月８日付け）

　古来日本では順番を決めるのにあみだくじなる道具を利用してきた。

　例えば、３本の線を引き、

1  2  3
|  |  |
|--|  |
|  |--|
|--|  |
|  |  |

なるあみだくじを引けば、結果は 3, 2, 1 の順になり、上で引いた順番と全く逆の結果となる。

　そこで、7本の線が引かれていた場合、上で引いた７人の順番が引いた結果全く入れ替わっ
てしまうあみだくじを構成してほしい。ただし、可能な限り横線の数が少なくなるものを示してほ
しい。

　答えは幾通りも作れるので、その一つを再現できる様に表現を工夫してアップして下さい。


　らすかるさんからのコメントです。（平成２８年２月８日付け）

　3本のとき

┃┃┃
┣┫┃
┃┣┫
┣┫┃
┃┃┃

ならば、7本のときは

┃┃┃┃┃┃┃
┣┫┃┃┃┃┃
┃┣┫┃┃┃┃
┣┫┣┫┃┃┃
┃┣┫┣┫┃┃
┣┫┣┫┣┫┃
┃┣┫┣┫┣┫
┣┫┣┫┣┫┃
┃┣┫┣┫┃┃
┣┫┣┫┃┃┃
┃┣┫┃┃┃┃
┣┫┃┃┃┃┃
┃┃┃┃┃┃┃

がわかりやすそうですね。


（コメント）　当ＨＰの「順列の転位」の話題とも関係するかな？


（追記）　令和２年１２月１６日付け

　１，２，３，４，５ のあみだくじで、１と５の入れ替えのあみだくじは何種類あるかを考えてみ
ました。交差する位置を考慮して、全部で４種類あるようです。

　　　　　　　


（追記）　令和３年２月２４日付け

　あみだくじで何かを決めるとき、横棒を何本でも引いていいよ、という場合が多い。
横棒の最小本数は、「横棒の数＝転位数」で決まっているので、意味がない横棒も
あるが、横棒を追加することによって新たなチャンスになることもあり興味はつきない。

例　次のあみだくじは横棒の本数が違うだけで同じ結果を得る例になっている。

　　　　　　　　　

　転位数を計算すると、　２＞１、３＞１、４＞１　から、転位数は３で、横棒は最低３本あれ
ば十分である。

　上図は数が少ないので、同じ結果になることは明白だが、もっと数が多い場合に同じ結果
になるかならざるかは少し考えるかもしれない。


（追記）　令和６年５月２５日付け

　「チコちゃんに叱られる」（ＮＨＫ　５月２４日放送）で、あみだくじの話題が取り上げられてい
た。その中で興味を引いたのは、当たりくじを引くためには、どの線を選ぶのがベストかとい
うこと。確率計算によれば、当たりくじの真上を選ぶのが半々の確率で当たりとなるらしい。
当たりから最も遠い線を選ぶと、当たりの確率は極端に下がるとのこと。

　今度、試してみよう！


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

　私も「チコちゃんに叱られる」の番組を見ていて、縦線が５本、横線が８本からなるあみだ
くじの全パターン数が、9841通りあり、

上の線 1 | 2 | 3 | 4 | 5　に対して、

下の線(1の下がa,･･････,5の下がe)　であるとき、

a; 43.92 | 24.61 | 16.53 | 10.25 | 4.68
b; 24.61 | 25.46 | 22.06 | 17.61 |10.25
c; 16.53 | 22.06 | 22.81 | 22.06 |16.53
d; 10.25 | 17.61 | 22.06 | 25.46 |24.61
e;  4.68 | 10.25 | 16.53 | 24.61 |43.92

の表が映像に出た。確かに真下に当たりがあれば、そこからスタートすれば確率が高い。

　この確率をどうしたら出せるのか色々挑戦しているのだが、なかなかこの値を持たせられ
ない。また、「9841」はどこからどうして算出するものなのか？


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

　横線の立体交差はアリでしたか？

　たとえば、

�@　左から１本目の縦線と３本目の縦線とのあいだに横線を１個つなげる、ただし、２本目
　の縦線とこの横線とは立体交差にする。

�A　横線どうしで立体交差をする。


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

　特に、立体交差のコメントは無かったので、通常のあみだの横線の引き方で考えるものだ
と思います。


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

　Ｗｅｂサイト「高校数学の美しい物語」によると、縦線５本、横線８本でのあみだくじの行き
先の確率は、

　　

から、Ｐ₅⁸ を計算して、

[12155/32768 19449/65536 12393/65536 1581/16384 765/16384]

[19449/65536 8627/32768 3345/16384 9129/65536 1581/16384]

[12393/65536 3345/16384 6995/32768 3345/16384 12393/65536]

[ 1581/16384 9129/65536 3345/16384 8627/32768 19449/65536]

[ 765/16384 1581/16384 12393/65536 19449/65536 12155/32768]

これを、小数へ直し、

[ 0.37094116 0.29676819 0.18910217 0.096496582 0.046691895]

[ 0.29676819 0.26327515 0.20416260 0.13929749 0.096496582]

[ 0.18910217 0.20416260 0.21347046 0.20416260 0.18910217]

[0.096496582 0.13929749 0.20416260 0.26327515 0.29676819]

[0.046691895 0.096496582 0.18910217 0.29676819 0.37094116]

となるのではないかと思うのだが・・・？


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

　そのサイトでは、横線の引き方が ｍⁿ 通りと言っていますので、確率分布が違うのではな
いでしょうか。例えば、

を別のものと考えているのでは？

# 全部きちんと読んだわけではありませんので、もし、とんちんかんなことを言っていたら
　ご容赦下さい。


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

　ツイッター検索で調べたら、チコちゃんの番組で、あみだくじについて解説した先生が、
岩手大学理工学部の山中克久教授であるとわかりました。

　OEIS のサイトで、この先生の名前で検索したらヒットしました。（→　「A006245」）

　「A006245」の参考文献に、以下があげられていました。

ひとつめ
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno and Kunihiro Wasa,
Ladder-Lottery Realization, 30th Canadian Conference on Computational Geometry
(CCCG 2018) Winnipeg.

ふたつめ
K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara and K. Nakada,
Efficient enumeration of all ladder lotteries and its application,
Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010.

　なお、ladder lotteries とはアミダクジのことです。


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

　9841通りの計算は、

　Σ[i=0〜8]Σ[j=0〜8-i] (i+j)Cj×9C(i+j+1)＝9841

という式で出せました。

　i は、2本目の縦線と3本目の縦線の間に描く横線の数、

　j は、3本目の縦線と4本目の縦線の間に描く横線の数、

　(i+j)Cj は、「2本目の縦線と3本目の縦線の間の横線」と「3本目の縦線と4本目の縦線の
間の横線」の位置関係の場合の数、

　9C(i+j+1) は、残りの 8-i-j 本の横線を「1本目の縦線と2本目の縦線の間」と「4本目の縦
線と5本目の縦線の間」に配置する場合の数です。


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

　らすかるさん、凄いです。


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

　「9841通り」の数値をはじき出す数式を見つけるなんて、ビックリです。分析させて頂きました。

　そこで、　i、j＝0、2 で、　1*84=84　の解釈が、

　縦線 2、3 番目には 0 本、3、4 番目には 2 本引かれているので、1、2 と 4、5 間には合計
6 本の縦線がある。そこで、

1,2番間　;4,5番間
　6　 ;0
　5 　;1
　4 　;2
　3　 ;3
　2　 ;4
　1 　;5
　0 　;6

本の線がある場合に分かれる。ところで、2、3 番間には、i＝0 より、上記の左の本数は何
の制限もなく引くことが出来る。

　一方、j＝2 より、既に、3、4 番間には 2 本の横棒が引かれている。そこで、上記の右の
本数の横棒を引く位置は、それぞれ重複組合せから、

　3H0=1
　3H1=3
　3H2=6
　3H3=10
　3H4=15
　3H5=21
　3H6=28

　これの合計が、84 となる。何と、これが一発で

　9C6=9C3=9*8*7/(3*2*1)=3*4*7=84

なわけですね。同じく、i、j＝0、3 で、1*126＝126 は、

1,2番間　;4,5番間
　5 ;0
　4 ;1
　3 ;2
　2 ;3
　1 ;4
　0 ;5

　上記の右の本数の横棒を引く位置はそれぞれ重複組合せから

　4H0=1
　4H1=4
　4H2=10
　4H3=20
　4H4=35
　4H5=56

　この合計が 126。同じく、一発で、9C5=9C4=9*8*7*6/(4*3*2*1)=126

　こんな仕組みで計算されているんですね〜


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

　5 本の縦線に ｎ 本の横線を引く場合、(3^(n+1)-1)/2 通りですか？


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

　5 本の縦線に ｎ 本の横線を引く場合、(3^(n+1)-1)/2 通りですか？

　こんな明快な式になるとは？

　ひょっとして、最も左の縦線と最も右の縦線とを同一視して、合計４本の縦線とみなすこと
によって全ての縦線について対称とするテクニックを使うということなのでしょうか？

　((4-1)^(n+1)-1)/2　において、「-1」のファクターの意味が取れませんが…… orz


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

　(3^(n+1)-1)/2 通りの場合に、n＝3 なら 40 となるが、別で調査すれば、確かに 40 通りと
なりますね。例の

(i,j)=
(0,0)-->4
(0,1)-->6
(0,2)-->4
(0,3)-->1
(1,0)-->6
(1,1)-->8
(1,2)-->3
(2,0)-->4
(2,1)-->3
(3,0)-->1　で、計40通り

　何か縦線ｍ本、横線ｎ本のあみだくじでの一般式が作れそうですね。

　一般式を作ろうと思っているが、縦線が奇数と偶数では構造が変わる様に感じたので、縦
線が４本で横線がｎ本である場合のあみだくじの種類を調べてみたら、

n=1-->3
n=2-->8
n=3-->21
n=4-->55
n=5-->144
n=6-->377

　ここまで調べて、この数字はなんか見たことあるぞ！で検索すると、フィボナッチ数列fibo(n)
での　fibo(2*n+2)　の部分が対応している。

　なお、この各合計数は、次の組合せ関数　nCr(=binomial(n,r))　を使うと、

gp > T(n,k)=binomial(n+k,2*k-1);
gp > for(n=1,10,S=[];for(k=1,n+1,S=concat(S,[T(n,k)]));print(n"=>"S";"vecsum(S)))

1=>[2, 1];3
2=>[3, 4, 1];8
3=>[4, 10, 6, 1];21
4=>[5, 20, 21, 8, 1];55
5=>[6, 35, 56, 36, 10, 1];144
6=>[7, 56, 126, 120, 55, 12, 1];377
7=>[8, 84, 252, 330, 220, 78, 14, 1];987
8=>[9, 120, 462, 792, 715, 364, 105, 16, 1];2584
9=>[10, 165, 792, 1716, 2002, 1365, 560, 136, 18, 1];6765
10=>[11, 220, 1287, 3432, 5005, 4368, 2380, 816, 171, 20, 1];17711

で求めていることになっている。しかし、縦線が６本の場合は、未調査なので、まだ何とも言
えないですが･･･。


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

　縦線が m 本である場合、

　「1 から m-1 までの数を重複を許して n 個並べる、ただし、直前の数より 2 つ以上小さく
なってはいけない」

の並べ方の総数と一致します。なので、

縦線 3 本である場合、

[1,1] * [[1,1],[1,1]]^(n-1) * t[1,1] = 2^n

縦線 4 本である場合、

[1,1,1] * [[1,1,0],[1,1,1],[1,1,1]]^(n-1) * t[1,1,1]
= 1/√5 * ( ((3+√5)/2)^(n+1) - ((3-√5)/2)^(n+1) )

縦線 5 本である場合、

[1,1,1,1] * [[1,1,0,0],[1,1,1,0],[1,1,1,1],[1,1,1,1]]^(n-1) * t [1,1,1,1] = (3^(n+1)-1)/2

と出せます。

　縦線 6 本は、固有値が綺麗に出ないので難しそう。


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

　６本の縦線がある場合について、横線が ｎ 本の場合の構成数について調べてみました。

n=1-->5
n=2-->11
n=3-->40
n=4-->145
n=5-->525
n=6-->1900
n=7-->6875
n=8-->24875

　ここまでで、OEISのお世話になると、n=1 を除いて、「A136775」がヒットした。そこには

Number of multiplex juggling sequences of length n, base state <1,1> and hand capacity 2.

という分けがわからい説明が付けられていた。

　ただし、この数値は、らすかるさんが構成されているプログラムを参考にさせてもらい、

F(n)=for(i=0,n,for(j=0,n-i,for(k=0,n-i-j,\
print(i","j","k"=>"binomial(i+j,j)"*"binomial(j+k,k)"*"binomial(n-1,n-(i+j+k))"=>"\
binomial(i+j,j)*binomial(j+k,k)*binomial(n-1,n-(i+j+k))))))

で、

2、3 番目の間にある横線の数を i 本
3、4 番目の間にある横線の数を j 本
4、5 番目の間にある横線の数を k 本

として、その横線の取り方が binomial(i+j,j)*binomial(j+k,k) で起こせて、残りの本数 n-(i+j+k)

を1、2 番目と 5、6 番目の間に取れる場合の可能性が binomial(n-1,n-(i+j+k)) としてやるこ

とで、上手く働くことを観察してみた。

　これをすべて掛け合わせることで、(i,j,k) に対するパターン数が求まっていくので、すべての
総和から、ｎ≧ 2 での数値を求めて行きました。

　n＝6 で 1900 となる経過が下の表である。(F(6)からの表示)

　合計 1900

　はて、これは一つの式で作れるのか？


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

　残りの本数 n-(i+j+k) を1、2 番目と 5、6 番目の間に取れる場合の可能性が binomial(n-1,n-(i+j+k))

　これは、　binomial(n+1-j,n-(i+j+k))　にしないといけないと思います。
(中央に使った j 本は残り本数に影響しますが、配置に影響しません)。

　よって、ｎ＝1、2、3、…　に対する構成数は、

　　5,19,66,221,728,2380,7753,25213,81927,…

のようになります。（ｎ＝2 を手作業で数えてみると、19で正しいことがわかると思います。）

　そして、この数列は、「A005021」にあり、漸化式が

　a[1]＝5、a[2]＝19、a[3]＝66、a[n+3]＝5a[n+2]−6a[n+1]＋a[n]

と書かれていますので、これを解いて一般項は、 a[n]＝up^n＋vq^n＋wr^n

ただし、

u={-(4√91)sin(arcsin(127√91/2366)/3)+7}/21
v={-(4√91)cos(arccos(-127√91/2366)/3)+7}/21
w={(4√91)cos(arccos(127√91/2366)/3)+7}/21
p={-(2√7)cos(arccos(-√7/14)/3)+5}/3
q={-(2√7)sin(arcsin(√7/14)/3)+5}/3
r={(2√7)cos(arccos(√7/14)/3)+5}/3

とわかります。

# u、v、w は、49x^3-49x^2-105x+1=0　の３解、p、q、r は、x^3−5x^2＋6x−１＝0 の３解で
　す。


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

　らすかるさんからのご指摘を受けて、改めて(数個のパターンでいいと勝手に思ってしまう
悪い癖)、６本の縦線がある場合について、横線がｎ本の場合の構成数について調べてみ
ました。

n=1-->5
n=2-->19
n=3-->66
n=4-->221
n=5-->728
n=6-->2380
n=7-->7753
n=8-->25213

ここまででOEISのお世話になるとA「A005021」がヒットした。

　らすかるさんと n＝3 で違ったので、

(i,j,k)
0,0,0= 1*1*4= 4
0,0,1= 1*1*6= 6
0,0,2= 1*1*4= 4
0,0,3= 1*1*1= 1
0,1,0= 1*1*3= 3
0,1,1= 1*2*3= 6
0,1,2= 1*3*1= 3
0,2,0= 1*1*2= 2
0,2,1= 1*3*1= 3
0,3,0= 1*1*1= 1
1,0,0= 1*1*6= 6
1,0,1= 1*1*4= 4
1,0,2= 1*1*1= 1
1,1,0= 2*1*3= 6
1,1,1= 2*2*1= 4
1,2,0= 3*1*1= 3
2,0,0= 1*1*4= 4
2,0,1= 1*1*1= 1
2,1,0= 3*1*1= 3
3,0,0= 1*1*1= 1　　合計; 66

でチェックしてみたのですが、どうしても「67」にはなれないのですが・・・?
（あら！修正されたんですね。安心しました。）

　「A005021」のコメントは、「Random walks」となっているので、とても驚いています。

　「A005021」が縦線が６本の時、横線を合計ｎ本引いた時のあみだくじのパターン数として
このサイトに繋がって、そこではRandom Walksの解説となっていたことに興味を持ち、どんな
内容なのか読んでみると、

　P_6と呼ばれる道（直線上６点A、B、C、D、E、F が並んでいる。）を、Aから出発し、
2*n+5(歩)にてFの地点に到着する酔歩のコースが何通りできるか？

ということらしい。

　ｎ＝1 なら、全部で７歩なので、次の５コースがあるという。

1;[A, B, A, B, C, D, E, F]
2;[A, B, C, B, C, D, E, F]
3;[A, B, C, D, C, D, E, F]
4;[A, B, C, D, E, D, E, F]
5;[A, B, C, D, E, F, E, F]

　そこで、ｎ＝2 なら、全部で９歩なので、全コースを構成してみた。

1;[A, B, A, B, A, B, C, D, E, F]
2;[A, B, A, B, C, B, C, D, E, F]
3;[A, B, A, B, C, D, C, D, E, F]
4;[A, B, A, B, C, D, E, D, E, F]
5;[A, B, A, B, C, D, E, F, E, F]
6;[A, B, C, B, A, B, C, D, E, F]
7;[A, B, C, B, C, B, C, D, E, F]
8;[A, B, C, B, C, D, C, D, E, F]
9;[A, B, C, B, C, D, E, D, E, F]
10;[A, B, C, B, C, D, E, F, E, F]
11;[A, B, C, D, C, B, C, D, E, F]
12;[A, B, C, D, C, D, C, D, E, F]
13;[A, B, C, D, C, D, E, D, E, F]
14;[A, B, C, D, C, D, E, F, E, F]
15;[A, B, C, D, E, D, C, D, E, F]
16;[A, B, C, D, E, D, E, D, E, F]
17;[A, B, C, D, E, D, E, F, E, F]
18;[A, B, C, D, E, F, E, D, E, F]
19;[A, B, C, D, E, F, E, F, E, F]

　この様に、次は、ｎ＝3 での１１歩でのコースづくりをやれば全部で、６６コース、同じく、ｎ＝4
での１３歩での２２１コース、ｎ＝5 での１５歩での７２８コース、････････････

と、ここに載せられている数のコースが次々と判明するということになっている様だ。

　まさか、あみだくじが酔っ払いの歩き方と繋がっているとは夢にも思わなかった。
(似てなくもないか？)


（追記）　moonlight さんからご投稿いただきました。（令和７年４月２３日付け）

　最近また「統計」絡みで、「あみだくじ」のどこを選ぶかは偏りがある系の話が沸いています。

　気になる記事があったので「確かめよう」としましたが、そもそも「あみだくじ」の数え上げが
判らないことに気がつきました。仕方がないので数えてみようとしたのですが...。

　例えば、縦の筋が4本で、横棒が3本の場合に、20通りかな？となったのですが、どうにも自
信が持てません。ただ、横棒が3本の場合で、縦の筋の本数を増やしていけば、似た計算で
漸化式的に数えられそうだと...。

　でもさっぱり要領を得ないので、例えば、「縦の筋が5本で横棒が6本入ったあみだくじ」の
総数はどう計算すれば良いか教えて下さい。




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

　「20通り」の数えあげで、「左に1本、中に0本、右に2本」が数えられていない気がします。
私の勘違いでしたらご容赦下さい。


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

　懐かしかったので自分でも、もう一度整理してみました。

　縦線が4本で横線がn本では(A088305)

gp > a(n)=(((3+sqrt(5))/2)^(n+1)-((3-sqrt(5))/2)^(n+1))/sqrt(5)
gp > for(n=1,10,print(n";"round(a(n))))

1;3
2;8
3;21
4;55
5;144
6;377
7;987
8;2584
9;6765
10;17711

　縦線が5本で横線がn本では(A261547)

gp > b(n)=(3^(n+1)-1)/2
gp > for(n=1,10,print(n";"b(n)))

1;4
2;13
3;40
4;121
5;364
6;1093
7;3280
8;9841
9;29524
10;88573

　縦線が6本で横線がn本では(A005021)

c(n)={S=[];}for(i=0,n,for(j=0,n-i,for(k=0,n-i-j,\
S=concat(S,[binomial(i+j,j)*binomial(j+k,k)*binomial(n+1-j,n-(i+j+k))]))));vecsum(S)
gp > for(n=1,10,print(n";"c(n)))

1;5
2;19
3;66
4;221
5;728
6;2380
7;7753
8;25213
9;81927
10;266110

　なお、縦棒が6本での横軸n本でのあみだくじの本数がA005021での解説では P_6と呼ばれ
る道（直線上６点A、B、C、D、E、F が並んでいる。）を、Aから出発し、2*n+5(歩)にてFの地点
に到着する酔歩のコースが何通りできるか？ に同じとある。

　よって、横棒2本では、2*2+5=9歩で進む実例を構成すると、

1;[A, B, A, B, A, B, C, D, E, F]
2;[A, B, A, B, C, B, C, D, E, F]
3;[A, B, A, B, C, D, C, D, E, F]
4;[A, B, A, B, C, D, E, D, E, F]
5;[A, B, A, B, C, D, E, F, E, F]
6;[A, B, C, B, A, B, C, D, E, F]
7;[A, B, C, B, C, B, C, D, E, F]
8;[A, B, C, B, C, D, C, D, E, F]
9;[A, B, C, B, C, D, E, D, E, F]
10;[A, B, C, B, C, D, E, F, E, F]
11;[A, B, C, D, C, B, C, D, E, F]
12;[A, B, C, D, C, D, C, D, E, F]
13;[A, B, C, D, C, D, E, D, E, F]
14;[A, B, C, D, C, D, E, F, E, F]
15;[A, B, C, D, E, D, C, D, E, F]
16;[A, B, C, D, E, D, E, D, E, F]
17;[A, B, C, D, E, D, E, F, E, F]
18;[A, B, C, D, E, F, E, D, E, F]
19;[A, B, C, D, E, F, E, F, E, F]

と計算の通り19パターン構成可能なので、縦棒が5本である時はP_5と呼ばれる道（直線上5点
A、B、C、D、E が並んでいる。）を、Aから出発し、2*n+4(歩)にてEの地点に到着する酔歩のコ
ースが何通りできるか？と上のパターンを参考に、今度は2*2+4=8歩で進み

1;[A, B, A, B, A, B, C, D, E]
2;[A, B, A, B, C, B, C, D, E]
3;[A, B, A, B, C, D, C, D, E]
4;[A, B, A, B, C, D, E, D, E]
5;[A, B, C, B, A, B, C, D, E]
6;[A, B, C, B, C, B, C, D, E]
7;[A, B, C, B, C, D, C, D, E]
8;[A, B, C, B, C, D, E, D, E]
9;[A, B, C, D, C, B, C, D, E]
10;[A, B, C, D, C, D, C, D, E]
11;[A, B, C, D, C, D, E, D, E]
12;[A, B, C, D, E, D, C, D, E]
13;[A, B, C, D, E, D, E, D, E]

の13通り（計算上一致)がすぐに探すことができます。

　だから、縦棒4本のときはP_4と呼ばれる道（直線上4点A、B、C、D が並んでいる。）を、Aか
ら出発し、2*n+3(歩)にてDの地点に到着する酔歩のコースが何通りできるか？で処理され、
横棒2本では7歩で進み、

1;[A, B, A, B, A, B, C, D]
2;[A, B, A, B, C, B, C, D]
3;[A, B, A, B, C, D, C, D]
4;[A, B, C, B, A, B, C, D]
5;[A, B, C, B, C, B, C, D]
6;[A, B, C, B, C, D, C, D]
7;[A, B, C, D, C, B, C, D]
8;[A, B, C, D, C, D, C, D]

が見つかる。


　moonlight さんからのコメントです。（令和７年４月２４日付け）

　ありがとうございます。うっかり数え落としをしていた事が確認できました。行きつ戻りつの
順路数で数えられる理路はちゃんと確認できてませんが、Pythonでプログラムしてみて確か
に書かれている場合な数が得られる事は分かりました。

　次は記事にあった、縦棒8本横棒12本の場合に、あみだくじの行き先を場合わけして数え
る事が必要になります。

　「行きつ戻りつ」を1と-1のリストで数え上げる事はできたので、あとはそのリストからあみだ
くじを復元して行き先を確認すれば良いのですが... あみだくじの「復元」はどのようにすれば
良いでしょう？


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

　縦8本で横棒n本のときの異なるあみだくじの引き方は、次の計算で与えられそうです。

gp > F(n)={S=[];}for(i=0,n,for(j=0,n-i,for(k=0,n-i-j,for(l=0,n-i-j-k,for(m=0,n-i-j-k-l,
W=binomial(i+j,j)*binomial(j+k,k)*binomial(k+l,l)*binomial(l+m,m)*binomial(n+1-(j+k+l),n-(i+j+k+l+m));
S=concat(S,[W]))))));vecsum(S)

gp > for(n=1,12,print(n";"F(n)))

1;7
2;34
3;143
4;560
5;2108
6;7752
7;28101
8;100947
9;360526
10;1282735
11;4552624
12;16131656

　OEISで検索すると、「A005023」がヒットしました。従って、求めるべき値は16131656(通り)
では？

　私も酔歩とあみだくじを対応させようと試みたのですが、総数で一致しか言えないです。


　moonlight さんからのコメントです。（令和７年４月２４日付け）

　対応の仕方はこうじゃないか？というものに思い至りました。如何でしょう。
あとは仕方ないので, Pythonで一つ一つ数えるしか...。




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

　以下の考えはどうでしょうか？

　n本の縦線にm本の横線を引く場合、

・項数m
・各項の値は、1以上n-1以下
・任意の連続する2項について、a[i+1] > a[i]-2

という条件を満たす数列と一対一に対応すると思います。そして、そのような数列の個数は、
最後の項が何なのかで分類して漸化式が作れると思います。


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

　あみだくじで縦線がn本(n≧3)で横線がk本での作り方Tn(k)を漸化式で構成すると、

T3(k)=if(k==1,2,2*memorize(T3,k-1))
T4(k)=if(k==1,3,k==2,8,3*memorize(T4,k-1)-binomial(2,2)*memorize(T4,k-2))
T5(k)=if(k==1,4,k==2,13,4*memorize(T5,k-1)-binomial(3,2)*memorize(T5,k-2))
T6(k)=if(k==1,5,k==2,19,k==3,66,5*memorize(T6,k-1)-binomial(4,2)*memorize(T6,k-2)
　+binomial(3,3)*memorize(T6,k-3))
T7(k)=if(k==1,6,k==2,26,k==3,100,6*memorize(T7,k-1)-binomial(5,2)*memorize(T7,k-2)
　+binomial(4,3)*memorize(T7,k-3))
T8(k)=if(k==1,7,k==2,34,k==3,143,k==4,560,7*memorize(T8,k-1)-binomial(6,2)*memorize(T8,k-2)
　+binomial(5,3)*memorize(T8,k-3)-binomial(4,4)*memorize(T8,k-4))
T9(k)=if(k==1,8,k==2,43,k==3,196,k==4,820,8*memorize(T9,k-1)-binomial(7,2)*memorize(T9,k-2)
　+binomial(6,3)*memorize(T9,k-3)-binomial(5,4)*memorize(T9,k-4))
T10(k)=if(k==1,9,k==2,53,k==3,260,k==4,1156,k==5,4845,9*memorize(T10,k-1)
　-binomial(8,2)*memorize(T10,k-2)+binomial(7,3)*memorize(T10,k-3)
　-binomial(6,4)*memorize(T10,k-4)+binomial(5,5)*memorize(T10,k-5))
T11(k)=if(k==1,10,k==2,64,k==3,336,k==4,1581,k==5,6954,10*memorize(T11,k-1)
　-binomial(9,2)*memorize(T11,k-2)+binomial(8,3)*memorize(T11,k-3)
　-binomial(7,4)*memorize(T11,k-4)+binomial(6,5)*memorize(T11,k-5))

*スピードアップを計るためメモ化して処理しています。
縦の本数が多くなると初期値をいくつか集めないといけないので、この辺が面倒か？

縦の本数

-3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11(本)

横の本数; で見て下さい。

1;2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
2;4 | 8 | 13 | 19 | 26 | 34 | 43 | 53 | 64
3;8 | 21 | 40 | 66 | 100 | 143 | 196 | 260 | 336
4;16 | 55 | 121 | 221 | 364 | 560 | 820 | 1156 | 1581
5;32 | 144 | 364 | 728 | 1288 | 2108 | 3264 | 4845 | 6954
6;64 | 377 | 1093 | 2380 | 4488 | 7752 | 12597 | 19551 | 29260
7;128 | 987 | 3280 | 7753 | 15504 | 28101 | 47652 | 76912 | 119416
8;256 | 2584 | 9841 | 25213 | 53296 | 100947 | 177859 | 297275 | 476905
9;512 | 6765 | 29524 | 81927 | 182688 | 360526 | 657800 | 1134705 | 1874730
10;1024 | 17711 | 88573 | 266110 | 625184 | 1282735 | 2417416 | 4292145 | 7283640
11;2048 | 46368 | 265720 | 864201 | 2137408 | 4552624 | 8844448 | 16128061 | 28048800
12;4096 | 121393 | 797161 | 2806272 | 7303360 | 16131656 | 32256553 | 60304951 | 107286661
13;8192 | 317811 | 2391484 | 9112264 | 24946816 | 57099056 | 117378336 | 224660626 | 408239530
14;16384 | 832040 | 7174453 | 29587889 | 85196928 | 201962057 | 426440955 | 834641671 | 1547129284
15;32768 | 2178309 | 21523360 | 96072133 | 290926848 | 714012495 | 1547491404 | 3094322026 | 5844716616
16;65536 | 5702887 | 64570081 | 311945595 | 993379072 | 2523515514 | 5610955132 | 11453607152 | 22025185281
17;131072 | 14930352 | 193710244 | 1012883066 | 3391793664 | 8916942687 | 20332248992 | 42344301686 | 82836630954
18;262144 | 39088169 | 581130733 | 3288813893 | 11580678656 | 31504028992 | 73645557469 | 156404021389 | 311063682160
19;524288 | 102334155 | 1743392200 | 10678716664 | 39539651584 | 111295205284 | 266668876540 | 577291806894 | 1166646177136
20;1048576 | 267914296 | 5230176601 | 34673583028 | 134998297600 | 393151913464 | 965384509651 | 2129654436910 | 4371207361885


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

　まだ何の検証もしませんが... Python でプログラムして数えた分布がこうなりました。
「1282735」は総数の筈ですが、皆さんの数値と合ってないような気がします...

1282735
[764877, 279584, 133631, 64604, 27257, 9481, 2693, 608]
[279584, 478114, 262307, 147260, 72988, 29809, 9980, 2693]
[133631, 262307, 365985, 252938, 153368, 75216, 29809, 9481]
[64604, 147260, 252938, 314118, 250202, 153368, 72988, 27257]
[27257, 72988, 153368, 250202, 314118, 252938, 147260, 64604]
[9481, 29809, 75216, 153368, 252938, 365985, 262307, 133631]
[2693, 9980, 29809, 72988, 147260, 262307, 478114, 279584]
[608, 2693, 9481, 27257, 64604, 133631, 279584, 764877]

　Pythonで組んだものはなかなか処理が終わらないので、Claudiにお願いしてJuliaに書き直
して貰って実行するとそこそこの時間で結果が出ました。

--start---------------------------------------
8 12
--Ans-------------------------------------------

16131656
[9188341, 3508269, 1778834, 939616, 451633, 184261, 63000, 17702]
[3508269, 5568480, 3238722, 1961381, 1086206, 507952, 197646, 63000]
[1778834, 3238722, 4168532, 3074842, 2048283, 1130230, 507952, 184261]
[939616, 1961381, 3074842, 3550353, 3019342, 2048283, 1086206, 451633]
[451633, 1086206, 2048283, 3019342, 3550353, 3074842, 1961381, 939616]
[184261, 507952, 1130230, 2048283, 3074842, 4168532, 3238722, 1778834]
[63000, 197646, 507952, 1086206, 1961381, 3238722, 5568480, 3508269]
[17702, 63000, 184261, 451633, 939616, 1778834, 3508269, 9188341]
--end-------------------------------------------

　この結果を使うと、「統計リテラシーのない者がカモられる時代がやってきた」というダイアモ
ンド・オンラインの記事にある、あみだくじの話の分布の部分を確認できます。

　GAI さんへ：「if(k==1,2,2*memorize(T3,k-1))」の読み方？が分かりません。これはもしかし
て、「if k=1 then 2 else 2*T3(k-1) endif」ということでしょうか？


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

　そうです。


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

　教えていただいた「行きつ戻りつ」の行程があみだくじに対応するという知恵を使ってPython
で組んだけど、遅すぎたのでClaudeにお願いしてJuliaに書き換えたもので無事に8筋12横棒の
あみだくじでは、何筋目を選んだ場合何筋目に至るかという数え上げはできましたが、「m筋n
横棒のあみだくじでi筋目を選んだ場合にj筋目に至るものは幾つあるか」は「どうすれば計算で
きるか」は解決していません。何とか計算で済ませることはできないものでしょうか？

　皆さんの助けを借りて少し取り組んだことをまとめたpdfをここに置いておきます。まだ解決し
ていませんのでもう少し助けて下さい。


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

　8筋12横棒のものを数列に対応付けます。

例えば、

┣┫┃┣┫┃┃┃
┃┣┫┃┣┫┣┫
┣┫┃┣┫┃┃┃
┣┫┣┫┃┣┫┃
┃┃┃┣┫┃┣┫

という形のもので考えます。

これの横線に番号を

・基本的に左にあるものから右にあるものへ、同じ列内では上にあるものから下にあるもの
　へ、順に番号を振る
・ただし、自分の上流に未採番のものがあれば、それが採番されるまで保留する

というルールで振っていきます。

・最左列の一番上のが1
・最左列真ん中は上流に未採番のものがあるので保留
・最左列下段は上流に未採番のものがあるので保留
・左から2列目のが2
・最左列真ん中は上流が採番されたのでこれが3
・最左列下段は上流が採番されたのでこれが4
以下略

　各番号が左から何列目にあるかを見ると、「1,2,1,1,4,5,4,3,4,7,6,7」という数列になります。

　この対応付けで、8筋12横棒のあみだくじと、1から7までの数を「どの項も前項-1以上」とい
う条件で12項並べる数列が一対一に対応します。

　よって、あみだくじの個数の代わりに後者を数えることにします。

1項並べる場合、
末尾が1のものが1個
末尾が2のものが1個
末尾が3のものが1個
末尾が4のものが1個
末尾が5のものが1個
末尾が6のものが1個
末尾が7のものが1個
合計7個

2項並べる場合、
末尾が1のものが1+1=2個
末尾が2のものが1+1+1=3個
末尾が3のものが1+1+1+1=4個
末尾が4のものが1+1+1+1+1=5個
末尾が5のものが1+1+1+1+1+1=6個
末尾が6のものが1+1+1+1+1+1+1=7個
末尾が7のものが1+1+1+1+1+1+1=7個
合計34個

3項並べる場合、
末尾が1のものが2+3=5個
末尾が2のものが2+3+4=9個
末尾が3のものが2+3+4+5=14個
末尾が4のものが2+3+4+5+6=20個
末尾が5のものが2+3+4+5+6+7=27個
末尾が6のものが2+3+4+5+6+7+7=34個
末尾が7のものが2+3+4+5+6+7+7=34個
合計143個

4項並べる場合、
末尾が1のものが5+9=14個
末尾が2のものが5+9+14=28個
末尾が3のものが5+9+14+20=48個
末尾が4のものが5+9+14+20+27=75個
末尾が5のものが5+9+14+20+27+34=109個
末尾が6のものが5+9+14+20+27+34+34=143個
末尾が7のものが5+9+14+20+27+34+34=143個
合計560個

あと8回分略

　手計算でも数分で終わるレベルなので、いくらPythonが遅い言語といっても一瞬だと思いま
す。

　あ、対応関係もでしたか。まあ、最後の番号ごとに「到着地点がどこになるものが何個」をわ
けて計上していけばどうとでもなると思います。


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

　DD++ さん、細かい解説をありがとうございます。

　「行きつ戻りつ」でも仰る「項数m・各項の値は1以上n-1以下・任意の連続する2項について、
a[i+1] > a[i]-2」となる有限数列を数える手法でも全部で何通りあるかを数えることはできて、コ
レまた仰る通り「全部で何通り」だけならいくら遅いPythonでも十分我慢できる時間で結果を教
えてくれます。（そして多分Juliaならもっとプログラムも書き易くて早い）
そのレベルの話は（面白いですけど）まぁある意味解決済みです。

　そうではなくて、8筋12横棒のあみだくじで, 4筋目を選んだときに至る筋が3筋目になるような
あみだくじは何通りあるか? を数えたいのです。でないと、記事にあるような「分布」はシミュレ
ーションでしか確認できませんから。
「ちゃんと数えてみたい」できれば「数式で（例え漸化式レベルでも）計算したい」という話です。
何とかならないでしょうか？

　DD++さんの仰る通りで、「どうとでもなった」結果は得られているのですが... あまりにも機械
頼りな数え上げなので...。


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

　ゴール位置も考えたい場合の計算例

3本目スタートの場合

1項並べる場合、
末尾が1のものが1個（3ゴールが1個）
末尾が2のものが1個（2ゴールが1個）
末尾が3のものが1個（4ゴールが1個）
末尾が4のものが1個（3ゴールが1個）
末尾が5のものが1個（3ゴールが1個）
末尾が6のものが1個（3ゴールが1個）
末尾が7のものが1個（3ゴールが1個）
合計7個（2ゴールが1個、3ゴールが5個、4ゴールが1個）

2項並べる場合、
末尾が1のものが1+1=2個（1ゴールが1個、3ゴールが1個）
末尾が2のものが1+1+1=3個（2ゴールが1個、3ゴールが1個、4ゴールが1個）
末尾が3のものが1+1+1+1=4個（2ゴールが1個、3ゴールが1個、4ゴールが2個）
末尾が4のものが1+1+1+1+1=5個（2ゴールが1個、3ゴールが3個、5ゴールが1個）
末尾が5のものが1+1+1+1+1+1=6個（2ゴールが1個、3ゴールが4個、4ゴールが1個）
末尾が6のものが1+1+1+1+1+1+1=7個（2ゴールが1個、3ゴールが5個、4ゴールが1個）
末尾が7のものが1+1+1+1+1+1+1=7個（2ゴールが1個、3ゴールが5個、4ゴールが1個）
合計34個（1ゴールが1個、2ゴールが6個、3ゴールが20個、4ゴールが6個、5ゴールが1個）

　例えば、末尾が4のものの場合、1つ横線が少ないやつの末尾5以下を全部合計してから、
ゴール4のものとゴール5のものの個数を入れ替えるという感じですね。


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

　最近C++によるプログラミングの勉強を始めたので、ご要望のものを一瞬で出力するコード
を書いてみました。（……掲示板にコード丸ごと載せちゃって大丈夫かな？）

　標準入力からnとmを入力してください。n≧3のみ対応、また結果が2^63を超えるとオーバ
ーフローすることには対処を放棄しています。Pythonで実行したければAIにでも翻訳しても
らってください。

-----
#include <bits/stdc++.h>
using namespace std;

int main () {

int n, m;
cin >> n >> m;
assert(n>2);

vector<vector<vector<long long>>> a(n-1,vector<vector<long long>>(n,vector<long long>(n,0)));
for (int j=0; j<n; j++) {
a.at(0).at(j).at(j) = 1;
}

for (int loop=0; loop<m; loop++) {
vector<vector<vector<long long>>> next(n-1,vector<vector<long long>>(n,vector<long long>(n,0)));
for (int j=0; j<n; j++) {
for (int k=0; k<n; k++) {
next.at(0).at(j).at(k) = a.at(0).at(j).at(k) + a.at(1).at(j).at(k);
for (int i=1; i<n-2; i++) {
next.at(i).at(j).at(k) = next.at(i-1).at(j).at(k) + a.at(i+1).at(j).at(k);
}
next.at(n-2).at(j).at(k) = next.at(n-3).at(j).at(k);
}
}
for (int i=0; i<n-1; i++) {
for (int j=0; j<n; j++) {
swap (next.at(i).at(j).at(i),next.at(i).at(j).at(i+1));
}
}
swap (a,next);
}

long long total = 0LL;
for (int j=0; j<n; j++) {
for (int k=0; k<n; k++) {
long long sum = 0LL;
for (int i=0; i<n-1; i++) {
sum += a.at(i).at(j).at(k);
}
cout << sum;
if (k==n-1) {
total += sum;
cout << endl;
} else {
cout << " ";
}
}
}
cout << "total:" << total << endl;

return 0;
}
-----

出力サンプル

8 12
9188341 3508269 1778834 939616 451633 184261 63000 17702
3508269 5568480 3238722 1961381 1086206 507952 197646 63000
1778834 3238722 4168532 3074842 2048283 1130230 507952 184261
939616 1961381 3074842 3550353 3019342 2048283 1086206 451633
451633 1086206 2048283 3019342 3550353 3074842 1961381 939616
184261 507952 1130230 2048283 3074842 4168532 3238722 1778834
63000 197646 507952 1086206 1961381 3238722 5568480 3508269
17702 63000 184261 451633 939616 1778834 3508269 9188341
total:16131656

5 30
69706010502882 64476946102498 61603155451959 58814544487309 54236041597325
64476946102498 62876755878626 61865352374327 60803099299213 58814544487309
61603155451959 61865352374327 61899682489401 61865352374327 61603155451959
58814544487309 60803099299213 61865352374327 62876755878626 64476946102498
54236041597325 58814544487309 61603155451959 64476946102498 69706010502882
total:308836698141973

（追記：インデント全部消えるんかーい！）


　moonlight さんからのコメントです。（令和７年４月２７日付け）

　DD++さん、対応頂き有難いのですが... 矢張り数え方は総当たりよりは素敵なのかもしれ
ませんがモヤります。


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

　モヤるとはどういう意味で仰っていますか？不満点を具体的にしていただかなければ何と
もしようがありませんが。


　moonlight さんからのコメントです。（令和７年４月２７日付け）

　既に書いた通り、ある意味問題は解決しているわけです。で、総当たりではない数え方を
という意味では、DD++ さんのご教授は大変参考になるのでは？と思いつつも、あまりに煩
雑で、本来の意味での「総当たり」ではないにせよ、各層では「総当たり」している感が強い...
というところがモヤるところなのかと自己分析しています。

　できうれば、もう少し簡潔にならないかなぁと。各層での「場合わけ」の定型化など... 難しい
というよりは表現が大変そうですけど...。


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

　煩雑な原因の大部分は、任意のスタートから任意のゴールへ行くパターン数をn^2個全部
出せという問題設定にあります。処理方法を変えたところで、そのn^2個という個数が減るわ
けではないので、その点はこちらではどうしようもないです。

　別表現を、というなら行列の累乗として表現もできると思いますよ。ただし、固有値はnの値
ごとに個別に求めるしかなくなるので、一般化からは遠ざかる方向になりますけど。


　moonlight さんからのコメントです。（令和７年４月２７日付け）

　単純な行列の累乗では無理だと思いますけど...それは兎も角、ネットの方には、更に高速化
されたプログラムを載せて下さってる方がいてとても「早い」です。どうなってるのか一寸詳しく
は分かりませんが...8筋20横棒でも一瞬で結果が出てきました。

　コレならもう「計算式」要らんやんと思ってしまいそうですけど、矢張りもっと規模が大きいと
無理でしょう（例えば30人のあみだくじで一人2本ずつ横棒入れるとか）から、できれば一般的
な計算式が構成できれば欲しいなぁと... （直接でなくて漸化式的なものでも... ）


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

　あみだくじの縦線の数がいくら多くなっても漸化式でその時の横線数kを指定してやれば、
あみだの総数を算出できる方法なら、ある手段で割とスムーズに構成できます。

　あみだの縦線が偶数本の時
(nをもっと大きくとっても可能です。polchebyshev(2*n+2,2) は、第２チェビシェフ多項式）

for(n=1,9,print(2*n+2";"subst(polchebyshev(2*n+2,2),x,t/2)))

4;t^4 - 3*t^2 + 1
6;t^6 - 5*t^4 + 6*t^2 - 1
8;t^8 - 7*t^6 + 15*t^4 - 10*t^2 + 1
10;t^10 - 9*t^8 + 28*t^6 - 35*t^4 + 15*t^2 - 1
12;t^12 - 11*t^10 + 45*t^8 - 84*t^6 + 70*t^4 - 21*t^2 + 1
14;t^14 - 13*t^12 + 66*t^10 - 165*t^8 + 210*t^6 - 126*t^4 + 28*t^2 - 1
16;t^16 - 15*t^14 + 91*t^12 - 286*t^10 + 495*t^8 - 462*t^6 + 210*t^4 - 36*t^2 + 1
18;t^18 - 17*t^16 + 120*t^14 - 455*t^12 + 1001*t^10 - 1287*t^8 + 924*t^6 - 330*t^4
　+ 45*t^2 - 1
20;t^20 - 19*t^18 + 153*t^16 - 680*t^14 + 1820*t^12 - 3003*t^10 + 3003*t^8 - 1716*t^6
　 + 495*t^4 - 55*t^2 + 1

　これで、縦線が4本の時は、t^4-3*t^2+1=X^2-3*X+1 とみて、=0 から、X^2=3*X-1 の式と
して、この時横線がk本である場合の求める総数をT4(k)で表し、この式から

　T4(k)=3*T4(k-1)-T4(k-2)

の漸化式を生み出す。使うためには、T4(1)=3、T4(2)=8 を与えれば良い。

　もし縦線が20本なら、

T20(k)=19*T20(k-1)-153*T20(k-2)+680*T20(k-3)-1820*T20(k-4)+3003*T20(k-5)
　+1716*T20(k-6)-495*T20(k-7)+55*T20(k-8)-T20(k-9)

の漸化式と、

T20(1)=19,T20(2)=208,T20(3)=1725,T20(4)=12051,T20(5)=74907,T20(6)=427924,
T20(7)=2294248,T20(8)=11709940,T20(9)=57483052,T20(10)=273438880

を与えれば良い。

　また、縦線が奇数本の時は、

gp > for(n=1,9,print(2*n+3";"subst(polchebyshev(2*n+3,2),x,t/2)/t))

より

5;t^4 - 4*t^2 + 3
7;t^6 - 6*t^4 + 10*t^2 - 4
9;t^8 - 8*t^6 + 21*t^4 - 20*t^2 + 5
11;t^10 - 10*t^8 + 36*t^6 - 56*t^4 + 35*t^2 - 6
13;t^12 - 12*t^10 + 55*t^8 - 120*t^6 + 126*t^4 - 56*t^2 + 7
15;t^14 - 14*t^12 + 78*t^10 - 220*t^8 + 330*t^6 - 252*t^4 + 84*t^2 - 8
17;t^16 - 16*t^14 + 105*t^12 - 364*t^10 + 715*t^8 - 792*t^6 + 462*t^4 - 120*t^2 + 9
19;t^18 - 18*t^16 + 136*t^14 - 560*t^12 + 1365*t^10 - 2002*t^8 + 1716*t^6 - 792*t^4
　 + 165*t^2 - 10
21;t^20 - 20*t^18 + 171*t^16 - 816*t^14 + 2380*t^12 - 4368*t^10 + 5005*t^8 - 3432*t^6
　 + 1287*t^4 - 220*t^2 + 11

　これから、例えば、縦線が17本なら、

T17(k)=16*T17(k-1)-105*T17(k-2)+364*T17（k-3)-715*T17(k-4)+792*T17(k-5)-462*T17(k-6)
　+120*T17(k-7)-9*T17(k-8) と
T17(1)=16,T17(2)=151,T17(3)=1100,T17(4)=6854,T17(5)=38480,T17(6)=200655,T17(7)=990756,
T17(8)=4692780

から横線数kをいろいろ変えて(初期値の求め方はDD++さんの方法で)

1;16
2;151
3;1100
4;6854
5;38480
6;200655
7;990756
8;4692780
9;21518464
10;96160636
11;420866416
12;1810911128
13;7683058880
14;32215438277
15;133749903324
16;550649378199
17;2250829575120
18;9143995148926
19;36950585233432
20;148629592843159

等が判明してくる。


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

　8筋20横棒どころか、30筋500横棒でも、私のアルゴリズムで1秒以内ですよ。ただ、C++で
2^63を超える数を扱うのはいろいろ面倒ですし、そんなデカい数を何千個も一覧出力する需
要はないと思ったので、オーバーフローへの対応をサボってるだけで。求めるものが概数で
よければ、コード中の「long long」と書かれている8箇所を全部「double」に書き換えれば、
10^308くらいまではすぐ対応できますが、そっちの方がよかったですか？

　一応、doubleへの書き換えをした上での、30筋500横棒対応の出力の、最初3行。全部見た
い方は以前投稿したコードの「long long」8か所を全部「double」に書き換えて、paiza.ioででも実
行してください。標準入力に「30 500」と入れて実行すれば、一瞬で全部出してくれます。

30 500
1.91318e+304 7.03258e+303 3.68362e+303 2.25787e+303 1.51266e+303 1.07205e+303
7.89158e+302 5.9652e+302 4.59462e+302 3.58607e+302 2.82409e+302 2.23627e+302
1.77531e+302 1.40923e+302 1.11579e+302 8.79137e+301 6.87716e+301 5.32915e+301
4.08166e+301 3.08311e+301 2.29171e+301 1.67253e+301 1.19554e+301 8.34624e+300
5.66958e+300 3.72827e+300 2.35477e+300 1.40994e+300 7.81054e+299 3.79149e+299
7.03258e+303 1.09241e+304 5.87978e+303 3.69338e+303 2.52801e+303 1.82552e+303
1.36614e+303 1.04793e+303 8.17924e+302 6.46161e+302 5.14587e+302 4.11754e+302
3.30103e+302 2.64478e+302 2.11264e+302 1.67864e+302 1.32374e+302 1.03367e+302
7.97502e+301 6.06579e+301 4.53826e+301 3.33238e+301 2.39561e+301 1.68122e+301
1.14757e+301 7.57952e+300 4.80621e+300 2.88793e+300 1.60476e+300 7.81054e+299
3.68362e+303 5.87978e+303 7.71461e+303 5.02038e+303 3.53913e+303 2.61979e+303
2.00249e+303 1.56466e+303 1.24139e+303 9.95288e+302 8.03405e+302 6.5095e+302
5.28011e+302 4.27738e+302 3.45271e+302 2.7709e+302 2.20594e+302 1.73824e+302
1.35269e+302 1.03729e+302 7.82063e+301 5.78407e+301 4.18604e+301 2.95596e+301
2.02917e+301 1.34718e+301 8.58238e+300 5.17835e+300 2.88793e+300 1.40994e+300
以下略。


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

　現在プログラムを参考にするべき記事にはPython やC#、C++の言語で記述されているも
のを多く見ます。自分もこの言語が使えたらいいなと思いながらも未だに手に付かずにいま
す。昔からPARIは我流で利用していますが、まだ知らない使い方も多く他の言語まで手を伸
ばす余裕がありません。

　DD++ さんは殆んど頭を利用する記事ばかりが多かったので、コンピュータは使われないの
かと思っていましたら、勉強中とは言いながら忽ち使いこなされていることに驚きました。さす
がです。

　ところで、moonlight さんが何気に30人がそれぞれ2本ずつ横線を入れあみだを作ったら･･･
の記事をみて（これは縦線30本、横線60本のあみだに相当と思い。）自分流に何通り作れる
か挑戦してみました。

　初期値を求める部分も、ある程度自動で求めれる様にプログラムしてやってみたら、何と
その総数が

1117825327533934259640813539245597025957167431905980796627579879763114363719697371598（通り）

となってしまいました。果たしてこの数字は妥当でしょうか？よかったら、DD++ さん、m=30、
n=60で確認してもらえませんか？


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

　30筋60本の総数とか30筋500横棒でも1秒以内とか素晴らしいのですけど...筋の対応表は
どうでしょうか？

　この話の発端は、「あみだくじの偏りを正確に数え上げる」ところにあるので、その辺りの
「数学的に明快な要領」を「納得したい」ところです。まぁ、プログラムのアルゴリズムの要領
でも良いのですけど。あと、C++を走らせる技量がない（というよりは使う気がない... ）ので、
困惑しています。


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

　もしこの数字が正しいとしての話なのですが、30人がランダムに2本ずつ横線を引く時点で、
構造的に同型であるものが十分に発生するので、どの線を引いた人がどの場所に落ち着くか
はその時その時で全部異なる結果を生むと思われます。

　ですから全員が同型とはならない様に引いたとして（偶然では決して起こらない。）もこんな
莫大なパターンが起こせるので、これを全部調べる気が起こらない。

　例えば、縦に3本横に2本なら、異なるくじは4通り出来て、

[1,2,3]->[1,2,3];2通り　、[1,2,3]->[2,3,1];１通り　、[1,2,3]->[3,1,2];1通り

の結果が生じる。

　縦に4本横に2本なら、異なるくじは8通り出来て、

[1,2,3,4]->[1,2,3,4];3通り　、[1,2,3,4]->[1,2,4,3];1通り　、[1,2,3,4]->[1,3,4,2];1通り
[1,2,3,4]->[1,4,2,3];1通り　、[1,2,3,4]->[2,3,1,4];1通り　、[1,2,3,4]->[3,1,2,4];1通り

　縦に5本横に3本なら、異なるくじは40通り出来て、

[1,2,3,4,5]->
12345; 2通り　、12354; 3通り　、12435; 6通り　、12543; 2通り　、13245; 6通り　、13452; 1通り
13524; 1通り　、14253; 1通り　、14325; 2通り　、15234; 1通り　、21345; 5通り　、21453; 1通り
21534; 1通り　、23154; 1通り　、23415; 1通り　、24135; 1通り　、31254; 1通り　、31425; 1通り
32145; 2通り　、41235; 1通り

　この様に調べてみると、1の下の1へ辿り着くパターンが圧倒的に多い感じがする。

　この様な分布が知りたいのですね。私はここまでは手で一つ一つ手で書いていって調べて
います。これを30人2つずつの横線で構成される全パターンでの分布など私の手に負えるも
のではありません。またそれを正確に出したとしても、私には1のくじの真下に辿り着くことが
最も起こり易いが感じられれば十分な気がします。手で調べた経緯を自動化するにはとは思
いますがどうやればよいのかは全くわからないです。moonlightさんと同じあみだくじでの興味
に違いがあるのですね。


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

　GAI さん、まあ、どう計算すれば作業量が減るか考える部分は、普通の数学となんも変わ
りませんからね。自分がやろうとしてる計算手順を言語化するだけで行ける範囲はわりとす
ぐでした。

30 1 で 29
30 2 で 463
30 3 で 5390
30 4 で 51171
30 5 で 420394
30 10 で 4.55989e+09
30 20 で 4.03578e+16
30 30 で 1.06671e+23
30 40 で 1.76862e+29
30 50 で 2.34175e+35
30 60 で 2.74243e+41 ←ご要望の
30 70 で 2.98696e+47
30 80 で 3.10927e+53
30 90 で 3.14275e+59
30 100 で 3.11465e+65

　60の場合、GAIさんの1.117825e+84とはだいぶ相違がありますね。もちろん、私の方が間
違ってる可能性もあります。GAIさんの方では他の横線本数ではどんな結果ですか？

　 moonlight さん、筋の対応表とは何を指しておっしゃってます？moonlight さんが上記で書
いている形式とほぼ同じもの（合計を先に出すか後に出すかと、括弧などの装飾が違うだけ）
を私も出しているのですけれど。これが筋の対応表ではないとおっしゃるなら、まず筋の対応
表とやらの実例を提示してください。

　漸化式の作り方も上記で説明していますし、筋の対応を求める方法への変更も上記で説明
しています。

　「この投稿のこの文章がわからないからもっと詳しく」とかなら対応のしようもありますが、
説明を投稿済のものに対して「いいから説明を書け！」とだけ言い続けるのは、ただあなた
に話を聞く気がないだけとしか思えません。

　私はあなたの先生でもないですし、あなたがどの程度の学力かも知りません。具体的な不
明点も言わずにただ喚くだけの人に、寄り添う努力をする義理もなければ、その手段も持っ
ていません。

　C++を走らせる気がないというのは、私が提示した「paiza.ioを開いてそこにコードを投げる」
という誰でも30秒でできることすらやるつもりがないということですか？

　「PythonがいいならAIに訳してもらえばいい」と言ったのも、やるのが面倒だから無視ってこ
とですよね。本人にそれらの手間すらかける気がないのであれば、きっとあなたには誰が何
をどれだけ説明をしても無駄なんでしょうね。


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

　横線数60までの可能数一覧
1;29
2;463
3;5390
4;51171
5;420394
6;3098862
7;20993804
8;132939015
9;796625654
10;4559889334
11;25112905580
12;133834729210
13;693377073900
14;3505338139380
15;17345898649800
16;892033314203139
17;27733773552429223
18;1118409311622637368
19;40443070417349370483
20;1527210370835118559332
21;56673976478816860747774
22;2117897601581472517771066
23;78923421248818203600565427
24;2944399943419196373497114774
25;109797106537775911758807162778
26;4095095417290316282939442547680
27;152723339720122501108555011840342
28;5695863174154192679028192753380340
29;212426436445814460576060868565141484
30;7922452345203935157114149652287687884
31;295467611549841015492082915284979621511
32;11019463714682126522890048157626008654473
33;410970741180874710387820391271814117039458
34;15327149785690207118885870323300255918993423
35;571625873548142874360678229042613943062115466
36;21318780749923986727127209867571593246051772792
37;795083690343313989839224384718429436112629600108
38;29652637460436628119426525781824034780378617858107
39;1105894785552205786432302749539159553666515145287222
40;41244333795790621245739946592147320794065883565680290
41;1538206972425500348947263126645174656249917797251481336
42;57367412016658739514161229915304087943069732860319297800
43;2139516996330777959490116551283833358117060754594797276832
44;79793262703232759273815095962367380584502386825047441842582
45;2975888849544976589836518005290872762652116689120004217680428
46;110985741713586389931309449649350862931122663738438389421170269
47;4139212009073395230798901086511848165112620340965868742219499787
48;154371866075172177263089105463100114315014887200826345809003180000
49;5757297037042150504612687946059868808701941641867529313983174674031
50;214718329288028117388183596542053732242317398732806011411150816078034
51;8007917714790557941233055393258000318873880099217751017200538624008158
52;298655202559982290915864096247122825932213134993383861881469194843760686
53;11138342474648737567533867624306069773630827219825309621513293889500901823
54;415404359338583563240822830410726177624082300119922772035644260066074468818
55;15492500984796742751657733290329634715839880609542698284110815714988820803522
56;577792652792786427263779283761230091891336037456469059968177339997587731768310
57;21548770592232778950593226336183306224619421016130072191215241776265825517607246
58;803661160785313324174825880131482661709940319330388414827929681984410805278529046
59;29972534098423254020758850854144560768881344890674163772909010594416675059756419112
60;1117825327533934259640813539245597025957167431905980796627579879763114363719697371598

の並びとなりました。


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

　15までは私と一致しています。「30 16 で 84235251439605」から一致しませんね。なんで
こんな半端なとこから？横線の本数が縦線の本数の半分を超えると何かあるんでしょうか？

　縦線8本の場合、

8 1 で 7
8 2 で 34
8 3 で 143
8 4 で 560
8 5 で 2108 ←ここからが食い違う？
8 6 で 7752

ってなるんでしょうか？


　moonlight さんからのコメントです。（令和７年４月２９日付け）

　折角興味深い算出法が... と思って大して努力はしてません、疑問を投げているだけなので
すが...一寸気が利いてなかったようで申し訳ありません。

　明らかにあみだくじの筋の選びようによる結果の分布には偏りがある事は明らかだという
のも別段否定したりはしません。その通りですから。ただ、数え方が怪しかったり数えられる
にも関わらずサボって恐らくは間違ったシミュレーションで語られるのは拙いなぁと。沢山あ
るあみだくじの話の大半はあみだの総数を(筋の数-1)^(横線の数)通りとしていて、多分その
根拠としている構成法を使ってシミュレーションしているでしょうから。だったら正確にシミュレ
ーションしようとすれば先ずは選ばれるあみだくじ全体の構成法がきちんとないとね、という
話です。そういう意味では「行きつ戻りつ」を攫う事できちんと構成できるという話はとても有
難い「教え」でした。とはいえ別段皆さんを「先生」だと思ってるわけではありません。お知恵
を拝借して助けて貰おう、あわよくば更に新しい知見を見出せれば♪という思惑です。そも
そも最近の先生は「きちんと教える」事ができないようで、「やり方」を仕込む事を仕事だと
か教育だと心底思ってる人が大半らしいですからそういう「先生」呼ばわりするなんてとても
失礼だとも思ってます。

　ところで、議論する中身としては小さな規模のあみだくじで十分だと思うので、何故計算が
食い違うのかも含めて、アルゴリズムの確認ができないものでしょうか？


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

　何度も言っていますが、私はアルゴリズムの全容を既に全部書いてます。「確認ができない
でしょうか」も何も、あとはあなたが読んで確認するだけです。

　不明点を具体的に挙げてもらえば協力はできますが、そうではなくただ駄々をこねるだけ
の人にしてあげられることはありません。


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

　再挑戦！これではどうでしょうか？

1;29
2;463
3;5390
4;51171
5;420394
6;3098862
7;20993804
8;132939015
9;796625654
10;4559889334
11;25112905580
12;133834729210
13;693377073900
14;3505338139380
15;17345898649800
16;84235251439605
17;402316301124360
18;1893310678517700
19;8793147391736136
20;40357786347273252
21;183266905331524344
22;824255034747971688
23;3674950883378678800
24;16255421882564830140
25;71384840041723959608
26;311418663604915014072
27;1350375077353954614384
28;5823041821257562590120
29;24981782165889424128048
30;106671345686835109102032
31;453501538615221120120097
32;1920247373753821060916773
33;8100476665368181748160571
34;34052954042136508229919042
35;142690568445704254905970971
36;596112426258621587933361150
37;2483369892192881694636148630
38;10318473866094099974679219796
39;42768516724584960514403750335
40;176862366945026630666520869874
41;729813126230735455341470281926
42;3005456846790981942293708712036
43;12353359966837224339431413442178
44;50685607079444329323255005077044
45;207613079229358124452968845335380
46;849058280539586545208387260201240
47;3467146895324531934103815498948841
48;14138241146010198255730566783356800
49;57575916461409965986900847410036600
50;234174867066415421926684291204186160
51;951312375045376858090381562585181640
52;3860263877836478670013758164200228880
53;15647593976660949236650911300126253200
54;63363471704000869756678505803691947360
55;256338444794052835483998138135784555640
56;1036079462632519082207654384813062022800
57;4184049118051380918526064679844187838320
58;16882762634340248602038470164697874805280
59;68069225361124124594166026380622389476240
60;274242739789885194337625897729987657084960


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

　それであれば、私の結果と一致していると思います。（全部を精査したわけではないですが）


　moonlight さんからのコメントです。（令和７年４月２９日付け）

　DD++さんの仰る通りに Claude におねがしてみました。何も余分なことを訊かずにDD++ さ
んのプログラムを投げたところ、
---------------------------------------------------------------------------
　このプログラムは２つの整数 n と m を読み込み、(n-1)×n×nサイズの３次元配列を作成
して、それに対して m 回の変換操作を行います。初期状態では、最初の層の対角要素がす
べて1に設定されています。各変換操作は主に2つのステップで構成されています：

累積フェーズ：現在の状態から値を合計して次の状態を構築します
交換フェーズ：各層で隣接する要素を交換します

　すべての反復が終わった後、プログラムは各位置の合計値を計算して出力し、最終的な
合計も表示します。
---------------------------------------------------------------------------
とプログラムを解析してくれましたが、細かい点の解説はまだ訊けてません。

　で、Juliaで書き換えてもらいました。30筋60横棒の場合に負の数が現れた（整数型のオー
バーフロー）ので、それも書き直して貰いました。

　プログラムを動かしてみたところ、既に結果が判っているものと合致しています。そして早い。
これなら十分実用範囲内です。あとは、ここで数えた「あみだくじ」から無作為に選び出して「試
す」ことができれば、あちこちにある杜撰そうなシミュレーションではなく、正確なシミュレーション
が実行できるというわけですね。ありがとうございます。

　アルゴリズムというかプログラムの本質はコレから読んで「分かる（というより解説できる？）」
努力をしてみます。

　claudeにプログラムの解説をお願いしてみました。

　Juliaに書き換えたものを解説して貰っていますがアルゴリズム的には同じ事でしょう。
---------------------------------------------------------------------------
　あみだくじを数えるプログラムのアルゴリズムについて、関数ごとに解説します。
　このプログラムは、あみだくじの可能な組み合わせ数（または経路数）を計算するものです。
各関数の役割と背後にあるアルゴリズムを説明します：

count_amidakuji(n, m) 関数・・・この関数は全体の処理を管理しており、以下のようなステッ
プで動作します：

初期化:

n本の縦線と、それらを横線でつなぐ構造を考えます
3次元配列 a[i, j, k] を作成します：

i: 横線の層を表します（1からn-1まで）
j: 出発点を表します（1からnまで）
k: 到達点を表します（1からnまで）

最初は、a[1, j, j] = 1 として、出発点jから同じ位置jに到達する経路が1つあることを表します

反復操作（m回）:

各反復は、横線（あみだくじの「横棒」）を1本追加する可能性をシミュレーションします
大きく分けて「累積フェーズ」と「交換フェーズ」があります：

a. 累積フェーズ:
next[1, j, k] は、最初の層と2番目の層の値を合計します
中間層の next[i, j, k] は、前の層からの累積値と次の層の現在値を合計します
これにより、経路数が下から上へと累積されていきます

b. 交換フェーズ:
各層iにおいて、位置(j,i)と(j,i+1)の値を交換します
これは、横線が引かれたときに経路がどのように変化するかを表現しています

最終計算:
すべての反復が終わったら、各出発点jから各到達点kへの経路数の合計を計算します
特に最後の列（k=n）への経路の総数が「total」として計算されます

main() 関数
この関数は単にユーザーインターフェースを提供します：

ユーザーから入力値n（縦線の本数）とm（横線の追加回数）を受け取ります
大きな計算になる場合の警告を表示します
count_amidakuji(n, m) を呼び出して計算を実行します

アルゴリズムの数学的解釈
　このアルゴリズムは、あみだくじの組み合わせを直接生成するのではなく、動的計画法を使
用して経路数を効率的に計算しています：

　配列 a[i, j, k] は、i層目で出発点jから到達点kへの経路数を表します
横線が引かれると、隣接する経路が交換されます（交換フェーズ）
層が追加されるごとに、経路数は累積されます（累積フェーズ）
m回の反復後、最終的な経路数が計算されます

　特に、このアルゴリズムは、あみだくじを「排他的な横線の組み合わせ」として効率的にカ
ウントしています。すべての可能な組み合わせを列挙するのではなく、数学的に経路数を計
算するので、大きな入力値に対しても比較的効率的に動作します。
ただし、時間計算量はO(m×n³)なので、非常に大きな値に対しては計算時間が長くなる場合
があります。それに対応するため、BigInt型を使用して数値のオーバーフローを防いでいます。
----------------------------------------------------------------------------
　何となく「漸化式的」と表現していましたが、「動的計画法」と呼ぶのですね。説明は抽象的
ですが多少は分かり易いので確認してみます。


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

　 大きな計算になる場合の警告を表示します

　ここは（AIが何か足したのでなければ）n>2 でなかった場合の警告のことですかね？これは
大きな計算になるからではなく、n=2 だと途中でクラッシュするので入れています。n=2 の場合
は明らかに1通りしかないので、特別対応する価値もありませんし。

　それ以外はAIの解釈であっています。

　方針は、漸化式であってますよ。DP（動的計画法）⊃漸化式　なので、DPと呼んでもいいだ
けです。


　moonlight さんからのコメントです。（令和７年４月２９日付け）

　DD++ さん、返信ありがとうございます。ここまでで理解した内容をpdf にまとめたものと、
Julia のプログラムをJupyter Notebook にしたものをこちらに置きました。あとは、この「ちゃ
んと数えたあみだくじ」で「無作為に1つ選ぶ」ということができるかどうかです。Claude には訊
いてみたのですが、怪しいプログラムが返ってきたところで、無料枠を使い切ってしまったの
で続きは後日です。

　m筋n横線の場合に(m-1)^nという杜撰な数え方をしていれば、「無作為に1つあみだくじを
選ぶ」のも実に簡単なのですが... それは一寸許せないので何とかしたい。できそうな気はす
るのですけど...。


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

　無作為に選ぶ、というのはあみだ1人分じゃなく、全員分の対応関係を同時に取りたいって
ことですか？それだとまた根本的に別のコードが必要そうですが。

　あと、確率という意味では、むしろ(n-1)^mでやる方が正確さは上じゃないかなあという気が
します。

　PDFを拝見しました。言われてみれば確かにAIの言う「層」という表現が謎ですね。

　このiは、あみだくじで最後に引いた線は左から何本目の右に引かれているか、です。

　i=3なら、最後（番号付け的な意味で）の線が左から3番目と4番目の間に引かれているもの
を意味します。酔歩モデルなら、最後の右下移動は、左下から数えて3本目を通った場合と
いう意味に対応するかな？


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

　moonlight さんへ質問です。

　10人で各一本ずつ好きな場所に横線を入れ横線の総数が10本である場合、第一行が左
端（くじ棒1）を選んだ時全部で4292145通りのあみだくじのパターンのうち、この10人がどの
パターンを作っているかは知る由もないが(そのどれかにはなっているはず。）くじの行き先
が左から最終的にくじの1,2,3,･･･,10番へと至る総数を知らせる。第２行が選んだくじが2番で
ある場合の最終の到達場所になっています。以下同様

横線総数10;
2797793, 895375, 368825, 152326, 55475, 16989, 4315, 889, 142, 16
895375, 1886974, 858064, 400591, 167993, 59769, 17877, 4456, 904, 142
368825, 858064, 1553894, 840565, 413847, 172825, 60764, 18016, 4456, 889
152326, 400591, 840565, 1388969, 834802, 418154, 173782, 60764, 17877, 4315
55475, 167993, 413847, 834802, 1318601, 833690, 418154, 172825, 59769, 16989
16989, 59769, 172825, 418154, 833690, 1318601, 834802, 413847, 167993, 55475
4315, 17877, 60764, 173782, 418154, 834802, 1388969, 840565, 400591, 152326
889, 4456, 18016, 60764, 172825, 413847, 840565, 1553894, 858064, 368825
142, 904, 4456, 17877, 59769, 167993, 400591, 858064, 1886974, 895375
16, 142, 889, 4315, 16989, 55475, 152326, 368825, 895375, 2797793
total: 4292145(通り)

横線総数20;(各自2本ずつ勝手に横線を書き入れた場合)
1206969885175, 444626687408, 223944116341, 123985414511, 68419073997, 35219432968,
16356793415, 6802760919, 2521009672, 809262504
444626687408, 736976131952, 404974329652, 244129892658, 146778115239, 82292337422,
41427338639, 18559662466, 7368931802, 2521009672
223944116341, 404974329652, 552089840963, 377497635883, 254748110156, 159277066729,
88500743423, 43260170378, 18559662466, 6802760919
123985414511, 244129892658, 377497635883, 454051817726, 360453569477, 259933003640,
163318227538, 88500743423, 41427338639, 16356793415
68419073997, 146778115239, 254748110156, 360453569477, 407940958106, 354592769176,
259933003640, 159277066729, 82292337422, 35219432968
35219432968, 82292337422, 159277066729, 259933003640, 354592769176, 407940958106,
360453569477, 254748110156, 146778115239, 68419073997
16356793415, 41427338639, 88500743423, 163318227538, 259933003640, 360453569477,
454051817726, 377497635883, 244129892658, 123985414511
6802760919, 18559662466, 43260170378, 88500743423, 159277066729, 254748110156,
377497635883, 552089840963, 404974329652, 223944116341
2521009672, 7368931802, 18559662466, 41427338639, 82292337422, 146778115239,
244129892658, 404974329652, 736976131952, 444626687408
809262504, 2521009672, 6802760919, 16356793415, 35219432968, 68419073997,
123985414511, 223944116341, 444626687408, 1206969885175
total: 2129654436910(通り)

横線総数30;;(各自3本ずつ書き入れた場合)
496647560097440001, 200445588666012991, 111899880246277899, 69792696535021405,
44738672491416379, 27922874500844965, 16258458172179943, 8597168046702841,
4054782107743644, 1643303416611824
200445588666012991, 282712254410516606, 174876883331777285, 118941996483630956,
82376641820193608, 55272922570250507, 34417898391400316, 19315501555853237,
9586514942872742, 4054782107743644
111899880246277899, 174876883331777285, 203125589064861508, 157132397723195171,
120882336138695072, 89132275101361093, 60473442328480160, 36565510743047626,
19315501555853237, 8597168046702841
69792696535021405, 118941996483630956, 157132397723195171, 166300290157052329,
146258783232882355, 121111693187082065, 91313328069327192, 60473442328480160,
34417898391400316, 16258458172179943
44738672491416379, 82376641820193608, 120882336138695072, 146258783232882355,
151780229152448736, 142524556085077112, 121111693187082065, 89132275101361093,
55272922570250507, 27922874500844965
27922874500844965, 55272922570250507, 89132275101361093, 121111693187082065,
142524556085077112, 151780229152448736, 146258783232882355, 120882336138695072,
82376641820193608, 44738672491416379
16258458172179943, 34417898391400316, 60473442328480160, 91313328069327192,
121111693187082065, 146258783232882355, 166300290157052329, 157132397723195171,
118941996483630956, 69792696535021405
8597168046702841, 19315501555853237, 36565510743047626, 60473442328480160,
89132275101361093, 120882336138695072, 157132397723195171, 203125589064861508,
174876883331777285, 111899880246277899
4054782107743644, 9586514942872742, 19315501555853237, 34417898391400316,
55272922570250507, 82376641820193608, 118941996483630956, 174876883331777285,
282712254410516606, 200445588666012991
1643303416611824, 4054782107743644, 8597168046702841, 16258458172179943,
27922874500844965, 44738672491416379, 69792696535021405, 111899880246277899,
200445588666012991, 496647560097440001
total: 982000984280251892(通り)

　もし当たりがどのくじの元に設定されているかが事前に判明しておれば、全体的にどんな
あみだくじ状態になっているかはわからなくても、確率的にはその当たりのくじの番号に相当
する籤を選ぶのが当たりを引ける戦略だ。

　ということは可能性の総数の比較より論理的に言えるのですよね。（当然全体的くじの構造
によってはハズレも十分にあり得ますが・・・)の解釈はいいんでしょうか？


　moonlight さんからのコメントです。（令和７年４月３０日付け）

　DD++ さん、見て頂いてありがとうさんです。「間違ったこと」は書いてないでしょうか？i の受
け取り方を間違えていたのでしょうか？まぁ「どの方向？操作？から見るか」で表現は変わり
そうだとは思いましたが...。

　GAIさん、もちろんm^{n-1}でザックリ数えても凡その結果というか傾向は分かるので、勿論
それでも「良い」のかも知れませんが、私的には「嘘」を伝えているようでとても「気持ち悪い」
です。まぁ統計自体が「嘘八百」ばかり（現実問題に対応するには致し方ない部分があるとは
いえ）なのでどうしようもないのかも知れないし、webの記事や御本とか見ても鈍感さに慣れっ
こになっているのかも知れませんけど... 数えられるときは「数えられるけどこちらの概算で大
体わかるから「ちゃんとしたこと」は別途調べて／これは杜撰な数え方での集計だけど大体
は掴めるから正しくはないけどコレで話を進めます」みたいなことはちゃんと書いておいて欲
しいなぁと。（このあみだくじの話の場合は、杜撰な数え方を根拠にした抽出をしてるから余
計に救い難い... ）

　で、こういう『有難い場所』で「きちんと数えるということはどういうことか」が議論され、そこ
そこ纏められていれば、気になる人は調べられるだろうから良いかなぁと。そんなことを思っ
ています。


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

　「これは杜撰な数え方での集計だけど・・・」と書かれていましたが、これはDD++ さんがつく
られたプログラムをPARIのコードに読みかえて実行すると、例えば、縦数5本、横数3本では

25, 10, 4, 1, 0
10, 15, 10, 4, 1
4, 10, 12, 10, 4
1, 4, 10, 15, 10
0, 1, 4, 10, 25
total: 40

と結果が返されます。

　これは勿論異なるあみだ数が40通り存在することを教えると同時に、上の5×5行列に現
れている各数の意味は、5本のくじを左から1,2,3,4,5番と呼ぶとき、籤1番を選ぶと結果的に
1に戻ってくるものが40パターン中25個、2へ辿り着くのが10個、3には4個、4には1個、5は存
在しない。
　籤2番を選ぶと結果的に1には10個、2は15個、3は10個、4は4個、5は1個 以下、籤3、4、5
が選ばれた時の行き先の度数が同時に判明しています。

　これは実際40通りにあみだを作ってみて、それがどの様な結果が起きて、40パターンの総
計として結果を整理すると、正しくここに掲げられた表と一致するのです。ここにプログラムが
掲載される前にその作業をしていたので、このプログラムがその結果と一致しているのをみ
てこのプログラムのありがたみを痛感しました。

　moonlight さんも「m筋n横棒のあみだくじでi筋目を選んだ場合にj筋目に至るものは幾つあ
るか」は「どうすれば計算できるか」は解決していません、とそんな数値を渇望されていたでは
ありませんか？正確なシミュレーションをあれほど望んであったのでは？

　したがって、このプログラムを活用すれば正確に例の結果が求まるのです。けっして杜撰
な数え方での集計ではないのです。

　だからこれに私的には「嘘」を伝えているようでとても「気持ち悪い」です、との発言をされて
いることに、一体どんなことを求められているのだろうとの疑問が湧きます。


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

　私も、あみだくじの総数としてはmoonlightさんの数え方を支持しますが、確率として求める
なら逆にmoonlightさんの主張の方が杜撰だと思います。

　例えば、左からi本目とi+1本目の間に引かれる横線の本数の期待値を考えてみます。

　例えば、4筋2横線の場合、moonlightさんの考えるやり方では、

1本目と2本目の間：5/16本　、2本目と3本目の間：3/8本　、3本目と4本目の間：5/16本

となり、真ん中に偏って横線が引かれます。これは本当にランダムにあみだくじを作っている
と言えるのでしょうか？

　あ、AIによる解釈は多少表現方法に「ん？」と思うところがある（層とか）以外は間違ってな
いと思います。最後の計算でi=2のときがおかしいところはmoonlightさんが正しくやり直してい
ますし。あとは、n≧4の場合はn=3の場合にはない事象（i=1に対しての計算でi=3の分を足さ
ない）が発生するので、その例も出してもらうといいかもしれませんね。


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

　GAIさん、「杜撰な数え方」というのはここで皆さんが提示して下さった、「同じ」ものは省いて
数えたもの（DD++さんのも勿論）ではなく、隣同士の置換で済ませるm筋n横線なら(m-1)^nと
してしまう方です。読み難くて申し訳ない。（どこで誤解されたかもまだ特定してません... ）

　DD++さんの「moonlightさんの主張の方が杜撰」というのは...例えば、ここで紹介して貰った、
「m-1以下の自然数を階差が-1以上であるようにn個並べる数の列」で言えば、その中から
「無作為に選ぶ」場合に、m=4、n=3 だと

1-1-1, 1-1-2, 1-1-3, 1-2-1, 1-2-2, 1-2-3, 1-3-2, 1-3-3,
<==無条件なものから 1-3-1が除かれている
2-1-1, 2-1-2, 2-1-3, 2-2-1, 2-2-2, 2-2-3, 2-3-2, 2-3-3,
<==無条件なものから 2-3-1が除かれている
3-2-1, 3-2-2, 3-2-3, 3-3-2, 3-3-3
<==無条件なものから 3-1-1, 3-1-2, 3-1-3, 3-3-1 が除かれている

の21通りから選ぶ事になります。でも数の列を見ていれば、1,2,3 が各桁に入る分布は均等
ではなく、

どの数↓ 1 2 3 ←何番目
1 | 8 6 5　　|| 19
2 | 8 9 8　　|| 25 ←2だけ多い...
3 | 5 6 8　　|| 19
計 | 21 21 21←こちらが全部同じなのはまあ当然として

となる(2が多めに入っている)のだから「杜撰」だという、そういう事でしょうか？

　でもちゃんと数えているし、コレらは重複しないし、この中から選ぶのですから「同じように
選ばれる」としておかしくないですよね。そしてこれは、m筋n横本のあみだくじと対応している
わけですから... どう「杜撰」なのかが気持ち的には「わからないでもない」のですけど、分かり
ません。

　あと少し前の投稿の「無作為に選ぶ、というのはあみだ1人分じゃなく、全員分の対応関係
を同時に取りたいってことですか？」ですが... ちょっと上手く読み取れませんでしたが、「あみ
だくじが無作為に選ばれて、全員が筋を選ぶ、ということをした場合に、そのあみだくじによ
る結果というのか全員の対応も同時に分かる／分かりたい」ということです。
（で、それを統計的に処理するっていうことをしないと... となるのだろうかなぁ... )

　無作為に選ぶのは「1回だけ」です。コレで良いでしょうか？


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

　確率を考える場合、重複するものを別個で考えた方がいい場合があります。

　例えば、区別のつかないサイコロを２つ同時に振る場合。

　目の出方は21通りです。しかし、根元事象はサイコロの区別ができない場合でも３６通りと
すべきなのは明らかです。

　あみだくじの場合、例えば、4筋2横線で左の2本と右の2本の間に1つずつ横線があるパタ
ーンはどう扱うべきでしょう。

　パターン数としては合わせて1でいいと思いますが、根元事象としては２つと数えるべきだと
思います。

　全員分の対応を同時に取りたいのかというのは、例えば、１本目を選んだ人が１本目にた
どり着く結果を得るときに、同時に他の人がどういう結果だったのかでさらに細かく分類する
必要があるのかどうかということです。


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

　DD++さん、「根元事象としては２つ... 」のところが全く分かりません... どう考えればそうなるの
でしょう。

　あみだくじを知っている人に、何種類ありますかと聞けば多くの人は「重複しない数え方」を取
るのではと。同じですから。（あみだくじの区別をそのあみだくじで辿る経路、1>2>3>2>3>4のよ
うな、どの筋を順に辿るか、の辿り方の集合として区別すれば... という事になるのかなぁ... ）

　サイコロの場合はよく問題にあるように、大小２つのサイコロなどと「区別」をすれば明らか
に３６通りとなりますが...あみだくじの場合はどう見れば？「根元事象としては２つ... 」となるの
でしょう...。

　「全員分の対応を同時に取りたいのか」については... 分かりましたが分かりません... 「あみ
だくじには偏りがあることを知っているのは統計リテラシー」系の記事では当然「当たりの筋
を知って」いれば「その筋に近い筋を選ぶこと」が得策とありますが、その説明に必要なデー
タが欲しいわけですから... そういう意味では、あみだくじの全ての場合で、「その筋に近い筋
を選ぶこと」が得策って本当か？を検証するためのデータが必要だという話です。


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

　どう考えればも何も、普通にm^(n-1)通りで数えた方が同様に確からしい事象になると考え
るからですが。


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

　話はずいぶん遡りますが、単純な行列の累乗で分布が逐次計算できる事が分かりました。
無理だなんて適当な発言をして申し訳ない。状態遷移行列、或いはグラフ理論だと隣接行列
の累乗で計算できるのですねぇ。やっとそこまで追い付きました。

　隣接行列は正方行列で上でも下でも三角成分を全て1としてその反対側の対角成分から
1つ横にある成分も1として残りは全て0という綺麗な形の行列です。

　ただその累乗の各成分を表す式が...3次の場合はフィボナッチ数列そのもので、4次の場合
は3の累乗で簡単に表現できるのですが... 5次だともうお手上げです。

　確かにプログラム任せで必要な分だけ計算させる方が実用的なのかもとも。


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

　はい。このサイトでは1年前に既にそこまで議論済なのでした。


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

　そうだったのですね。流し読みではさっぱり分かりませんでした。そうなると、矢張り5次以上
は隣接行列の累乗を簡単に計算するのは無理そうだという結論ですか？


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

　5次「以上」かどうかはわかりません。5次は無理そうですが、もっと大きいところでたまたま
できるところはあるかもしれませんし。また、「簡単に計算する」という意味にもよりますね。

　各成分をnを用いた表記にするのは難しいでしょうが、機械計算で求めるのはある程度容
易いでしょうし。

　さらに言えば、対応関係まで取りたい場合は3筋や4筋でも行列のサイズは大きくなるでしょ
うし。



　　以下、工事中！