完全順列になる確率

質問

n個のものをランダムに並び替えたときに完全順列になる確率は、nを1ずつ増やしたとき、
nが奇数から偶数に増えるとき：増加
nが偶数から奇数に増えるとき：減少
となりますが、これは直観的にはどうしてでしょうか。
ご回答よろしくお願いします。

http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97

回答No.5

stomachman

g[n]=ng[n-1]±1 (±はnが偶数なら+、奇数なら-)
という形に書いたときの±1の部分を、g[n-2]より前の結果を使わずに（使うとn!と同じ形になってしまう）説明できりゃワカッタ！となるんじゃないかと思うんですが、その説明が入り組みすぎても駄目でしょうね、きっと。もう少し考えてみたいので、しばらく締め切らないで頂けると有り難いです。

お礼

質問は当分の間は締め切らずにおきますので、ご安心(？)ください。むしろ、お手数をおかけしてしまい、すみません。

自分でもいちおう(失礼！)考えてはいるのですが・・・。奇数と偶数の違いは、2で割って1余るかどうかなので、No.1の表記でいう g[1]=0 が効いてくる、ということも考えてみました。ちょこっと( n が小さいとクリティカルに)だけど、とりあえず効いてくる。たとえば、No.2で説明していただいた、(1)のケースが帰納的に「選ばれ」続けた場合、偶数のときは、自然に完全順列ができあがるけど、奇数のときは、g[1]=0 のせいで最後は不動点になってしまう。n が大きいと、(1)のケースが選ばれ続ける確率は小さいので、g[1]=0 の影響はどんどん小さくなる。・・・みたいに考えたりもしたのですが、2つずつのペア同士で互換する場合のみを特別視しているような気がして、なんか胡散臭いんですよね。。。

2009/05/26(火) 20:41

補足

だいぶ時間が経ちましたので、締め切ります。自分には結局わからなかったので、あきらめようと思います。ストマック・マンさんには、何度もご回答いただき、ありがとうございました。

2009/07/15(水) 21:31

回答No.4

stomachman

いやはや、ANo.3について訂正の訂正です。とほほ。
p[n] = g[n]/f[n] = p[n-1]+((-1)^n)/f[n]
でした。

回答No.3

stomachman

またやっちまいました。ANo.1を訂正です。
g[1]=1
なんて書いてますけど、0に決まってますね。で、rじゃなくて
p[n] = g[n]/f[n] = p[n]-((-1)^n)/n
となる。これが1/eに収束するんですね。

回答No.2

stomachman

ANO.1のコメントを拝見しました。うーん、そういうことですか。感覚的にワカッタというのは、こりゃもう完全に主観的体験だからなあ。

g[n]=(n-1)(g[n-1]+g[n-2])
がどうして出てくるのか、ひとつの説明をしてみると…
　「n個の鍵をn個の鍵穴に突っ込むけれども、どれ一つとして鍵が鍵穴に合わない」という場合の数を数える話です。まず、n番の鍵をk番(k≠n)の鍵穴に突っ込むことに決める。（kは1～n-1が選べます。）そうすると、n番の鍵穴には残りのどの鍵を突っ込んでも良い訳ですが、
　(1)ここでn番の鍵穴にあえてk番の鍵を突っ込んだとしましょう。そうすると、k番とn番の鍵および鍵穴については話が終わってしまったので、残りのn-2個の鍵と鍵穴の完全順列だけ考えりゃいいからg[n-2]通りある。
　(2)ここでまずn番の鍵穴の番号を「k番」と書き換えてしまう。従ってこの鍵穴にはk番の鍵を突っ込んではいけない。（なので、(1)の場合とは重複しません。）さて、これで1～n-1番の鍵穴に1～n-1番の鍵を突っ込む話になったから、g[n-1]通りある。（もちろん、突っ込み終わったら、「k番」と書き換えた鍵穴の番号を元のn番にもどしておくんです。）
…ということ。でも、この話からは奇数だ偶数だということはなかなか出てきそうにありません。

　そこで、漸化式を通して「g[2]が小さい」ということの影響が伝播していく、という説明にした訳です。
　イーカゲンに言えば、g[2n]が「ほんのほんのちょっと小さめ」になるのは、g[2n-2]が「ちょっと小さめ」で、g[2n-1]は「ほんのちょっと大きめ」で、両者が打ち消し合った結果である、とでも申しましょうか。

お礼

1/e への収束スピードを考えると、完全順列へのなりやすさ・なりにくさの違いは、微々たるものなんですよね。それでも、なんで奇数と偶数で変わるんだろう、と疑問に思ってしまいました。このような変な質問に何度も回答いただき、ありがとうございます。もともとは、小島寛之さんの『数学の遺伝子』という本の中で、Venn図で包除原理を使った説明がなされており、不思議に思って質問させていただきました。
主観的には、まだわかったという感じがしないのですが、納得することにします。ありがとうございました。

※それにしても、極限に e が顔を出すのは不思議ですね。また、1/e という確率もずいぶん高いなあと思ってしまいます。nが増えると、なんとなくですが、シャッフルしたときに偶々不動点ができちゃうケースが多くなりそうな気がします。しかも、収束が速いのも、なんか意外に思えてしまいます。。。

2009/05/25(月) 21:10

回答No.1

stomachman

完全順列の場合の数をg[n]とし、また普通の順列の場合の数、すなわちnの階乗(n!)をf[n]とすると
g[1]=1, g[2]=1
g[n]=(n-1)(g[n-1]+g[n-2]) (n≧3)
f[1]=1, f[2]=2
f[n]=(n-1)(f[n-1]+f[n-2]) (n≧3)
と書けますから、両者はn=2のときの値だけの違いしかない。で、
r[n] = (f[n]-g[n])/f[n]
は
r[1]=0
r[n]=r[n-1]+((-1)^n)/(n!)
と書ける。n→∞でr[n]はe^xのテイラー展開(x=-1)になってる訳です。そして、この級数は((-1)^n)の因子があるんで、項をひとつ増やすたびに収束値1/eより大きくなったり小さくなったり交互に振動しながら収束に向かう。
　…というのが、はて、ご質問の確率 p[n] = g[n]/f[n] が振動する直感的説明になってるのかどうか、いや人に依ると思うんですけどね。

お礼

ご回答いただき、ありがとうございます。
たしかに、式の上からは、おっしゃるような説明になると思うのですが、自分にとっては直観的という感じがしないのです。すみません。組み合わせ論的な説明と言ったほうがよかったかもしれません。
完全順列になることを、大胆に「並べ替えた後バラバラになる」ととらえると、なぜnが奇数のときのほうが「バラバラになりにくく」、nが偶数のときのほうが「バラバラになりやすい」のか。また、nを増やしていくとき、(nの範囲を)奇数に限定した場合は、nが大きいほど「バラバラになりやすく」なり、(nの範囲を)偶数に限定した場合は、nが大きいほど「バラバラになりにくく」なるのか。・・・などのシンプルな説明ってないのでしょうか。。。

2009/05/24(日) 10:33

補足

すみません。1つずつ「ずらす」のも完全順列なので、さきほどお礼に書いた「バラバラになる」はあまりに大胆すぎたかもしれません。。。

2009/05/24(日) 12:01