部屋割り
例えば，5人の人が鶴の間，亀の間，松の間の3つの部屋に泊まる場合， 部屋を割り当てる方法（空部屋はでないようにする）には何通りの方法があるだろうか． このような問題は，人を「区別するボール」，部屋を「区別する箱」として，ボールと箱のモデルで考えることができる．
| ボール・箱 | 単射 | 写像全て | 全射 | |
| あり・あり | 順列 | 重複順列 | 部屋割り | |
| なし・あり | 組合せ | 重複組合せ | 資源配分 | |
| あり・なし | （右枠の和） | 部屋割り（区別なし） | ||
| なし・なし | （右枠の和） | 資源配分（区別なし） |
部屋割りの数
ボールと箱のモデル3
無題
ボールと箱のモデルを使って
「区別する5個のボールを，区別する3個の箱に最低1個は配る場合の数」 を考えてみよう．
準備として，ボールは区別するので番号をつけ，それを①，②，③，④，⑤とし， 箱も区別するので番号をつけ，それを
としておく．
集合 $A，B，C，U$ をそれぞれ
$A$ ：
が空になる
$B$ ：
が空になる
$C$ ：
が空になる
$U$ ：ボールを適当に箱にしまう場合（空・重複有り）
とおくと，求めるものは $n(U)-n(A\cup{B}\cup{C})$ である．
$n(U)=3^5$ ←重複順列 $_{3}\Pi_{5}$
$n(A)=n(B)=n(C)=2^5$ ←1つ以上の箱が空になる場合
$n(A\cap{B})=n(B\cap{C})=n(C\cap{A})=1$ ←2つ（以上）の箱が空になる場合
$n(A\cap{B}\cap{C})=0$ ←全部の箱が空になる場合
であるから，包含と排除の原理を使って
\begin{align} &\ n(U)-n(A\cup{B}\cup{C})\\ =&\ n(U)-\{n(A)+n(B)+n(C)-n(A\cap{B})\\ &-n(B\cap{C})-n(C\cap{A})+n(A\cap{B}\cap{C})\}\\ =&\ n(U)-n(A)-n(B)-n(C)+n(A\cap{B})\\ &+n(B\cap{C})+n(C\cap{A})-n(A\cap{B}\cap{C})\\ =&\ 3^5-3\cdot2^5+3-0\\ =&\ 150 \end{align}通り となる．
ここで，ボールを箱へこのように配る方法を定義しておく．
部屋割りの数room(n,r)の定義
「区別するn個のボールを，区別するr個の箱に（空の箱がないように）最低1個は配る場合の数」を， $FTEXT$ では $\boldsymbol{room(n,~r)}$ と表す．
この例では， $room(5,~3)=150$ である．
$room(n,~r)$ は $n$ 個の要素をもつ集合 $A$ から， $r$ 個の要素をもつ集合 $B$ への全射のパターンの総数と等しい．
★包含と排除の原理の一般形
包含と排除の原理（一般の場合）
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}通り