包除原理とオイラー関数について

TL;DR

自分なりに包除原理やオイラー関数について整理しておきたかったのでメモを書きます。正確な情報は文献抄を見たほうがいいです。

文献抄

• 包除原理の2通りの証明
• 包除原理の意味と証明
• 包除原理
• 組合せ論

包除原理

intersectionからunionに変換する公式。

ただし、$|A_i|$は集合iの要素数。

証明

正直自信がないです

$|A_1 \cup A_2 \cup A_3 ... A_{n-1} \cup A_n|$に属する任意の要素$x$について考えます。左辺では、要素$x$は1回のみ数え上げられます。

そこで、右辺では要素$x$はプラスマイナスを考慮して、$|A_{j_1} \cap A_{j_2} ... \cap A_{j_i}|$において何回数え上げられたかを考えます。$x$を含む集合の数を$k$とし、$x$を含む集合を$A_i (i \in k)$とします。$x$を含まない集合では、カウントが行われないので考えないものとします。

$A_i (i\in k)$においてカウントされる数は$_kC_1$です。ある2つの集合$A_i \cap A_j (i,j \in k)$においてカウントされる数は$_kC_2$です。同様にして$x$を含む$r$個の積集合の組み合わせの中で$x$がカウントされる数は$_kC_r$です。プラスマイナスを考慮すると

とかけます。一方、二項定理より

となるので、任意の要素$x$のカウント回数は左辺と右辺で等しいことが言えます。よって、成り立つはずです。

実装

これをメモしたかった。 bit全探索を使って書けます。

100以下の2, 3, 5の倍数について考えます。

fn main() {
    let nums = vec![2, 3, 5];
    let mut counter = 0;

    for bit in 0..1 << nums.len() {
        // 2進数のときの1の数をカウント
        let popcount = bit.count_ones();
        let mut mul = 1;

        for i in 0..nums.len() {
            if bit & 1 << nums.len() {
                mul *= nums[i]
            }
        }

        if mul == 1 {
            continue;
        }

        if popcount % 2 == 1 {
            counter += 100 / mul;
        } else {
            counter -= 100 / mul;
        }
    }

    println!("{}", counter)
}

倍数性がわかるので、素因数分解すれば互いに素な数を数え上げるのとかにも使えます。

オイラー関数 自然数N以下の互いに素な自然数の個数

任意の自然数$n$について、$n$と互いに素な$n$以下の自然数の数の個数を、$\phi(n)$と書く。

このとき、$n$の素因数を$p_i$とすると、

が成り立つ。

包除原理による証明

任意の$x (1 \leq x \leq k)$において、素数$p_i$の倍数かつ$n$以下の自然数の集合を$|A_i|$とする。このとき、$|A_i| = \frac{n}{p_i}$とかける（ex., 100以下の2の倍数は100/2個）。

また、一般に、任意の積集合において、

が成り立つ（ex., 100以下の10の倍数は2の倍数かつ5の倍数なので、100/(2*5)）。

ここで、和集合$|A_{j_1} \cup A_{j_2} \cup ... \cup A_{j_k} |$は、素数$p_{j_1},p_{j_2},...,p_{j_k}$の倍数を1個ずつカウントした集合であるので、

が示せればよい。

包除原理を使うと

となり示せた。

乗法的性質を使った証明

包除原理から離れてしまうが、個人的にはこっちのほうが理解しやすかった。

参考動画