😊出会いの泉😊

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

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

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

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

単純な行列の累乗では無理だと思いますけど...
それは兎も角, ネットの方には
https://github.com/shimizudan/20250427amida/blob/main/20250427AmidaCount.ipynb
で更に高速化されたプログラムを載せて下さってる方がいてとても「早い」です。
どうなってるのか一寸詳しくは分かりませんが...
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
等が判明してくる。

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で確認してもらえませんか？

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さんと同じあみだくじでの興味に違いがあるのですね。

> 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さんが2622番で書いている形式とほぼ同じもの（合計を先に出すか後に出すかと、括弧などの装飾が違うだけ）を私も出しているのですけれど。
これが筋の対応表ではないとおっしゃるなら、まず筋の対応表とやらの実例を提示してください。

漸化式の作り方も2627で説明していますし、筋の対応を求める方法への変更も2631で説明しています。
「この投稿のこの文章がわからないからもっと詳しく」とかなら対応のしようもありますが、説明を投稿済のものに対して「いいから説明を書け！」とだけ言い続けるのは、ただあなたに話を聞く気がないだけとしか思えません。

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

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

縦線8本の場合、
8 1 で 7
8 2 で 34
8 3 で 143
8 4 で 560
8 5 で 2108 ←ここからが食い違う？
8 6 で 7752
ってなるんでしょうか？

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

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

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

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

再挑戦
これとはどうでしょうか？
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++さんの仰る通りに Claude におねがしてみました。

何も余分なことを訊かずにDD++さんのプログラムを投げたところ,
---------------------------------------------------------------------------------------------------------------------------------------------------------
このプログラムは2つの整数 n と m を読み込み、(n-1)×n×nサイズの3次元配列を作成して、それに対して 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型を使用して数値のオーバーフローを防いでいます。
----------------------------------------------------------------------------------------------------------------------------------------------------------------
何となく「漸化式的」と表現していましたが, 「動的計画法」と呼ぶのですね。
説明は抽象的ですが多少は分かり易いので確認してみます。

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

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

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

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

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

自分もあみだくじについていくつかの投稿をしていたのを記憶していたので調べてみたら
私の備忘録中の
数学・・・その他(数学についての雑学を・・・)
思い通りのあみだくじを作る方法　(右列上から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]
が見つかる。

ありがとうございます。
うっかり数え落としをしていた事が確認できました。
行きつ戻りつの順路数で数えられる理路はちゃんと確認できてませんが、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(通り)では？

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

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

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

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

まだ何の検証もしませんが... 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-------------------------------------------
この結果を使うと,
「統計リテラシーのない者がカモられる時代がやってきた」というダイアモンド・オンラインの記事
https://diamond.jp/articles/-/363654
にあるあみだくじの話の分布の部分を確認できます。

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

そうです。

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

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

https://amaryllis4u.wordpress.com/2025/04/26/標準的な「あみだくじ」である筋を選んだときに/

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が遅い言語といっても一瞬だと思います。

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

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

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

何とかならないでしょうか？

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のものの個数を入れ替えるという感じですね。

最近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

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

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

問題の解釈とプログラムが正しければ、ですが

F(x)=x/(1-x-x^2)　（|x|＜1）なので
F^(-1)(y)=(-y-1+√(5y^2+2y+1))/(2y)　（∵|x|＜1）
これに4～9を代入して
F^(-1)(4)=(-5+√89)/8
F^(-1)(5)=(-3+√34)/5
F^(-1)(6)=(-7+√193)/12
F^(-1)(7)=(-4+√65)/7
F^(-1)(8)=(-9+√337)/16
F^(-1)(9)=(-5+√106)/9
「xが有理数でF(x)が10000以下の正の整数値を取る」
⇔「yが10000以下の正の整数で5y^2+2y+1が平方数」
「yが10000以下の正の整数で5y^2+2y+1が平方数」を満たすyは
5個(2,15,104,714,4895)なので
「xが有理数でF(x)が10000以下の正の整数値を取る」を満たすxは
5個(1/2,3/5,8/13,21/34,55/89)

G(x)=(1+3x)x/(1-x-x^2)　（|x|＜1）なので（G(1/2)=5, G(2/5)=2では？）
G^(-1)(y)={-y-1±√(5y^2+14y+1)}/(2(y+3))　（y＜2）
G^(-1)(y)={-y-1+√(5y^2+14y+1)}/(2(y+3))　（y≧2）
これに4～9を代入して
G^(-1)(4)=(-5+√137)/14
G^(-1)(5)=(-3+7)/8=1/2
G^(-1)(6)=(-7+√265)/18
G^(-1)(7)=(-4+√86)/10
G^(-1)(8)=(-9+√433)/22
G^(-1)(9)=(-5+√133)/12
「xが有理数でG(x)が1000000以下の正の整数値を取る」
⇔「yが1000000以下の正の整数で5y^2+14y+1が平方数」
「yが1000000以下の正の整数で5y^2+14y+1が平方数」を満たすyは
14個(2,5,21,42,152,296,1050,2037,7205,13970,49392,95760,338546,656357)なので
「xが有理数でG(x)が1000000以下の正の整数値を取る」を満たすxは
14個(2/5,1/2,7/12,3/5,19/31,8/13,50/81,21/34,131/212,55/89,343/555,144/233,898/1453,377/610)

出題ミス（タイプミス)
G(2/5)=2 でした。
(G(1/2)=5）

このミスにも拘わらず
F(x)<10000での5個
G(x)<1000000での14個のxの有理数もすべて完璧に正解です。
上の5個がフィボナッチ数の有理数で構成されていくのに比べ
下の14個は偶数番目；1/2,3/5,8/13,21/34,55/89,144/233,377/610 がフィボナッチ数での有理数
そして奇数番目；2/5,7/12,19/31,50/81,131/212,343/555,898/1453 も疑似フィボナッチ数での有理数
で構成されるのが面白いです。

母関数から一気に逆関数を考えることが自分の方法と異なり、この手が最も効率よく進められることを
教えられました。

F(x)＜10000の5個の数列 2,15,104,714,…は A081018 にありますね。
よって問題がF(x)＜1000000000000000000000000000000000000000000000
であっても容易に答えられます（この場合54個）。
G(x)の方の数列 2,5,21,42,152,… はOEISにありませんが、
漸化式を立てれば同様に巨大数まででも答えられると思います。
ちなみに
前者の漸化式は a[1]=2, a[2]=15, a[n+2]=7a[n+1]-a[n]+1
後者の漸化式は a[1]=2, a[2]=5, a[3]=21, a[4]=42, a[n+4]=7a[n+2]-a[n]+7

・簡単な問題
上表の右列の式で、7番目の17に「*1」がありますが、
次に右列の式で「*1」が出てくるのは何番目の素数でしょうか。
また、中列で「*1」が出てくるのは何番目の素数でしょうか。

・やや難しい問題
右列で出てくる10個目の「*1」は、何番目の素数でしょうか。

・解けない問題
中列で出てくる7個目の「*1」は、何番目の素数でしょうか。

・簡単な問題
9551番目と6455番目の素数

・やや難しい問題
1;17
2;99551
3;4303027
4;6440999
5;14968819
までは見つけたがこの先10個も見つける自信なし
と思ってOEISの検索を掛けたらA046883を発見
カンニングで
12426836115943

・解けない問題
1;64553
2;64567
3;64577
4;64591
5;94601
6;64661
までは難なく見つかるが
これから先範囲を広げて捜索しても見つからず。
A236469に関連するか？

A046883(16) = 23540145178774772939
A046883(16) = p(540145178774772939)
A046883(17) = 39904678560078237431
A046883(17) = p(904678560078237431)
という情報をみつけましたが
OEIS にはエントリーされていないですね…

https://www.primepuzzles.net/puzzles/puzz_1083.htm

回答ありがとうございます。
簡単な問題→正解

やや難しい問題
カンニングで答える点は正解です。
ただし「何番目の素数」という問題なので、正解は426836115943です。
A046883の12426836115943だけを見ても
2426836115943なのか426836115943なのか26836115943なのか
確定しませんので、「何番目か」の数列であるA067248を見つけて
答えれば完璧でした。

解けない問題
見つかっている6個は
n=[p(n)/10]となっているわけですが、
この後はp(n)/nは10より大きくなって増加してしまうため、
7番目の値は初めて
n=[p(n)/100]となる値です。
（ただし、そのような値があれば、です。多分あるとは思いますが）
これについて計算してみると
約7.38202775×10^41番目の素数が
約7.38202775×10^43となり、その辺に答えがありそうです。
現在素数の正確な個数がわかっているのは10^29までのようですので、
当分は見つからないでしょう。

https://oeis.org/A006880/b006880.txt

10^29 まで……すごいですね、どれだけ時間かけたのでしょうか。

金７枚銀９枚のケースでは
６回の呪文詠唱で確実に偽コインを特定できると判明いたしました。
難しく考えていたためにどツボに嵌っていたようです。

お騒がせいたしました。

せっかくですので
金３枚銀５枚のケースで
呪文詠唱４回のやり方をひとつご案内させていただきます。

金をG1, G2,G3
銀をS1,S2,S3,S4,S5
とします。偽コインのありうるケースは15通りです。添付の図をご覧ください。

１回目の計測では①をカバーするように袋にいれて呪文を唱えます。袋が光れば、残り３回の呪文で①のなかにある偽コインペアを確定させる課題はイージーです。
１回目の計測で光らない場合には次のステップに行きます。

２回目の計測では②をカバーするように袋にいれて呪文を唱えます。袋が光れば、残り２回の呪文で②のなかにある偽コインペアを確定させる課題はイージーです。
２回目の計測で光らない場合には次のステップに行きます。

３回目の計測では③をカバーするように袋にいれて呪文を唱えます。袋が光れば偽コインペアは確定です。(G1:S5)
３回目の計測で光らない場合には次のステップに行きます。

４回目の計測では④をカバーするように袋にいれて呪文を唱えます。袋が光れば偽コインペアは確定です。(G2:S5)
４回目の計測で光らない場合には偽コインペアは確定です。(G3:S5)


なお、上記のやり方は容易に拡張できて
金7枚銀9枚のケースで呪文６回で済ませる方法があることがわかります。

金7枚銀9枚のケースの図解も作りました。
偽コインのペアが
⑤に含まれていれば残り５回の詠唱で確定。
さもなければ
④に含まれていれば残り４回の詠唱で確定。
さもなければ
③に含まれていれば残り３回の詠唱で確定。
さもなければ
②に含まれていれば残り２回の詠唱で確定。
さもなければ
①に含まれていれば残り１回の詠唱で確定。
さもなければ
※で確定
ということになります。

ふと思い立ちまして、
chatgpt-4o-latest-20250326 にたいして
下記のように出題しましたが、誤答を返して来ました。なお、英文なのはそのほうが生成AIにとって理解しやすいとわかったからです。
(誤答についてはナンセンスなので省略いたします。)
出題内容の下には、私がいま取り組んでいることも付記させていただきます。
皆さんにご助力を願えれば幸いです。よろしくお願い申し上げます。

♦出題内容♦
Fake Coins and a Magic Bag

You have a collection of 9 coins in total: 3 gold coins, 3 silver coins, and 3 bronze coins. Among these, exactly one gold coin, exactly one silver coin, and exactly one bronze coin are counterfeit.
Assume that the three coins of each metal are distinguishable (e.g., labeled G_1, G_2, G_3, S_1, S_2, S_3, B_1, B_2, B_3).

You are provided with a magic bag that has the following property:
When you place any subset of coins into the bag and cast a spell, the bag glows if and only if the subset contains all three counterfeit coins simultaneously, regardless of any additional genuine coins that might be included.

If the subset contains only one, only two, or none of the counterfeit coins, the bag does not glow.

All tests are deterministic and error-free. There are no restrictions on how many or which coins you may include in a single test, and coins may be reused in multiple tests.

Your task is to devise a strategy that is guaranteed to identify all three counterfeit coins using no more than 5 tests.

Justify your answer with a logical or mathematical argument.

♦出題内容はここまで♦

♥私が今もがいていること♥
この出題についてどのようなヒント(誘導)を追加すれば生成AI(chatgptなど)が正解に辿り着くか工夫をしているのですが悪戦苦闘しております。

皆さんに伺いたいのですが
なにか良いアイデアはないものでしょうか？

申し遅れました。
決定木を求めてほしかったんです。
下記の図のような。
分割統治戦略で二分木を作りそれぞれの枝において分析に必要な情報ビットが過度に大きくならないように。

↓これがそのXの数列(73→51)
oeis.org/A103876
↓これが対になる数列(73→22)
oeis.org/A357913

例えば740001は4桁ずつ区切って差をとると73であり73で割り切れますが、この数は137では割り切れません。

単に73の倍数を判定するなら
N=10*A+bが73の倍数<==>A+22*bが73の倍数
を使える。

例N=9012288(=10*901228+8)
901228+22*8=9012228+176=901404
同じく
90140+22*4=90228
9022+22*8=9198
919+22*8=1095
109+22*5=219
ここ辺りで219=73*3が判明
よって元の
N=9012288も73で割れる。(73*123456=N)

ちなみに137の倍数の判定では
N=10*A+bが137の倍数<==>A - 41*bが137の倍数
の原理が使える。

4桁ずらし差分と合わせると速そうですね。
9012288
2288-901=1387
138+22*7=292
29+22*2=73