包除原理

勉強したことをまとめましょう。

包除原理。http://www.me.ics.saitama-u.ac.jp/~hira/ex02d/ex02d_1.html から

|\neg{A}\cap\neg{B}\cap\neg{C}|=|ALL|-(|A|+|B|+|C|)+(|A\cap{B}|+|B\cap{C}|+|C\cap{A}|)-|A\cap{B}\cap{C}|

よくよく考えると簡単。 A でも B でも C でも無いものっていうのは、全体から A なものと B なものと C なものを引くと引きすぎちゃったから、 A かつ B なものと B かつ C なものと C かつ A なものを足すと足しすぎちゃったから、 A かつ B かつ C なものを引く。これは n 個に一般化可能。

で、今回の例では A さん B さん C さんが A' さん B' さん C' さんと swapping すると考えると、全体は 1 、 X さんが X' に行く確率を R(X) とすると R(A),R(B),R(C) は 1/3 が 3C1 個、で R(A) かつ R(B) は 1/3*1/2 が 3C2 個、R(A) かつ R(B) かつ R(C) は 1/3*1/2*1/1 で、足して引いて足して引いてで 1/3 。

で、これを一般化すると、

P(n)=\sum_{i=0}^n{{}_nC_i\frac{(n-i)!}{n!}}

面倒だからΣは足して引いて足して引いて…という演算記号だと思って下さい。ていうかそういう記号存在したと思うんですけどなんだったけか。あるいは引数が even なら 1 を、 odd なら -1 を返す関数。

で、式変形して、

P(n)=\sum_{i=0}^n{\frac{n!}{(n-i)!i!}\frac{(n-i)!}{n!}}=\sum_{i=0}^n{\frac{1}{i!}}

これを n→∞極限を取ると e^x の Taylor 展開で x=-1 を代入したものに他ならないので、

P(n\rightarrow{\infty})=\frac{1}{e}

こんなもんでしょうか。

追記: mimeTeX って prod と lim 無いのかな。

sin-xさんご鞭撻ありがとうございました。それと touch ./-i は ls * の出力がおかしくなっちゃうので私はスペース4つのファイルを作ってそれを chmod 000 してますがこれでは rm -f には勝てません。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h