😊出会いの泉😊

「実際の入試の原文」通りなのですが、明らかに誤字ですよね。ＨＰでは「数式」に修正しておきます。

まあ、防衛医大だと数学の専門家はいないでしょうから、そこらへんの正確さは蔑ろにならざるを得ないんでしょうねえ。

素数を2から約1億個を求めるのに、25秒でできます。(CPU:i5-2500)
経過時間= 0 分 25 秒
素数個数=105080509
まあ、ここでは、ふさわしい話でもないし、膨大なので、Webにもあげられないし、意味がないですね。
求めた最後の5個は、
2147117417　2147117419　2147117507　2147117509　2147117519
でした。

DD++ さん、誤りをご指摘いただきありがとうございます。
計算を見直したら、はじいてはいけない解をはじいていました。
（解）は修正しました。

n本の場合に刺し方がF(n)通りあるとする。
ただし、n=0の場合はF(0)=1とする。

まち針がn+1本ある時を考える。
特定の1本のまち針[赤]に着目し、その先端側にあるまち針の本数をi本、頭側にあるまち針の本数をn-i本とする(0≦i≦n)。
n本のまち針をこの2グループに分ける方法はCombination(n,i)通り。
先端側にあるi本のまち針の刺し方はF(i)通りで、その各々に対しまち針[赤]を刺す場所がi+1通り(針山とi本のまち針の頭)。
頭側にあるn-i本のまち針の刺し方はF(n-i)通り(まち針[赤]の頭を針山とみなせばよいため)。
よって漸化式は、
F(n+1) = Σ[i=0...n] Combination(n,i) * F(i) * (i+1) * F(n-i)
となる。

F(n)の式の形は予想できているので数学的帰納法で示せばよい。

……のですが、式変形できずに詰まっています。

そうなんですよ。

Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n

Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

このどっちかが成り立ってくれれば話は終わりなんですけど、
「私の備忘録」->「代数学分野」->「二項係数の性質」
にもそれっぽい式はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されていたら「よくある問題」なんですが、両方変わっていくのはほとんど見たことがありません。

どれが積でどれが添字か全くわからないので、添字は [ ] で書くなど区別しやすい表記にしてもらうことはできますか？

やっと情報を見つけました。
https://en.m.wikipedia.org/wiki/Cayley%27s_formula

こっちにある証明法がわかりやすかったので、この問題の用語や数値に合わせながら翻訳します。
https://en.m.wikipedia.org/wiki/Double_counting_(proof_technique)


まず、針山もまち針とみなします。
つまり「針山をまち針の頭に刺す」が、なぜかできそうな気分になっておきます。

以下の操作を行います。

(1) n+1 本のまち針（本当は針山であるものも含む）を机上に並べます。

(2) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(3) n+1 個の頭から 1 つを選びます。そして、その頭とつながっておらず、かつどこにも刺していない針先 n-1 個のうち 1 つを選びます。選んだ針先を選んだ頭に刺します。

(4) さらに繰り返し、合計 n 回行います。選べる針先の選択肢が 1 つずつ減っていき、n 回目では 1 個のうち 1 個を選んで刺すことになります。

(5) ある 1 本のまち針の頭に他の n 本が全部刺さっているオブジェ（木と呼びたいが根っこが刺さってない……）ができたら操作終了です。

各選択肢の個数を考えると、この操作の方法は全部で (n+1)^n * n! 通りあります。
ただし、同じ形のオブジェがまち針を刺す順番違いで n! 個ずつできるので、オブジェの種類は (n+1)^n 通りです。

そして、このオブジェには n+1 本の各まち針が一番下になるパターンが (n+1)^(n-1) 通りずつ含まれます。
つまり、まち針とみなしていた針山の上に本物のまち針 n 本が全部刺さって、きちんと題意通りの形になっているパターンは (n+1)^(n-1) 通りとなります。


これで「最長数列の総数」も解決したことになります。
あるいは、考え方を流用すれば「まち針の木」の問題に帰着させるまでもなくあっちを解けるかも。
上手い説明ができるかどうか考えてみます。

そして残った No.1051 の恒等式の謎。
組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

DD++さん
> そして残った No.1051 の恒等式の謎。
> 組み合わせを用いて証明できたことになりますが、式変形で示せるのかどうか。

式変形できました。
nCk を C[n,k] と書くことにします。

事前準備その１
C[n,i] * C[n-i,j] = C[n,j] * C[n-j,i]
（証明略）

事前準備その２
f(k)をkのn-1次以下の多項式として、
Σ[k=0...n] C[n,k] * (-1)^k * f(k) = 0
（証明は、「私の備忘録」->「代数学分野」->「二項係数の性質」の中の性質(5)と(28)、あるいは
　平成２３年１１月１９日から２６日にかけてのらいさん・攻略法さん・ａｔ さん・ＦＮさんのやりとり を参照）


それでは本番 (2行目から3行目の置き換えはh=n-k)
Σ[h=0...n] C[n,h] * (h+1)^h * (n-h+1)^(n-h-1)
= Σ[h=0...n] C[n,n-h] * (n-h+1)^(n-h-1) * (h+1)^h
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * (n-k+1)^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * ((n+2)-(k+1))^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * { Σ[m=0...n-k] C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-k-m) }
= Σ[k=0...n] Σ[m=0...n-k] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= Σ[m=0...n] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,m] * C[n-m,k] * (n+2)^m * (-1)^(n-m) * (-1)^k * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * { Σ[k=0...n-m] C[n-m,k] * (-1)^k * (k+1)^(n-m-1) }
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * 0
= (n+2)^n

おお、なるほど、そんな方法で k+1 の指数から k を消せるとは。
これで

> Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
>
> Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

の上の式は示されましたね。
下の式はりらひいさんの証明の 1 行目（ h をそのまま k に書き換え）と 3 行目を足したものが最終結果の 2 倍になることから得られます。

これらの総和、いつかどこかでまた使うことがあるかもしれないので、証明方法ともども覚えておきたいと思います。
ありがとうございます。

先日の式変形（No.1068）をもう一度眺めていて思ったのですが、次の式

(a+b)^n / a = Σ[k=0...n] C[n,k] * (a+k)^(k-1) * (b-k)^(n-k)

が成り立つんですね。
ただし、 a≠0とします。
計算は先日の3行目～最終行とまったく同様です。
先日の式は、 a=1, b=n+1 の場合にあたります。

a,bは整数に限らず実数でいけるのが面白いところですね。

ある本に、無限ということばが、自然に出ています。
限りなくとか、無数という言葉が、出てきます。形式主義と公理主義、
直観主義が、混雑しています。

https://shayashiyasugi.com/wwwshayashijp/HistoryOfFOM/Axiomatik/axiomatism.html

長いですが、興味がおありの方もいらっしゃることかと。

正しい指摘だと思います。

どう投げても、底面が上になることは、有り得ない。
それに、元々、サイコロというのは、どの面も合同でないと
サイコロの意味を成さないと思います。

> 四角錘
漢字は「四角錐」だと思います。

> 重心をどこにとれば、長さの比をどのようにすれば、いいのか？物理的な問題でしょうか？
四角錐の材質・床の材質・反発係数などが関係しそうな気がしますので、物理の問題で、しかも与えられた条件では答えが出せない気がします。


> どの面も合同でないとサイコロの意味を成さない
そうでもないと思います。例えば「両側を削った元々六角柱の鉛筆」のような形なら、削った円錐面が下になることがありませんので、ちゃんと（理論的には）確率1/6ずつのサイコロになると思います。

四角錐のサイコロは古代メソポタミアで実際に使われていたようですね。発掘されているとのこと。

ふと思ったのですが、
ニつの合同な正五角錐を、底面どうしで貼りつけた形状のものが実際には便利ではないかと。美的には十ある面が正三角形のものがよいかもですね。

「正双五角錐」という名前があるようですね。
https://www.wikiwand.com/ja/%E5%8F%8C%E8%A7%92%E9%8C%90
↑ここに「双五角錐」と書かれた図形がありますが、
見た感じ「正双五角錐」になっているようです。
この形だと平べったくなってサイコロのように振った時にどうかなと思ったのですが、
コマのように回せますのでかえって面白いかも知れませんね。

正ねじれ双五角錐によるサイコロというものがあるのでしたか。

https://ja.m.wikipedia.org/wiki/%E3%81%AD%E3%81%98%E3%82%8C%E5%8F%8C%E8%A7%92%E9%8C%90#/media/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%3A10-sided_dice_250.png

gp > for(n=1,10,print(n";",\
-sum(k=1,n+1,(-1)^k*k*binomial(n+1,k)*(n+1)^(n-k)), " VS ",n^n))

に関しては、{(n+1)-1}^n を二項展開した後少し変形しただけですかね。
nCk を含む総和公式は、
「底が k に依存しない」場合は二項展開の式で変数の中身をうまく選んだ式あることが多く、
「指数が k に依存しない」場合は二項展開の式に何か掛けたり割ったりしながら微積分を繰り返して作った式であることが多いです。

今にして思えば、/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
が得られました。