積の法則により, 求める場合の数は \[\begin{aligned} &{}_{n_1+\cdots +n_r}\mathrm C_{n_1}\cdot\cdots\cdot{}_{n_k+\cdots +n_r}\mathrm C_k\cdot\cdots\cdot{}_{n_r}\mathrm C_{n_r} \\ &= \frac{(n_1+\cdots +n_r)!}{n_1!(n_2+\cdots +n_r)!}\cdot\cdots\cdot\frac{(n_k+\cdots +n_r)!}{n_k!(n_{k+1}+\cdots +n_r)!}\cdot\cdots\cdot\frac{n_r!}{n_r!0!} \\ &= \frac{(n_1+\cdots +n_r)!}{n_1!\cdots n_r!} \end{aligned}\] である.

　同じものごとに番号をふって $1$ 列に並べる方法は $(n_1+\cdots +n_r)!$ 通りあり, 番号を消したときに同一視されるものが $n_1!\cdots n_r!$ 通りずつあるから, 求める場合の数は \[\frac{(n_1+\cdots +n_r)!}{n_1!\cdots n_r!}\] である.

　$n$ 種類のものから重複を許して $r$ 個選ぶ方法を記録するには, $r$ 個の空欄〇と $n-1$ 個の仕切り｜を横 $1$ 列に並べることで $r$ 個の空欄 〇 を $n$ 個の区画に分け (〇 が $0$ 個の区画があってもよい), 左から順に区画に種類の名前を記入すればよい. つまり, その場合の数は, $r$ 個の ◯ と $n-1$ 個の仕切り ｜ を $1$ 列に並べる方法の総数 \[ {}_{r+(n−1)}\mathrm C_r​ = {}_{n+r−1}\mathrm C_r​\] に等しい.

(1)

$1$ 個の玉につき $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ のどの箱に入れるかで $n$ 通りの方法があるから, 求める場合の数は $n^r$ である.

(2)

求める場合の数は, $n = 2$ のとき (1) において箱の区別をなくした場合の数に等しく, $\dfrac{2^r}{2!} = 2^{r-1}$ である.

(3)

求める場合の数を $N$ とおく.

(i)

$r$ 個の玉が $1$ つの箱に入る場合は, $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3$ 通りあるから, (1) の $3$ 通りが生じる.

(ii)

$r$ 個の玉が複数の箱に入る場合は, $N-1$ 通り. このとき，玉の入った箱は入っている玉によって区別でき, 空箱は高々 $1$ 個で玉の入った箱と区別できるから, 箱はすべて区別できる. よって, この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-1)$ 通りが生じる.

(i), (ii) と (1) の結果により \[ 3+3!(N-1) = 3^r\] が成り立つから, \[ N = \frac{3^r+3}{3!} = \frac{3^{r-1}+1}{2}\] である.

(3)

区別ができる $r$ 個の玉を区別のできない $3$ つの箱に入れるとき, $r$ 個の玉が $1$ つの箱に入る場合の数を $a_r,$ ちょうど $2$ つの箱の箱に入る場合の数を $b_r,$ ちょうど $3$ つの箱に入る場合の数を $c_r$ とおき, その総数を $N_r$ とおく. このとき, \[\begin{aligned} N_r &= a_r+b_r+c_r, \\ a_{r+1} &= a_r, \\ b_{r+1} &= a_r+2b_r, \\ c_{r+1} &= b_r+3c_r \end{aligned}\] であるから, \[\begin{aligned} N_{r+1} &= a_{r+1}+b_{r+1}+c_{r+1} \\ &= a_r+(a_r+2b_r)+(b_r+3c_r) \\ &= 3(a_r+b_r+c_r)-a_r \\ &= 3N_r-1 \quad [1] \end{aligned}\] が成り立つ. よって, $[1]$ の辺々から $x = 3x-1$ の解 $x = \dfrac{1}{2}$ を引くと \[ N_{r+1}-\frac{1}{2} = 3\left( N_r-\frac{1}{2}\right)\] となる. したがって, $\left\{ N_r-\dfrac{1}{2}\right\}$ は初項 $N_1-\dfrac{1}{2} = \dfrac{1}{2},$ 公比 $3$ の等比数列であるから, \[\begin{aligned} N_r-\frac{1}{2} &= \frac{1}{2}\cdot 3^{r-1} \\ N_r &= \frac{3^{r-1}+1}{2} \end{aligned}\] である.

(1)

$\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ の各箱に入る玉の個数を $x_1,$ $\cdots,$ $x_n$ とおくと, \[ x_1+\cdots +x_n = r, \quad x_1,\ \cdots,\ x_n \geqq 0\] となり, $x_1,$ $\cdots,$ $x_n$ はそれぞれ $r$ 個の〇と $n-1$ 本の｜の順列において｜で仕切られた〇の個数に対応するから, 求める場合の数は \[ {}_{r+(n-1)}\mathrm C_r = {}_{r+(n-1)}\mathrm C_{n-1} = \frac{(n+r-1)!}{(n-1)!r!}\] である.

(2)

$n = 2$ のとき, (1) の場合の数は \[ {}_{r+(2-1)}\mathrm C_{2-1} = r+1\] である. 求める場合の数を $N$ とおく.

(I)

$r$ が奇数の場合. $2$ つの箱に入る玉の個数は異なるので, この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつける方法は $2!$ 通りある. よって, (1) の場合の数について \[ 2!N = r+1\] が成り立つから, \[ N = \frac{r+1}{2}\] である.

(II)

$r = 2k$ ($k$: 正の整数) の場合.

(i)

$2$ つの箱に入る玉の個数が等しい場合, 玉の個数の組合せは $\{ k,k\}$ の $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.

(ii)

$2$ つの箱に入る玉の個数が異なる場合, 玉の個数の組合せは $N-1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $2!$ 通りあるから, (1) の $2!(N-1)$ 通りが生じる.

(i), (ii) から (1) の場合の数は \[ 1+2!(N-1) = r+1\] と表せるので, これを $N$ について解くと \[ N = \frac{r}{2}+1\] が得られる.

(3)

$n = 3$ のとき, (1) の場合の数は \[ {}_{r+(3-1)}\mathrm C_{3-1} = \frac{(r+2)(r+1)}{2} \quad \cdots [1]\] である. 求める場合の数を $N$ とおく.

(I)

$r = 6k$ ($k$: 正の整数) の場合.

(i)

各箱に入る玉の個数がすべて等しい場合, 玉の個数の組合せは $\{ 2k,2k,2k\}$ の $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.

(ii)

各箱に入る玉の個数が $2$ 箱だけ等しい場合, 玉の個数の組合せは $\{ 0,0,6k\},$ $\cdots,$ $\{ 3k,3k,0\}$ から (i) の場合を除いた $3k$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $\dfrac{3!}{2!} = 3$ 通りあるから, (1) の $3\cdot 3k$ 通りが生じる.

(iii)

各箱に入る玉の個数がすべて異なる場合, 玉の個数の組合せは $N-3k-1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-3k-1)$ 通りが生じる.

(i)～(iii) から (1) の場合の数は \[\begin{aligned} &1+3\cdot 3k+3!(N-3k-1) \\ &= 6N-9k-5 = 6N-\frac{3r+10}{2} \quad \cdots [2] \end{aligned}\] と表せるので, $[1] = [2]$ を $N$ について解くと \[ N = \frac{r^2+6r+12}{12}\] が得られる.

(II)

$r = 6k+1$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+1)+3!(N-3k-1) \\ &= 6N-9k-3 = 6N-\frac{3(r+1)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.

(III)

$r = 6k+2$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+2)+3!(N-3k-2) \\ &= 6N-9k-6 = 6N-\frac{3(r+2)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.

(IV)

$r = 6k+3$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &1+3(3k+1)+3!(N-3k-2) \\ &= 6N-9k-8 = 6N-\frac{3r+7}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+3)^2}{12}\] である.

(V)

$r = 6k+4$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+2)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.

(VI)

$r = 6k+5$ ($k$: 非負整数) の場合. (I) と同様にして (1) の場合の数は \[\begin{aligned} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+1)}{2} \end{aligned}\] と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.

(1)

\[\begin{aligned} {}_n\mathrm H_r &= {}_{n+r-1}\mathrm C_r \quad \cdots [1], \\ {}_{n+1}\mathrm C_{r+1} &= {}_n\mathrm C_r+{}_n\mathrm C_{r+1} \quad \cdots [2] \end{aligned}\] ($[2]$ の証明についてはこちらを参照) であるから, \[\begin{aligned} {}_{n+1}\mathrm H_{r+1} &= {}_{n+r+1}\mathrm C_{r+1} \quad (\because [1]) \\ &= {}_{n+r}\mathrm C_r+{}_{n+r}\mathrm C_{r+1} \quad (\because [2]) \\ &= {}_{n+1}\mathrm H_r+{}_n\mathrm H_{r+1} \quad (\because [1]) \end{aligned}\] が成り立つ.

(2)

(1) を繰り返し使うと, \[\begin{aligned} {}_n\mathrm H_{r+1} &= {}_n\mathrm H_r+{}_{n-1}\mathrm H_{r+1} \\ &= \cdots \\ &= {}_n\mathrm H_r+\cdots +{}_k\mathrm H_{r+1} \\ &= {}_n\mathrm H_r+\cdots +{}_k\mathrm H_r+{}_{k-1}\mathrm H_{r+1} \\ &= \cdots \\ &= {}_n\mathrm H_r+\cdots +{}_2\mathrm H_r+{}_1\mathrm H_{r+1} \\ &= {}_n\mathrm H_r+\cdots +{}_2\mathrm H_r+{}_1\mathrm H_r \end{aligned}\] が得られる.

(1)

$n+1$ 人から重複を許して $r+1$ 人の役を選ぶ組合せを考える. $n+1$ 人の中に含まれる特定の人物 A を選ぶか選ばないかで場合に分けて数える.

(i)

A を選ぶ場合. $n+1$ 人から残りの $r$ 人の役を選ぶ ${}_n\mathrm H_r$ 通りの組合せがある.

(ii)

A を選ばない場合. 残りの $n$ 人から $r+1$ 人の役を選ぶ ${}_n\mathrm H_{r+1}$ 通りの組合せがある.

(i), (ii) は同時に起こらないから, \[ {}_{n+1}\mathrm H_{r+1} = {}_n\mathrm H_r+{}_n\mathrm H_{r+1}\] が成り立つ.

(1)

$n > r = 0$ のとき, \[\begin{aligned} s(n+1,1) &= \{ (n+1)-1\} ! = n!, \\ s(n,0)+ns(n,1) &= 0+n\cdot (n-1)! = n! \end{aligned}\] であるから, $[1]$ が成り立つ.
　以下, $n > r > 0$ のとき, 特定の人物 A を含む $n+1$ 人を $r+1$ 個の組に分けて各組で $1$ つの円順列を作る方法を考える.

(i)

A が単独の場合. A 以外の $n$ 人を $r$ 個の組に分けて各組で $1$ つの円順列を作る $s(n,r)$ 通りある.

(ii)

A が単独でない場合. まず A 以外の $n$ 人を $r+1$ 個の組に分けてから A が誰の右隣に入るかを考えると, $ns(n,r+1)$ 通りあることがわかる.

(i), (ii) は同時に起こらないから, \[ s(n+1,r+1) = s(n,r)+ns(n,r+1) \quad \cdots [1]\] が成り立つ.

(2)

$n = 0$ のとき. \[ x^{\bar n} = s(0,0)x^0 = 1\] であるから, $[2]$ が成り立つ.
　以下, 正の整数 $n$ に関する数学的帰納法で $[2]$ を示す.

(i)

$n = 1$ のとき. \[ x^{\bar 1} = s(1,0)x^0+s(1,1)x^1 = x\] であるから, $[2]$ が成り立つ.

(ii)

与えられた正の整数 $n$ に対して $[2]$ が成り立つとする. このとき, \[\begin{aligned} &x^{\overline{n+1}} = x^{\overline n}(x+n) \\ &= \left\{\sum_{k = 0}^ns(n,k)x^k\right\}(x+n) \\ &= \sum_{k = 0}^ns(n,k)x^{k+1}+n\sum_{k = 0}^ns(n,k)x^k \\ &= \sum_{k = 1}^{n+1}s(n,k-1)x^k+n\sum_{k = 0}^ns(n,k)x^k \\ &= ns(n,0)x^0+\sum_{k = 1}^n\{ s(n,k-1)+ns(n,k)\} x^k \\ &\qquad +s(n,n)x^{n+1} \\ &= s(n\!+\!1,0)x^0\!+\!\sum_{k = 1}^ns(n\!+\!1,k)x^k\!+\!s(n\!+\!1,n\!+\!1)x^{n+1} \\ &\qquad \left(\begin{array}{ll} \because [1], & s(n,0) = s(n+1,0) = 0, \\ {} & s(n,n) = s(n+1,n+1) = 1 \end{array}\right) \\ &= \sum_{k = 0}^{n+1}s(n+1,k)x^k \end{aligned}\] となるから, $[2]$ において $n$ を $n+1$ に置き換えた等式が成り立つ.

　以上から, すべての非負整数 $n$ に対して $[2]$ が成り立つ.

(1)

$n > r = 0$ のとき, \[ {}_{n+1}\mathrm S_1 = 1, \quad {}_n\mathrm S_0+1\cdot \,{}_n\mathrm S_1 = 0+1\cdot 1 = 1\] であるから, $[1]$ が成り立つ.
　以下, $n > r > 0$ のとき, 特定の人物 A を含む $n+1$ 人を $r+1$ 個の組に分ける方法を考える.

(i)

A が単独の場合. A 以外の $n$ 人を $r$ 個の組に分ける ${}_n\mathrm S_r$ 通りある.

(ii)

A が単独でない場合. まず A 以外の $n$ 人を $r+1$ 個の組に分けてから A がどの組に加わるかを考えると, $(r+1){}_n\mathrm S_{r+1}$ 通りあることがわかる.

(i), (ii) は同時に起こらないから, \[ {}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1)\,{}_n\mathrm S_{r+1} \quad \cdots [1]\] が成り立つ.

(2)

定義により, \[\begin{aligned} x^{\underline{n+1}}+nx^{\underline n} &= x^{\underline n}(x-n)+nx^{\underline n} = x^{\underline n}\{ (x-n)+n\} \\ &= x^{\underline n}x \quad \cdots [2] \end{aligned}\] が成り立つ.

(3)

$n = 0$ のとき. \[ x^0 = {}_0\mathrm S_0x^{\underline 0} = 1\] であるから, $[3]$ が成り立つ.
　以下, 正の整数 $n$ に関する数学的帰納法で $[3]$ を示す.

(i)

$n = 1$ のとき. \[ x^1 = {}_1\mathrm S_0x^{\underline 0}+{}_1\mathrm S_1x^{\underline 1} = x\] であるから, $[3]$ が成り立つ.

(ii)

与えられた正の整数 $n$ に対して $[3]$ が成り立つとする. このとき, \[\begin{aligned} &x^{n+1} = x^nx \\ &= \left(\sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline k}\right) x = \sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline k}x \\ &= \sum_{k = 0}^n{}_n\mathrm S_k\,(x^{\underline{k+1}}+kx^{\underline k}) \quad (\because [2]) \\ &= \sum_{k = 0}^n{}_n\mathrm S_k\,x^{\underline{k+1}}+\sum_{k = 0}^nk\,{}_n\mathrm S_k\,x^{\underline k} \\ &= \sum_{k = 1}^{n+1}{}_n\mathrm S_{k-1}\,x^{\underline k}+\sum_{k = 0}^nk\,{}_n\mathrm S_k\,x^{\underline k} \\ &= 0\cdot{}_n\mathrm S_0\,x^{\underline 0}+\sum_{k = 1}^n({}_n\mathrm S_{k-1}+k\,{}_n\mathrm S_k)\,x^{\underline k}+{}_n\mathrm S_n\,x^{\underline{n+1}} \\ &= {}_{n+1}\mathrm S_0\,x^{\underline 0}+\sum_{k = 1}^n{}_{n+1}\mathrm S_k\,x^{\underline k}+{}_{n+1}\mathrm S_{n+1}\,x^{\underline{n+1}} \\ &\qquad \left(\begin{array}{ll} \because [1], & {}_n\mathrm S_0 = {}_{n+1}\mathrm S_0 = 0, \\ {} & {}_n\mathrm S_n = {}_{n+1}\mathrm S_{n+1} = 1 \end{array}\right) \\ &= \sum_{k = 0}^{n+1}{}_{n+1}\mathrm S_k\,x^{\underline k} \end{aligned}\] となるから, $[3]$ において $n$ を $n+1$ に置き換えた等式が成り立つ.

　以上から, すべての非負整数 $n$ に対して $[3]$ が成り立つ.

　特定の人物 A を含む $n+1$ 人の組分けを考える. $0 \leqq k \leqq n$ なる整数 $k$ について A が $k+1$ 人の組に分けられるとき, A と同じ組に属する人の選び方が A を除く $n$ 人から $k$ 人を選ぶ組合せの ${}_n\mathrm C_k$ 通りあり, その各場合について残りの $(n+1)-(k+1) = n-k$ 人を組に分ける方法が $B(n-k)$ 通りあるから, このような組分けの方法は ${}_n\mathrm C_kB(n-k)$ 通りある. ゆえに, \[\begin{aligned} B(n+1) &= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(n-k) = \sum\limits_{k = 0}^n{}_n\mathrm C_{n-k}B(n-k) \\ &= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k) \end{aligned}\] が成り立つ.