★包含と排除の原理の一般形
包含と排除の原理（一般の場合）
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}この式が包含と排除の原理の一般形である．
部屋割りの数$room(m,r)$の計算
一般の部屋割りの数 $room(m,r)$ は，包含と排除の原理の一般形を用いて，次のように計算できる．
\begin{align} &room(m,~r)\\ =\ &n(U)-n(A_1{\cup}A_2{\cup}A_3{\cup}\cdots{\cup}A_r)\\ =\ &n(U)-\Big\{\sum_{i_1}^{r,~1}n(A_{i_1})-\sum_{i_1,~i_2}^{r,~2}n(A_{i_1}\cap{}A_{i_2})\\ &+\sum_{i_1,~i_2,~i_3}^{r,~3}n(A_{i_1}\cap{}A_{i_2}\cap{}A_{i_3})-\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})}\Big\}\\ =\ &n(U)-\sum_{i_1}^{r,~1}n(A_{i_1})+\sum_{i_1,~i_2}^{r,~2}n(A_{i_1}\cap{}A_{i_2})\\ &-\sum_{i_1,~i_2,~i_3}^{r,~3}n(A_{i_1}\cap{}A_{i_2}\cap{}A_{i_3})+\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})}\\ =\ &r^m-_{r}\mathrm{C}_{1}(r-1)^m+_{r}\mathrm{C}_{2}(r-2)^m\\ &-_{r}\mathrm{C}_{3}(r-3)^m+\cdots+(-1)^r{_{r}\mathrm{C}_{r}}(r-r)^m\\ =\ &\sum_{k=0}^{r}(-1)^k{_{r}\mathrm{C}_{k}}(r-k)^m \end{align}まとめておこう
部屋割りの数 $room(n,r)$ の計算
部屋割りの数 $room(n,~r)$ は
\begin{align} room(n,~r)&=\sum_{k=0}^{r}(-1)^k{_{r}\mathrm{C}_{k}}(r-k)^n\\ &=r!\sum_{k=0}^{r}\frac{(-1)^k(r-k)^n}{(r-k)!k!} \end{align}と計算できる．
吹き出し無題
この計算式は理論的にはこう表せるということを示したものであり，記憶する必要は全くない． シグマ記号 $\sum_{}^{}$ については $FTEXT$ 数学Bを参照のこと．
撹乱順列
『部屋割り』とは異なるが，『包含と排除の原理』の応用として次の問題を考えてみよう．
攪乱順列
4人の友達A，B，C，Dがクリスマスパーティーでプレゼントを交換する．自分自身の持ってきたプレゼントに誰も当たらないようになるのは何通りの分け方があるか求めよ．
解答1：包含と排除の原理
$U$ ：プレゼントの分け方のすべて
$A$ ：A君が自分自身のプレゼントをもらう
$B$ ：B君が自分自身のプレゼントをもらう
$C$ ：C君が自分自身のプレゼントをもらう
$D$ ：D君が自分自身のプレゼントをもらう
と集合をおくと
\begin{align} &\ n(U)-n(A\cup B\cup C\cup D)\\ =&\ n(U)-\bigl\{n(A)+n(B)+n(C)+n(D)\\ &\ -n(A\cap B)-n(A\cap C)-n(A\cap D)\\ &\ -n(B\cap C)-n(B\cap D)-n(C\cap D)\\ &\ +n(A\cap B\cap C)+n(A\cap B\cap D)\\ &\ +n(A\cap C\cap D)+n(B\cap C\cap D)\\ &\ -n(A\cap B\cap C\cap D)\bigr\}\\ =&\ 4!-\bigl\{\ _{4}\mathrm{C}_{1}(4-1)!-\ _{4}\mathrm{C}_{2}(4-2)!\\ &\ +\ _{4}\mathrm{C}_{3}(4-3)!-\ _{4}\mathrm{C}_{4}(4-4)!\bigr\}\\ =&\ 4!\left(\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right)\\ =&\ 4!-4\cdot3!+6\cdot2!-4\cdot1!+1\\ =&\ \boldsymbol{9} \end{align}通り
解答2：漸化式を使う
$n$ 人のプレゼント交換において， 自分自身の持ってきたプレゼントに誰も当らない場合の数を $D(n)$ とする．
いま， $D(4)$ は次の3つに場合分けできる．
- A君がB君のプレゼントに当る
- A君がC君のプレゼントに当る
- A君がD君のプレゼントに当る
i. ～iii. は対称的なので，以下i. についてだけ考える（のち4 − 1 = 3倍すればよい）．
プレゼントを小文字のアルファベットで表すとして，“A君のプレゼントaをbと考えて”，残りの3人へのプレゼントの配り方を考えると
- B君にb（本当はa）を配り，残りC，D君に自分自身のプレゼントが当らないように配る
- B，C，D君に自分自身のプレゼントが当らないように配る（見かけの上ではあるが，B君にbが配られない場合を考える）
の2通りに場合分けできる．ここで1. は $D(2)$ ，2. は $D(3)$ に他ならない．つまり $D(4)$ は
\[D(4)=(4-1)\left\{D(3)+D(2)\right\}\]で計算できる．この関係は $n$ が自然数で一般的に成り立つから
\begin{align} D(4)=&\ (4-1)\left\{D(3)+D(2)\right\}\\ =&\ 3D(3)+3D(2)\\ =&\ 3\left[2\left\{D(2)+D(1)\right\}\right]+3D(2)\\ =&\ 9D(2)+6D(1)\\ =&\ 9D(2)+0\\ =&\ 9\cdot1\\ =&\ \boldsymbol{9} \end{align}通り