20C入試問題研究に戻る96東大理科後期
$n$ を正の整数とし， $n$ 個のボールを3つの箱に分けて入れることを考える．ただし，1個のボールも入らない箱があってもよいものとする．次の各問いに答えよ．
(1) 1から $n$ まで異なる番号のついた $n$ 個のボールを， ${\rm A}$ ， ${\rm B}$ ， ${\rm C}$ と区別された3つの箱に入れる場合， その入れ方は全部で何通りあるか，また，3つの箱全部に少なくとも１つ入る入れ方は全部で何通りあるか．
(2) 互いに区別のつかない $n$ 個のボールを， ${\rm A}$ ， ${\rm B}$ ， ${\rm C}$ と区別された3つの箱に入れる場合， その入れ方は全部で何通りあるか，また，3つの箱全部に少なくとも１つ入る入れ方は全部で何通りあるか．
(3) 1から $n$ まで異なる番号のついた $n$ 個のボールを， 区別のつかない3つの箱に入れる場合，その入れ方は全部で何通りあるか， また，3つの箱全部に少なくとも1つ入る入れ方は全部で何通りあるか．
(4) $n$ が 6 の倍数 $6m$ であるとき，$n$ 個の互いに区別のつかないボールを， 区別のつかない3つの箱に入れる場合，その入れ方は全部で何通りあるか． また，3つの箱全部に少なくとも1つ入る入れ方は全部で何通りあるか．
96東大理科後期解答
$n$ を正の整数とし， $n$ 個のボールを3つの箱に分けて入れることを考える．ただし，1個のボールも入らない箱があってもよいものとする．次の各問いに答えよ．
(1) 入れ方は \[3^n \ (通り) \] どれか2つに入る場合は $3(2^n-2)$ 通り,どれか一つに入る場合は $3$ 通りだから，3つの箱全部に入るのは \[ 3^n- \{3(2^n-2)+3\}=3^n-32^n+3\ (通り) \]
(2) 求める場合の数は $x+y+z=n,\ \ x,\ y,\ z \ge 0$ となる解の個数であるから \[ {}_{n+2} \mathrm{C}_{2}=\dfrac{(n+2)(n+1)}{2}\ (通り) \] 全部に入る場合の数は $x+y+z=n,\ \ x,\ y,\ z > 0$ となる解の個数であるから \[ {}_{n-1} \mathrm{C}_{2}=\dfrac{(n-1)(n-2)}{2}\ (通り) \]
(3) グループ分けのみが問題である． \[ \left\{ \begin{array}{l} 1つのグループになる場合は１通り．\\ 2つのグループになる場合は \dfrac{2^n-2}{2!} 通り．\\ 3つのグループになる場合は \dfrac{3^n-3(2^n-2)-3}{3!} 通り． \end{array} \right. \] 総数はこの和なので， \[ \dfrac{3^{n-1}+1}{2}\ (通り) \] 全部に入る場合の数は \[ \dfrac{3^n-3(2^n-2)-3}{3!}=\dfrac{3^{n-1}-2^n+1}{2}\ (通り) \]
(4) ボールを3つに分ける個数のみことが問題である． 分け方を，異なる3数の組( $\{s,t,u\}$型 )，2数のみが同数の組( $\{s,s,t\}$型 )，3数が同数の組で考える． \[ \left\{ \begin{array}{l} 3数が同数の組にわけるのは， \{2m,\ 2m,\ 2m\} の1通り.\\ 2数のみが同数の組にわけるのは， \{k,\ k,\ 6m-2k\} で 0\leqq k \leqq 3m,\ k \ne 2m であるから， 3m 通り．\\ 異なる3数の組に分ける場合の数を x 通り，とする． \end{array} \right. \] ここで箱に区別がある場合と合わせて考えると(2)から次の表ができる． \[ \begin{array}{|c|c|c|c|c|} \hline 分け方&\{s,\ t,\ u\}型&\{s,\ s,\ t\}型&\{s,\ s,\ s\}型&総数\\ \hline 箱に区別がない場合&x&3m&1&N\\ \hline 箱に区別がある場合&6x&3\cdot3m&1&\dfrac{(6m+2)(6m+1)}{2}\\ \hline \end{array} \] したがって \[ 6x+9m+1=(3m+1)(6m+1) \] これから $x=3m^2\ (通り)$ である. \[ N=x+3m+1=3m^2+3m+1 \ (通り) \] ※ 別方法 求める場合の数を$a_m$とおく．グループ分けの個数のみが問題であるので， $a_m$は \[ x+y+z=6m,\ かつ0\leqq x\leqq y \leqq z \] となる整数の組$(x,\ y,\ z)$の個数である． $x=0$のときは， \[ y+z=6m,\ かつ0\leqq y \leqq z \] より \[ (y,\ z)=(0,\ 6m),\ \cdots,\ (3m,\ 3m) \] の$3m+1$通り． $x=1$のときは， \[ y+z=6m-1,\ かつ0\leqq y \leqq z \] より \[ (y,\ z)=(1,\ 6m-2),\ \cdots,\ (3m-1,\ 3m) \] の$3m-1$通り． よって，$a_m$は \[ x+y+z=6m,\ かつ2\leqq x\leqq y \leqq z \quad \cdots① \] となる整数の組$(x,\ y,\ z)$の個数と，$3m+1+3m-1$の和である． $①$は， \[ x-2+y-2+z-2=6(m-1),\ かつ0\leqq x-2\leqq y-2 \leqq z-2 \] なので，これを満たす整数の組$(x,\ y,\ z)$の個数は$a_{m-1}$である． よって， \[ a_m=a_{m-1}+6m \] がなりたつ．$a_0=1$なので， \begin{eqnarray*} a_m&=&a_0+\sum_{k=0}^{m-1}6(k+1)\\ &=&1+6\cdot\dfrac{(m-1)m}{2}+6m\\ &=&3m(m-1)+1+6m=3m^2+3m+1 \end{eqnarray*} このうち0を含むのは \[ \left\{ \begin{array}{l} \{s,\ t,\ u\}型では， \{0,\ k,\ 6m-k\}\ 1 \leqq k \leqq 3m-1 の 3m-1 とおり\\ \{s,\ s,\ t\}型では， \{0,\ 0,\ 6m\} と \{0,\ 3m,\ 3m\} の2 とおり\\ \{s,\ s,\ s\}型にはなし． \end{array} \right. \] よって全部にはいるのは \[ 3m^2+3m+1-(3m-1)-2=3m^2 \ (通り) \]