(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 \geqq 0,\ \cdots,\ x_n \geqq 0\] となり, $x_1,$ $\cdots,$ $x_n$ はそれぞれ $r$ 個の〇と $n-1$ 本の｜の順列において｜で仕切られた〇の個数に対応するから, 求める場合の数は \[ {}_{n+r-1}\mathrm C_{n-1} = {}_{n+r-1}\mathrm C_r = \frac{(n+r-1)!}{(n-1)!r!}\] である.

(2)

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

(I)

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

(i)

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

(ii)

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

(iii)

各箱に入る玉の個数がすべて異なる場合は, $N-3k-1$ 通り. この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $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}\] が成り立つ.

　特定の人物 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}$ が成り立つ.

　特定の人物 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}\] が成り立つ.