兼雑記

■[Misc] 包除原理

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

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

よくよく考えると簡単。 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 。

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

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

で、式変形して、

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

こんなもんでしょうか。

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

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