当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２６年４月８日付け）
ｎ人の大会参加者にゼッケン番号として、１〜ｎを着け番号順に一列に並んでもらう。大会
説明後、一旦休憩をとり再び一列にランダムに集合順に並んでもらう。
さて、大会参加者が、９，１０，１１人であった場合、参加者全員がもとの順番とは全く異な
る位置に並んでしまう確率が最も高くなるのは、何人のときか？
（答） （参考） 「自然対数の底 ｅ の体感」
らすかるさんからのコメントです。（平成２６年４月８日付け）
直感的にわかりますか？大雑把に考えて、ある人が元の順番に並ぶ確率は、1/ｎ だから、
誰も元の順番に並ばない確率は、(1-1/ｎ)n → 1/e
直感的に考えて、「→ 0」とか「→ 1」ならば直感的に答えられますが、0と1の間のある値に
収束する場合はよくわかりませんよね。
この問題は、完全順列の確率が、偶数のとき単調減少で、1/e に収束し、奇数のとき単調
増加で、1/e に収束ということを知っていれば、10人とわかります。
具体的な計算は、round(9!/e)/9!=0.36787918…、round(10!/e)/10!=0.36787946…
round(11!/e)/11!=0.36787943…
ＡＢＣＤＥＦさんからのコメントです。（平成２６年４月８日付け）
直感的に考えるのは難しいと思います。人数が増えれば1人の人が前と違う番号になる確
率は増えるけど、より多くの人に対して成り立たないといけないから条件はきつくなります。
確率が増える要素と減る要素のどちらがきいてくるかの判断は難しいでしょう。完全数列に
ついての知識があれば、10人のときが最大とすぐにわかりますが．．．。
完全順列の総数を、P(ｎ)とする。すなわち、1、2、･･･、ｎ の順列 a1、a2、･･･、an で、すべ
てのk=1、2、･･･、ｎ に対して、ak≠k が成り立つような順列の総数をP(n)とする。
このとき、漸化式 P(ｎ+1)=ｎ｛P(ｎ)+P(ｎ-1)｝ が成り立つ。
説明の便宜上、ｎ=4 のときの式 P(5)=4｛P(4)+P(3)｝ を証明する。
a5は、1、2、3、4 のどれかであるが、どの場合も同じであるから、a5=4 とする。
(1) a4=5 のとき、a1、a2、a3 は、長さ3の完全順列だから、P(3)通りある。
(2) a4=1or2or3 のとき、a1、a2、a3 のうちの1つは5であるから、それを4に変えると、
a1、a2、a3、a4 は、長さ4の完全順列であるから、P(4)通りある。
従って、P(5)=4(P(4)+P(3))
P(ｎ+1)=ｎ｛P(ｎ)+P(ｎ-1)｝も同様に証明できる。
1、2、･･･、ｎ の順列 a1、a2、･･･、an が完全順列である確率をp(ｎ)とすると、p(ｎ)=P(ｎ)/ｎ!
P(ｎ+1)=ｎ｛P(ｎ)+P(ｎ-1)｝の両辺を(ｎ+1)!で割ると、
P(ｎ+1)/(ｎ+1)!=ｎP(ｎ)/{(ｎ+1)ｎ!}+P(ｎ-1)/{(ｎ+1)(ｎ-1)!}
即ち、 p(ｎ+1)=ｎ/(ｎ+1)･p(ｎ)+1/(ｎ+1)･p(ｎ-1)
これは、数直線上で考えると、p(ｎ+1)がp(ｎ)とp(ｎ-1)を結ぶ線分を、1：ｎ に内分する点で
あることを示している。ともかく、p(ｎ+1)は、p(ｎ)とp(ｎ-1)の間にある。
p(1)=0、p(2)=1/2 であるから、上記のことを使えば、
p(1)＜P(3)＜P(5)＜P(7)＜P(9)＜P(11)＜････＜P(10)＜P(8)＜P(6)＜P(4)＜P(2)
であることがわかるので、p(10) が最大となる。
これは、「p(ｎ+1)はp(ｎ)とp(ｎ-1)の間にある」だけからわかる。「p(ｎ+1)がp(ｎ)とp(ｎ-1)を結ぶ
線分を1：ｎ に内分する点である」を使えば、p(ｎ)の正確な値が出る。