部屋割りの数$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}

まとめておこう