ゼータ変換とメビウス変換の関係

競技プログラミングでたまに使われるゼータ変換とメビウス変換について、逆変換だというのがどうもピンと来なかったので確かめてみる事にしました。
(多分探せばもっと高度でエレガントな証明があるんだろうなぁと思っています。)

これらの変換は、集合 X上の関数 f:2 ^ X \to \mathbb{R}を同じ集合上の関数に変換します。 定義を確認しておきます。

ゼータ変換

\displaystyle \zeta (f)(S) = \sum _ {S\subset T} f(T)

メビウス変換

\displaystyle \mu (f)(S) = \sum _ {S\subset T} (-1)^{|T| - |S|} f(T)

つまり、ゼータ変換はある集合 Sを含む集合 T全体にわたる和で、メビウス変換は同様の T全体に対して足したり引いたりします。(笑) (多分あとで例を出します。)

これが逆変換になるらしいのですが、眺めていてもよくわからない。という事で計算してみました。

計算

まずは \mu(\zeta(f))(S) = f(S)を示したい。
一応断っておきますが、ここでは集合 Xの大きさが有限だったりして和の順番は自由に入れ替えて良いとします。

\begin{aligned} \mu(\zeta(f))(S) &= \sum _ {S \subset T} (-1)^{|T| - |S|} \zeta(f)(T) \\ &= \sum _ {S \subset T} (-1)^{|T| - |S|} \sum _ {T \subset U} f(U) \\ &= \sum _ {S \subset U} f(U) - \sum _ {x \in X \smallsetminus S} \sum _ {S\cup \{x\} \subset U} f(U) + \sum _ {\{x,y\} \subset X \smallsetminus S} \sum _ {S\cup \{x,y\} \subset U} f(U) - \cdots \\ &= \left(f(S) + \sum _ {x \in X \smallsetminus S} f(S\cup \{x\}) + \sum _ {\{x,y\} \subset X \smallsetminus S} f(S\cup \{x,y\}) + \cdots \right) \\ &\ \ \ - \left(\sum _ {x \in X \smallsetminus S} f(S\cup \{x\}) + 2\sum _ {\{x,y\} \subset X \smallsetminus S} f(S\cup \{x,y\}) + 3\sum _ {\{x,y,z\} \subset X \smallsetminus S} f(S\cup \{x,y,z\}) + \cdots \right) \\ &\ \ \ + \left(\sum _ {\{x,y\} \subset X \smallsetminus S} f(S\cup \{x,y\}) + 3\sum _ {\{x,y,z\} \subset X \smallsetminus S} f(S\cup \{x,y,z\}) + \cdots \right) \\ &\ \ \ - \cdots \\ &= f(S) + \sum _ {k=1} ^ {|X \smallsetminus S|} \ _ kC _ 0 \sum _ {\{x _ 1, \ldots , x _ k\}\subset X \smallsetminus S} f(S \cup \{x _ 1 , \ldots , x _ k\}) \\ &\ \ \ - \sum _ {k=1} ^ {|X \smallsetminus S|} \ _ kC _ 1 \sum _ {\{x _ 1, \ldots , x _ k\}\subset X \smallsetminus S} f(S \cup \{x _ 1 , \ldots , x _ k\}) \\ &\ \ \ + \sum _ {k=2} ^ {|X \smallsetminus S|} \ _ kC _ 2 \sum _ {\{x _ 1, \ldots , x _ k\}\subset X \smallsetminus S} f(S \cup \{x _ 1 , \ldots , x _ k\}) \\ &\ \ \ - \cdots \\ &= f(S) + \left( _ 1C _ 0 - \ _ 1C _ 1 \right) \sum _ {\{x _ 1\} \subset X \smallsetminus S} f(S \cup \{x _ 1\}) \\ &\ \ \ + \left( _ 2C _ 0 - \ _ 2C _ 1 + \ _ 2C _ 2 \right) \sum _ {\{x _ 1, x _ 2\} \subset X \smallsetminus S} f(S \cup \{x _ 1, x _ 2\}) \\ &\ \ \ + \cdots \\ &= f(S) + \sum _ {n=1} ^ {|X \smallsetminus S|} \left(\sum _ {k=0} ^ n (-1)^{k} \ _ nC _ k \right) \sum _ {\{x _ 1, \ldots , x _ n\}\subset X \smallsetminus S} f(S \cup \{x _ 1 , \ldots , x _ n\}) \\ &= f(S) \end{aligned}

はい。
なんか途中でいろいろなことが起こりましたがなんとか結論まで持って来れました。
途中で行った式変形のほとんどは和の順番を変更するという操作です。
間違い探しパズルだと思えば式変形を追えないこともないんじゃないかなと思います。
そして最後の部分で、二項係数の交代級数の和 \sum _ {k=0} ^ n (-1)^{k} \ _ nC _ kが0になるということを利用しました。
ちなみにこれは、二項展開の式

\begin{aligned} (1 + x) ^ n = \sum _ {k=0} ^ n \ _ nC _ k \ x^k \end{aligned}

に x=-1を代入することで簡単に示せます。

計算その2

さきほどはゼータ変換してからメビウス変換すると元に戻ることを示しました。
ということで次は反対の \zeta(\mu(f))(S) = f(S)を示すために計算をしていきます。
(上の結果を利用して楽をする方法をしばらく考えたのですが、無理そうでした。)

\begin{aligned} \zeta(\mu(f))(S) &= \sum _ {S\subset T} \mu(f)(T) \\ &= \sum _ {S\subset T} \sum _ {T \subset U} (-1)^{|U|-|T|} f(U) \\ &= \sum _ {S \subset U} (-1)^{|U|-|S|} f(U) + \sum _ {x \in X \smallsetminus S} \sum _ {S\cup \{x\} \subset U} (-1)^{|U|-|S|-1} f(U) + \cdots \\ &= \left(f(S) - \sum _ {x \in X \smallsetminus S} f(s\cup\{x\}) + \sum _ {\{x,y\} \subset X \smallsetminus S} f(s\cup\{x,y\}) - \cdots \right) \\ &\ \ \ + \left( \sum _ {x \in X \smallsetminus S} f(s\cup\{x\}) - 2\sum _ {\{x,y\} \subset X \smallsetminus S} f(s\cup\{x,y\}) + \cdots \right) \\ &\ \ \ + \cdots \\ &= f(S) + \sum _ {n=1} ^ {|X \smallsetminus S|} (-1)^n \ _ nC _ 0 \sum _ {\{x _ 1, \ldots , x _ n\}\subset X \smallsetminus S} f(S\cup \{x _ 1 , \ldots, x _ n\}) \\ &\ \ \ + \sum _ {n=1} ^ {|X \smallsetminus S|} (-1)^{n+1} \ _ nC _ 1 \sum _ {\{x _ 1, \ldots , x _ n\}\subset X \smallsetminus S} f(S\cup \{x _ 1 , \ldots, x _ n\}) \\ &\ \ \ + \sum _ {n=2} ^ {|X \smallsetminus S|} (-1)^{n+2} \ _ nC _ 2 \sum _ {\{x _ 1, \ldots , x _ n\}\subset X \smallsetminus S} f(S\cup \{x _ 1 , \ldots, x _ n\}) \\ &\ \ \ + \cdots \\ &= f(S) - \left( _ 1C _ 0 - \ _ 1C _ 1 \right) \sum _ {\{x _ 1\} \subset X \smallsetminus S} f(S \cup \{x _ 1\}) \\ &\ \ \ + \left( _ 2C _ 0 - \ _ 2C _ 1 + \ _ 2C _ 2 \right) \sum _ {\{x _ 1, x _ 2\} \subset X \smallsetminus S} f(S \cup \{x _ 1, x _ 2\}) \\ &\ \ \ - \left( _ 3C _ 0 - \ _ 3C _ 1 + \ _ 3C _ 2 + \ _ 3C _ 3 \right) \sum _ {\{x _ 1, x _ 2, x _ 3\} \subset X \smallsetminus S} f(S \cup \{x _ 1, x _ 2, x _ 3\}) \\ &\ \ \ + \cdots \\ &= f(S) + \sum _ {n=1} ^ {|X \smallsetminus S|} (-1)^n \left(\sum _ {k=0} ^ n (-1)^{k} \ _ nC _ k \right) \sum _ {\{x _ 1, \ldots , x _ n\}\subset X \smallsetminus S} f(S \cup \{x _ 1 , \ldots , x _ n\}) \\ &= f(S) \end{aligned}

やってみたら上とほとんど同じでした。 ということでめでたくゼータ変換とメビウス変換は逆変換の関係になっていることが示せました。

おまけ

ここではゼータ変換、メビウス変換を

\displaystyle \zeta (f)(S) = \sum _ {S\subset T} f(T)\ ,\ \ \ \mu (f)(S) = \sum _ {S\subset T} (-1)^{|T| - |S|} f(T)

と定義しましたが、別の定義というか別のゼータ変換、メビウス変換として次のようなものがあります。

\displaystyle \zeta^\prime (f)(S) = \sum _ {T\subset S} f(T)\ ,\ \ \ \mu^\prime (f)(S) = \sum _ {T\subset S} (-1)^{|S| - |T|} f(T)

Sと Tの関係が逆になっていますが、これらも逆変換の関係にあります。
ちゃんとは確認していませんが、多分補集合をとるなどして関数と変数を適当に変換してやれば互いに移りあうと思います。

ちょっとした例

今更感ありますが、ちょっとした例を出してみます。
\left\lvert\bigcap _ {i \in S} A _ i\right\rvertの値から \left\lvert\bigcup _ {i \in S} A _ i\right\rvertの値を求めたいとします。
中学入試問題みたいなところでよく見るタイプの問題ですね。

答えは簡単で、

\begin{aligned} \left\lvert\bigcup _ {i \in S} A _ i\right\rvert &= \sum _ {i \in S} |A _ i| - \sum _ {\{i,j\} \subset S} |A _ i\cap A _ j| + \cdots \\ &= \sum _ {T \subset S} (-1)^{|T|+1} \left\lvert\bigcap _ {i \in T} A _ i\right\rvert \end{aligned}

です。 包除原理などとも呼ばれるらしいです。

ここで f(S) = \left\lvert\bigcap _ {i \in S} A _ i\right\rvert、　g(S) = \left\lvert\bigcup _ {i \in S} A _ i\right\rvertとおいてみれば、

\begin{aligned} g(S) &= \sum _ {T \subset S} (-1)^{|T|+1} f(T) \\ &= (-1)^{|S|+1} \sum _ {T \subset S} (-1)^{|S| - |T|} f(T) \\ &= (-1)^{|S|+1} \mu^\prime(f)(S) \end{aligned}

となってメビウス変換で表すことができます。

ちなみに、 fの定義を f(S) = (-1)^{|S|+1} \left\lvert\bigcap _ {i \in S} A _ i\right\rvertとすると、

\begin{aligned} g(S) = \sum _ {T \subset S} f(T) = \zeta^\prime(f)(S) \end{aligned}

と、ゼータ変換で表すこともできます。
(この例を出したのはこれが言いたいだけだったり。)

あとがき

ゼータ変換とメビウス変換は互いに逆変換だということを確認しました。
ここまで頑なに「変換」という言葉を使ってきましたが、写像と考えることもできるはずです。 集合 X上の関数全体の集合を F(X)とすると、ゼータ変換やメビウス変換は写像 \zeta,\ \mu : F(X) \to F(X)となり、逆写像があるので同型写像だと言えます。
ほかにも、畳み込みに対して特別な性質を持っていたり、この2つの変換の裏にはまだいくらか世界が広がっているのではないかと思っているのですが、今はそこまで踏み込む余裕はないのでこのあたりで終わろうと思います。