包除原理 - inamori’s diary

100未満の自然数を考えます。2の倍数または3の倍数の個数を数えるとします。2の倍数は49個、3の倍数は33個あります。これをあわせると82個になりますが、16個ある6の倍数を重複して数えているので、これを82から差し引いて、66個となります。

`S`	を集合`S`の要素の個数とすると、

|A∪B| = |A| + |B| - |A∩B|

となります。
これに、Cも加えると、

|A∪B∪C| = |A| + |B| + |C| - |B∩C| - |C∩A| - |A∩B| + |A∩B∩C|

となります。一般に、和集合の要素の個数を求めるとき、奇数個の交わりなら足して、偶数個の交わりなら引いてやります。これを包除原理（Inclusion-exclusion principle）と言います。

100未満の自然数で2か3か5か7の倍数の個数を求めるのはこんなコードでしょうか。



from itertools import combinations
def gen_comb(a):

    for n in range(1, len(a) + 1):

        for a1 in combinations(a, n):

            yield reduce(lambda x, y: -x * y, a1, -1)
N = 100

def f(x): return (N - 1) / x if x > 0 else -( (N - 1) / -x)

print sum(map(f, gen_comb([2, 3, 5, 7])))

gen_comb([2, 3, 5, 7])は、2,3,5,7,-6,-10, ..., -210と出します。奇数個の積なら正、偶数個の積なら負で出します。

包除原理は非常に強力なので是非憶えましょう。例えばこんな問題も鮮やかに解けます。

n人が一つずつプレゼントを持ち寄ります。そのプレゼントを一旦集めてランダムに一人一つずつ配りなおします。このとき、誰も自分の持ってきたプレゼントを配られない確率は？

補集合を考えます。すなわち、誰かが自分のプレゼントを配られる場合の数を数えます。n人を1から順に番号を振ります。1の人が同じプレゼントを配られる場合の数をN₁、1の人と2の人が同じプレゼントを配られる場合の数をN₁₂などとします。そうすると、誰かが自分のプレゼントを配られる場合の数は、

N₁ + N₂ + ... - N₁₂ - N₁₃ - ... - (-1)ⁿN_12...n

となります。N₁は、自分以外は任意なので(n - 1) !です。ほかの人も同様に考えられるので同じパターンがn通りあります。N₁₂は、2人を除くと任意なので(n - 2) !です。このパターンは_nC₂通りあります。まとめると、

n(n - 1)! - _nC₂(n - 2)! + ... - (-1)ⁿ

全体の場合の数はn!だから、上をここから引いてn!で割ると、

P_n = 1 - 1 + 1 / 2! - ... + (-1)ⁿ / n!

という確率になります。これは、e^xのテーラー展開、

e^x = 1 + x + x² / 2! + ...

にx = -1を代入して途中で打ち切った形になっています。すなわち、

P_n -> 1 / e (n -> ∞)

となります。