組み合わせの計算

数

集合\Omegaの部分集合の列A_1, A_2,\cdots,A_nがあって、
任意の添え字の組み合わせsに対して

A_s = \sharp(\bigcap_{i \in s} A_i)

は分かっている。これを使って

\sharp(A_1^c \cap A_2^c \cap \cdots \cap A_n^c)

を表すにはどうすればいいかな。

\begin{eqnarray} \sharp(A_1) &=& \sharp(A_1) \\ \sharp(A_1 \cup A_2) &=& \sharp A_1 + \sharp A_2 - \sharp(A_1 \cap A_2) \\ \sharp(\bigcup_{i=1}^n A_i) &=& \sharp(\bigcup_{i=1}^{n-1} A_i)+\sharp A_n-\sharp( (\bigcup_{i=1}^{n-1} A_i) \cap A_n) \\ &=& \sharp(\bigcup_{i=1}^{n-1} A_i)+\sharp A_n-\sharp(\bigcup_{i=1}^{n-1} (A_i \cap A_n)) \\ &=& \sum_{s:\sharp s is odd} #A_s - \sum_{s:\sharp s is even} \sharp A_s \end{eqnarray}

だよなあ。偶奇で加減すればいいのは直感できたんだが、確信できなかった。

これ、数式書けん。いいやあきらめ。

正負が交互に現れて総和

こういう正負が交互に現れる総和は反転公式に似てるから、何か一般的な規則があるんじゃなかろうかと考えていたんだが、
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E9%96%A2%E6%95%B0
メビウスの反転公式のとこにまんま載ってた。