メビウス反転公式についてのメモ

はじめに

会社の競プロ部の活動の一環として、メビウス反転公式についてまとめたいと思います。

メビウス反転公式といえばいわゆるメビウス関数はもちろん、累積和とか包除原理なんかも導ける汎用的な公式として有名ですが、どういろいろ導けるんだっけ？というのが私としては忘れがちですので、メモっておこうという記事になります。

まぁぶっちゃけ、内容としては次のWikipediaの記事にすべて含まれます。

メビウス反転公式

まず最初にメビウス反転公式を簡単におさらいします。設定は(個人的に)直感的な範囲で、公式が成立する一般的な状態までは拡げてないです。

有限な束$X=(X,\leq)$が与えられたとき¹、その閉区間全体$I(X) := \{[a,b] | \forall a,b \in X, a\leq b\}$上の整数値関数$F,G : I(X) \to \mathbb{Z}$に対して畳み込み$F\ast G$が次の式で定義されます。

$$ F \ast G : [a,b] \mapsto \sum_{a\leq z \leq b} F(a,z)G(z,b)$$ついで$I(X)$上の次のような関数$\zeta, \delta$を考えます。

$$ \zeta ([a,b]) = 1, \forall [a,b] \in I(X)$$

\delta ([a,b]) = \delta_{ab} = \left\{
\begin{array}{ll}
1 & (a = b) \\
0 & (a \neq b)
\end{array}
\right.

(このとき$\delta$は畳み込みに関する単位元になります)

さらに関数$\mu$を畳み込みに関する$\zeta$の逆元として定義します。

$$ \mu : I(X) \to \mathbb{Z} \ s.t. \mu \ast \zeta = \zeta \ast \mu = \delta$$関数$\mu$が存在するかは一見非自明ですが、つまりは$\zeta$を表す行列(=対角成分に1が並ぶ上半分行列)の逆行列になるわけで存在します。具体的に求めますと仮定から$\mu(a,a) = 1$であり、また$a<b$に対して

$$
\mu(a,b) \zeta(a,b) = \sum_{a\leq z \leq b}\mu(a,z) = \delta(a,b) = 0 \
\Rightarrow \mu(a,b) = -\sum_{a\leq z < b}\mu(a,z)
$$が成り立つので帰納的に計算できます。

このときメビウス反転公式は次の形で述べられます。$X$上与えられた2つの整数値関数$f,g$に対して

$$ g(x) = \sum_{a\leq x} f(a) \Leftrightarrow f(x) = \sum_{a\leq x} \mu(a,x) g(a)$$

特に左辺の総和は$\sum_{a\leq x} \zeta (a,x) f(a)$とも書けますので、$\zeta$と$\mu$の反転感が感じられるかと思います。

応用

以下、冒頭に触れたいくつかの応用の導出について確認します。

累積和

$i=1,\cdots,n$で添字付けられた整数列$\{a_1,\cdots,a_n\}=\{f(1),\cdots,f(n)\}$に対して$k$までの累積和$g(k)=\sum_{i\leq k} f(i)$を考えます。これは束$1\to 2 \to \cdots \to k$におけるメビウス反転公式の左式と一致しますので、右式を見ますと次の式が手に入ります。

$f(k)=\sum_{i\leq k} \mu(i,k)g(i)$

$\mu(k,k)=1$を念頭において$\sum_{i\leq j \leq k} \mu(j,k)=0$から帰納的に計算していくと、$\mu(i,k)$の値は下図の各$i$の下の値になります。

よって$f(k)=g(k)-g(k-1)$と求まります。これは累積和とその要素の関係としてよく見かける式かと思います。

メビウス関数

メビウスの反転公式として良く現れる$g(n)=\sum_{d|n} f(d)$について考えます。これは整除関係によって表される以下のような束に関するメビウス反転公式の左式となりますので、右式をみれば$f(n) = \sum_{d|n} \mu (d,n) g(d)$が分かります。

束の作り方からして結局$\mu(d,n)$の値は$\dfrac{n}{d}$にしか依存しないので、記号を濫用してこれを$\mu(\dfrac{n}{d})$と書いて右式を書き直せば$$f(n) = \sum_{d|n} \mu (d,n) g(d) = \sum_{d|n} \mu(d)g(\dfrac{n}{d})$$となり、メビウス関数による古典的なメビウス反転公式として見慣れたものが手に入ります。

では改めて$\mu(d)$の値を(雑に)求めましょう。まず互いに素な正整数$n,m$に対して$n\cdot m$の約数による束は$n$と$m$それぞれの束の直積であるため、$\mu(n\cdot m) = \mu(n) \mu(m)$であることが分かります(乗法的)。素数$p$に対しては$\mu(p) = -\mu(1) = -1$であるため、乗法的であることから相異なる素数$p_1,\cdots,p_k$に対して$\mu(p_1 \cdots p_k) = (-1)^k$であることが求まります。また同じ素数の冪に対しては$\mu(p^2) = -\mu(1) - \mu(p) = 0$であるため、平方因子$p$を持つ正整数$d$に対して$\mu(d)=\mu(p^2 \cdot \dfrac{d}{p^2})= \mu(p^2) \mu(\dfrac{d}{p^2}) = 0$が分かります。

まとめると正整数$d$に対して以下のようになり、よくみるメビウス関数が手に入ります。

• $d$が平方因子を持つならば$\mu (d) = 0$
• $d$が相異なる$k$個の素数の積ならば$\mu(d) = (-1)^k$

包除原理

有限集合$S={1,2,\cdots,n}$の冪集合が包含関係で成す束$\mathcal{P}(S)$を考えます。この時、だいぶ天下り的ですが$X\subset Y \subset S$に対して$\mu(X,Y) = (-1)^{|Y\backslash X|}$と定義しますとこれはまさに$\zeta$関数の畳み込みに関する逆元$\mu$となります。実際、$|Y\backslash X|=k$としますと
$$ \mu \ast \zeta (X,Y) = \sum_{X\subset Z \subset Y} \mu (X,Z) = 1 - {}_kC_1 + {}_kC_2-\cdots (-1)^k {}_kC_k = 0 $$となります(最後の式は$ (1+x)^k = \sum {}_k C_i x^i$とかから)。

では包除原理について述べるため、全体集合$X$と$S$によって添え字づけられた$X$の部分集合族$\{A_1,\cdots,A_n\}$について考えます。求めたいのは$|A_1 \cup \cdots \cup A_n|$です。

和集合の各領域をそれぞれ取得することを念頭に置いて$I \subset S$に対して、$f(I) = |\bigcap_{i\in I} A_i \backslash \bigcup_{i\notin I} A_i|$と置きます。すると$g(I)= \sum_{I\subset J} f(J)$は$|\bigcap_{i \in I} A_i|$と一致することが分かります。例えば$n=3$で$I= \{ 1,3 \}$なら以下のようになります。
$$ A_1 \cap A_3 = ((A_1 \cap A_3) \backslash A_2) \cup (A_1 \cap A_2 \cap A_3)$$

この和の式はメビウス反転公式の左式(向きは逆)になるので、右式をみれば$f(I)= \sum_{I \subset J} \mu(I,J) g(J)$が分かります。$\mu(I,J)=(-1)^{|J\backslash I|}$は先述の通りなので、$I=\emptyset$とすれば

\displaylines{
f(\emptyset) = |X| - |A_1 \cup \cdots \cup A_n| \\ = \sum_{I} (-1)^{|I|} g(I)
= |X| - \sum_i |A_i| + \sum_{i\neq j} |A_i \cup A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|
}

となります。整理すれば包除原理が導かれます。

$$ |A_1 \cup \cdots \cup A_n| = \sum_i |A_i| - \sum_{i\neq j} |A_i \cup A_j| + \cdots - (-1)^n |A_1 \cap \cdots \cap A_n| $$

まとめ

以上でメビウス反転公式とその応用について簡単にまとめさせて頂きました。だいぶ自分用のメモ感が強いかと思いますが、何かの参考になれば幸いです。

1. 計算を追えば分かりますが、実際には任意の閉区間$[a,b] = \{z | a\leq z \leq b\}$が有限集合になれば十分です(局所有限性)。 ↩