(1)の例

-

区別の出来ない\(n\)個のボールを区別の出来ない\(k\)個の箱に入れるとき、空箱なしは\(p\left(n-k,k\right)\)通りである。
漸化式
\begin{align*} & p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)\\ \Leftrightarrow & p\left(n-k,k\right)=p\left(n,k\right)-p\left(n,k-1\right) \end{align*} を使うと、
\begin{align*} \sum_{j=0}^{k}p\left(n-j,j\right) & =\sum_{j=0}^{k}\left\{ p\left(n,j\right)-p\left(n,j-1\right)\right\} \\ & =p\left(n,k\right) \end{align*} となるので、空箱ありは\(p\left(n,k\right)\)通りになる。

-

区別の出来ない\(n\)個のボールを区別の出来ない\(k\)個の箱に入れるとき、空箱ありは\(p\left(n,k\right)\)通りである。
漸化式
\begin{align*} & p\left(n,k\right)=p\left(n,k-1\right)+p\left(n-k,k\right)\\ \Leftrightarrow & p\left(n-k,k\right)=p\left(n,k\right)-p\left(n,k-1\right) \end{align*} を使うと、
\[ p\left(n,k\right)-p\left(n,k-1\right)=p\left(n-k,k\right) \] となるので、空箱なしは\(p\left(n-k,k\right)\)通りになる。

-

区別の出来る\(n\)個のボールを区別の出来ない\(k\)個の箱に入れるとき、空箱なしは\(S_{2}\left(n,k\right)\)通りである。
\begin{align*} \sum_{j=0}^{k}S_{2}\left(n,j\right) & =\sum_{j=0}^{k}\frac{1}{j!}\sum_{m=0}^{j}\left(-1\right)^{j-m}C\left(j,m\right)m^{n}\\ & =\sum_{m=0}^{k}\sum_{j=m}^{k}\left(-1\right)^{j-m}\frac{C\left(j,m\right)}{j!}m^{n}\\ & =\sum_{m=0}^{k}\sum_{j=m}^{k}\left(-1\right)^{j-m}\frac{1}{m!\left(j-m\right)!}m^{n}\\ & =\sum_{m=0}^{k}\frac{m^{n}}{m!}\sum_{j=m}^{k}\left(-1\right)^{j-m}\frac{1}{\left(j-m\right)!}\\ & =\sum_{m=0}^{k}\frac{m^{n}}{m!}\sum_{j=0}^{k-m}\frac{\left(-1\right)^{j}}{j!}\\ & =B\left(n,k\right) \end{align*} となるので、空箱ありは\(B\left(n,k\right)\)通りとなる。

-

区別の出来る\(n\)個のボールを区別の出来ない\(k\)個の箱に入れるとき、空箱ありは\(B\left(n,k\right)\)通りである。
\begin{align*} B\left(n,k\right)-B\left(n,k-1\right) & =\left(\sum_{j=0}^{k}-\sum_{j=0}^{k-1}\right)\frac{1}{j!}\sum_{m=0}^{j}\left(-1\right)^{j-m}C\left(j,m\right)m^{n}\\ & =\frac{1}{k!}\sum_{m=0}^{k}\left(-1\right)^{k-m}C\left(k,m\right)m^{n}\\ & =S_{2}\left(n,k\right) \end{align*} となるので、空箱なしは\(S_{2}\left(n,k\right)\)通りとなる。

(2)の例

-

区別の出来ない\(n\)個のボールを区別の出来る\(k\)個の箱に入れるとき、空箱なしは\(C\left(n-1,k-1\right)\)通りなので、
\begin{align*} \sum_{j=0}^{k}C\left(k,j\right)C\left(n-1,j-1\right) & =\sum_{j=0}^{k}C\left(k,j\right)C\left(n-1,n-1-\left(j-1\right)\right)\\ & =\sum_{j=0}^{k}C\left(k,j\right)C\left(n-1,n-j\right)\\ & =\sum_{j=0}^{n}C\left(k,j\right)C\left(n-1,n-j\right)\\ & =C\left(k+n-1,n\right)\\ & =H\left(k,n\right) \end{align*} となり、空箱ありは\(H\left(k,n\right)\)通りになる。

-

\(a,b,c\in\mathbb{Z}\land0\leq a\land b\leq c\)のとき、
\[ \sum_{j=0}^{k-a}\left(-1\right)^{j}C\left(k,j+a\right)C\left(j+b,c\right)=\begin{cases} \left(-1\right)^{k-a}C\left(b-a,c-k\right) & a-b+c\leq k\\ 0 & k<a-b+c \end{cases} \] を使う。
区別の出来ない\(n\)個のボールを区別の出来る\(k\)個の箱に入れるとき、空箱ありは\(H\left(k,n\right)\)通りなので、
\begin{align*} \sum_{j=0}^{k-a}\left(-1\right)^{k-j}C\left(k,j\right)H\left(j,n\right) & =\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)C\left(j+n-1,n\right)\\ & =\left(-1\right)^{k}\sum_{j=0}^{k}\left(-1\right)^{j}C\left(k,j\right)C\left(j+n-1,n\right)\\ & =\begin{cases} \left(-1\right)^{k}\left(-1\right)^{k}C\left(n-1,n-k\right) & -\left(n-1\right)+n\leq k\\ 0 & k<-\left(n-1\right)+n \end{cases}\\ & =\begin{cases} C\left(n-1,k-1\right) & 1\leq k\\ 0 & k<1 \end{cases}\\ & =\begin{cases} C\left(n-1,k-1\right) & 1\leq k\\ C\left(n-1,k-1\right) & k<1 \end{cases}\\ & =C\left(n-1,k-1\right) \end{align*} となり、空箱なしは\(C\left(n-1,k-1\right)\)通りになる。

-

区別の出来る\(n\)個のボールを区別の出来る\(k\)個の箱に入れるとき、空箱なしは\(S_{2}\left(n,k\right)k!\)通りなので、
\begin{align*} \sum_{j=0}^{k}C\left(k,j\right)S_{2}\left(n,j\right)j! & =\sum_{j=0}^{k}C\left(k,j\right)\frac{1}{j!}\sum_{m=0}^{j}\left(-1\right)^{j-m}C\left(j,m\right)m^{n}j!\\ & =\sum_{j=0}^{k}\sum_{m=0}^{j}\left(-1\right)^{j-m}C\left(k,j\right)C\left(j,m\right)m^{n}\\ & =\sum_{m=0}^{k}\left(-1\right)^{-m}m^{n}\sum_{j=m}^{k}\left(-1\right)^{j}C\left(k,j\right)C\left(j,m\right)\\ & =\sum_{m=0}^{k}\left(-1\right)^{-m}m^{n}\sum_{j=m}^{k}\left(-1\right)^{j}C\left(k,m\right)C\left(k-m,k-j\right)\\ & =\sum_{m=0}^{k}\left(-1\right)^{-m}m^{n}C\left(k,m\right)\sum_{j=m}^{k}\left(-1\right)^{j}C\left(k-m,j-m\right)\\ & =\sum_{m=0}^{k}m^{n}C\left(k,m\right)\sum_{j=0}^{k-m}\left(-1\right)^{j}C\left(k-m,j\right)\\ & =\sum_{m=0}^{k}m^{n}C\left(k,m\right)\delta_{km}\\ & =k^{n} \end{align*} となり、空箱ありは\(k^{n}\)通りになる。

-

区別の出来る\(n\)個のボールを区別の出来る\(k\)個の箱に入れるとき、空箱ありは\(k^{n}\)通りなので、
\begin{align*} \sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n} & =\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n}\\ & =k!\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n}\\ & =S_{2}\left(n,k\right)k! \end{align*} となり、空箱なしは\(S_{2}\left(n,k\right)k!\)通りになる。