😊出会いの泉😊

今にして思えば、/n がついているのは最初の数を 1 に限定しているせいですね。
最初の数も任意にしてよいのであれば、最長数列の総数は (n!)^n 通りというとても整った結果になります。
また、計算方法も先頭の数は任意である方がやりやすそうです。

ということで、「まち針の木」の方で wikipedia から拾ってきた発想をこの問題用に書き直しつつ、「n まで使える場合の最長数列の総数は (n!)^n 通りである」の証明を以下に記述します。
No.1041 の内容と重複する部分も含みます。
わかりにくければ、トランプを使って実際に手を動かすと助けになると思います。


条件を満たすような数列を以下のような方法で作ることを考えます。

1 から n までのカードの組を n セット用意します。
それぞれを適当な順に積み重ねて、各山に 1 番から n 番までの番号をつけておきます。

最初に初項 a[1] として 1 以上 n 以下の数を選びます。
a[1] 番の山の一番上のカードを手に取り、書いてあった数字を a[2] とし、カードは破棄します。
a[2] 番の山の一番上のカードを手に取り、書いてあった数字を a[3] とし、カードは破棄します。
以下、同様に繰り返します。
a[m] 番の山の一番上を手に取ろうとしたら既にその山にカードがなかった場合、a[m] を末項として数列を終了します。

[例1] n=3, a[1]=1 で各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：2, 3, 1
の場合、数列は 1, 1, 3, 2, 2, 1, 2, 3, 3, 1 となります。

[例2] n=3, a[1]=1 で、各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：1, 2, 3
の場合、数列は 1, 1, 3, 1, 2, 2, 1 となります。

[例3] n=3, a[1]=1 で、各山が上から順に
1 番の山：1, 3, 2
2 番の山：2, 1, 3
3 番の山：1, 3, 2
の場合、数列は 1, 1, 3, 1, 2, 2, 1 となります。

n^2+1 項続く最長数列ができる場合というのは、n^2 枚ある全てのカードを破棄できる場合ということになります。
そして、
「最長数列の内容」
「全て破棄できるようにカードを積み重ねて a[1] を選ぶ方法」
が一対一に対応することは数列の作り方からすぐにわかるので、結局カードを全部破棄できるような場合の数を考えればいいことになります。

では、カードを全て破棄することに関していくつか考察を行います。

まず、この操作は a[1] と異なる数のカードで終わることは絶対にありません。
しかも、終わったときには必ず a[1] と同じ数のカードが全ての山から破棄されています。
なぜなら、どこかの山でカードが足りなくなるのは「全ての山から a[1] と同じ数のカードを引く」を達成し、最初の 1 回とあわせて a[1] 番の山からカードを引くのが n+1 回目になるとき以外ありえないからです。

そして、a[1] と異なる数のカードも全て破棄されるかどうかは、a[1] 番以外の山の一番下のカードだけ見ればわかります。

例えば [例1] の場合、まず、a[1]=1 なので 1 のカードは全て破棄されることがわかります。
次に、3 のカードは全て破棄されることもわかります。
なぜなら 3 番の山の一番下に 1 のカードがあり、「3 のカードが全て破棄されるまで 3 番の山の 1 のカードが破棄できない」という状態になっているからです。
終わるまでに必ず 1 のカードが全て破棄されるのですから、その前に 3 のカードが全て破棄されることも達成されなければなりません。
さらに、2 のカードも全て破棄されることがわかります。
なぜなら 2 番の山の一番下に 3 のカードがあり、「2 のカードが全て破棄されるまで 2 番の山の 3 のカードが破棄できない」という状態になっているからです。
終わるまでに 3 のカードが全て破棄されることは先ほど確認したので、その前に 2 のカードが全て破棄されることも達成されなければなりません。
よって、[例1] は、実際に数列を作ってみなくても、1 も 2 も 3 も全て破棄される、つまり最長数列ができることがわかります。

一方で [例2] の場合、3 のカードが全て破棄されることはありません。
なぜなら 3 番の山の一番下に 3 のカードがあり、「3 のカードが全て破棄されるまで 3 番の山の 3 のカードが破棄できない」という状態になっているからです。
一般に、a[1]≠x で x 番の山の一番下に x のカードがある場合、その山は絶対に残ってしまいます。
よって、[例2] は、実際に数列を作ってみなくても、最長数列にはならないことがわかります。

また、[例3] の場合も、2 および 3 のカードが全て破棄されることはありません。
なぜなら 2 番の山の一番下に 3 のカードがあり、同時に 3 番の山の一番下に 2 のカードがあるため、
「2 のカードが全て破棄されるまで 2 番の山の 3 のカードが破棄できない」
「3 のカードが全て破棄されるまで 3 番の山の 2 のカードが破棄できない」
という状態になっているからです。
一般に、このような依存関係のループが発生すると、それらの山は絶対に残ってしまいます。
（[例2] も単独でループしているとみなすことができます）
よって、[例3] は、実際に数列を作ってみなくても、最長数列にはならないことがわかります。

ループが存在しなければ、全ての数のカードについて直接的または間接的に a[1] と同じ数のカードを全て破棄する前にそちらを全て破棄する必要があり、最長数列ができることが確定します。
よって、最長数列になるどうかは、積み重ねるときに a[1] 番以外の山の一番下に来るカードでループが発生しないかどうかだけを考えればいいことになります。

さて、では、カードを無作為に積み重ねて初項も無作為に選んだ場合に、最長数列を作れる確率がどのくらいになるか考えます。

まず、無作為にカードを積み重ねつつ初項を無作為に選ぶ方法として以下の手順を採用します。

1 から n までのカード 1 組をシャッフルします。その後、1 番から n 番までの番号を 1 つ無作為に選び、この山の番号とします。
改めて別の 1 から n までのカード 1 組をシャッフルします。その後、1 番から n 番までの番号のうち重複しないものを 1 つ無作為に選び、この山の番号とします。
これを n 回繰り返すと、1 番から n 番までの山が完成します。
そして、最後に作った山の番号を a[1] として採用します。

この作り方であれば、n 個の山の積み重ね方 (n!)^n 通りと a[1] の選び方 n 通りの組、全 n*(n!)^n 通りの起こりやすさが同様に確からしいといえます。

ここで、確率 P[k] (0≦k≦n) を「この山の作り方で k 個の山を作った段階で、最後に残ることが確定した山がまだどこにもない確率」と定義します。
もちろん P[0]=1 です。

このとき 1 - P[k+1]/P[k] は「k 個の山を作った段階で最後に残ることが確定した山がまだどこにもないという条件のもとで、k+1 個目の山を作ったせいで最後に残ることが確定した山ができてしまう条件付き確率」です。

これは、0≦k≦n-2 の場合、k+1 個目の山をシャッフルしたときに一番下にきたカードが x だったとして、
・x 番の山が k 番目までにまだなく、その x 番をk+1 番目の山につけてしまった
・x 番の山が k 番目までにもうあり、「x 番の山の一番下のカードは y」「y 番の山の一番下のカードは z
」……と辿って行き着いた未使用番号を k+1 番目の山につけてしまった
のどちらかが起こる確率であり、つまりは一番下のカードが何であるかに関係なく残っている n-k 個の番号から特定の 1 個を引いてしまう確率になります。

よって、
1 - P[k+1]/P[k] = 1/(n-k)
なので、
P[k+1]/P[k] = 1 - 1/(n-k) = (n-k-1)/(n-k)
であり、
P[n-1] = (1/2)*P[n-2] = (1/2)*(2/3)*P[n-3] = …… = (1/2)*(2/3)*……*((n-1)/n)*P[0] = 1/n
となります。
最後に作る山は、どんな順序になっても、a[1] の選び方を考えれば確率に影響は与えません。
よって、
P[n] = P[n-1] = 1/n
です。

これで、「n 個の山を無作為に作り、初項 a[1] を無作為に選んだ場合に、最長数列を作れる確率は 1/n である」ことがわかりました。

ところで、この山の作り方は n*(n!)^n 通りが同様に確からしく作れる方法でした。
つまり、最長数列を作れるようにカードの積み重ねて a[1] を選ぶ方法がそのうち N[n] 通りであるとすると、古典的確率の定義より
N[n] / {n*(n!)^n} = 1/n
となります。

したがって分母を払って
N[n] = (n!)^n
が得られました。