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

TL;DR

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

文献抄

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

包除原理

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

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

証明

正直自信がないです

に属する任意の要素について考えます。左辺では、要素は1回のみ数え上げられます。

そこで、右辺では要素はプラスマイナスを考慮して、において何回数え上げられたかを考えます。を含む集合の数をとし、を含む集合をとします。を含まない集合では、カウントが行われないので考えないものとします。

においてカウントされる数はです。ある2つの集合においてカウントされる数はです。同様にしてを含む個の積集合の組み合わせの中でがカウントされる数はです。プラスマイナスを考慮すると

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

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

実装

これをメモしたかった。 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以下の互いに素な自然数の個数

任意の自然数について、と互いに素な以下の自然数の数の個数を、と書く。

このとき、の素因数をとすると、

が成り立つ。

包除原理による証明

やってることは正しい気がするが最後の式変形何がどうなった。

任意のにおいて、素数の倍数かつ以下の自然数の集合をとする。このとき、とかける（ex., 100以下の2の倍数は100/2個）。

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

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

ここで、和集合は、素数の倍数を1個ずつカウントした集合であるので、

が示せればよい。

包除原理を使うと

となり示せた。

乗法的性質を使った証明

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

参考動画