包含と排除の原理（一般の場合）

1から $r$ までの $r$ 個の自然数の集合 $\{1,~2,~\cdots,~r\}$ から $k$ 個の要素をとってきて， 小さいものから順に並び換えた組

\begin{align} (\underbrace{i_1,~i_2,~i_3,~\cdots,~i_k}_{k個}) \end{align}

を作るとする． このとき，この組の作り方は全部で $_{r}C_{k}$ 通りあるが，そのすべてに関して次の例のような和を考え $\displaystyle \sum_{i_1,~i_2,~\cdots,~i_k}^{r,~k}$ と表すことにする．

例えば， $k = 1$ の例 $\displaystyle \sum_{i_1}^{r,~1}2^{i_1}$ は

$\displaystyle \sum_{i_1}^{r,~1}2^{i_1}=2^1+2^2+2^3+\cdots+2^{(r-1)}+2^r$

を意味し， $r = 4，k = 2$ の例 $\displaystyle \sum_{i_1,~i_2}^{4,~2}a_{i_1}a_{i_2}$ は

\begin{align} \sum_{i_1,~i_2}^{4,~2}a_{i_1}a_{i_2}=\ &{a_1}{a_2}+{a_1}{a_3}+{a_1}{a_4}\\ &\ +{a_2}{a_3}+{a_2}{a_4}+{a_3}{a_4} \end{align}

を意味している

この記号を用いると， $r$ 個の集合 $A_1,A_2,A_3,\cdots,A_r$ の和集合 $A_1\cup{A_2}\cup\cdots\cup{A_r}$ の要素の個数に関して，次の式が成り立つ．

\begin{align} &n(A_1\cup{A_2}\cup\cdots\cup{A_r})\\ =\ &\sum_{i_1}^{r,~1}n(A_{i_1})-\sum_{i_1,~i_2}^{r,~2}n(A_{i_1}\cap{}A_{i_2})+\cdots+\\ &(-1)^{r-1}\sum_{i_1,i_2,\cdots,i_r}^{r,~r}n(A_{i_1}\cap{}A_{i_2}\cap\cdots\cap{}A_{i_r}) \end{align}

この式が包含と排除の原理の一般形である．