成績を上げるためには自宅学習!

各記事に対応する動画の作成開始しました。
チャンネル登録お願いいたします。

詳細はこちら

n個のボールを3つの箱に入れる問題【1996年 東京大】

n個のボールを3つの箱に入れる問題数学IAIIB

スポンサーリンク

(3)の別解Ⅱ

1から $n$ まで異なる番号のついた $n$ 個のボールを,区別のつかない3つの箱に入れる場合,その入れ方は全部で何通りあるか。空箱があってもよい。

ヒロ
ヒロ

次は漸化式を利用した解法も説明しておこう。

求める場合の数を $a_n$ として,$n$ 個のボールを入れた状態から $n+1$ の番号のついたボール(ボールAとする)の入れ方を考える。
$n=1$ のときは,箱を区別しないからボールの入れ方は1通りしかないから $a_1=1$ となる。
また,$n=2$ のときは,1つの箱に2個とも入れるか,2つの箱に1個ずつ入れるかの2通りあるから $a_2=2$ となる。
$n$ 個のボールを入れた状態には,
 (i) 2つの箱が空のとき(1通り)
 (ii) (i)以外のとき($a_n-1$ 通り)
の2種類の状態がある。
(i)のとき,ボールAの入れ方としては,$n$ 個のボールが入っている箱に入れるか,空の箱に入れるかの2通りがある。
(i)以外のときのボールAの入れ方は,3つの箱のうち,どの箱に入れるかを考えて3通りある。
(ii)のときが起こるのが $n$ が2以上のときだから $n\geqq2$ のとき
\begin{align*}
&a_{n+1}=1\Cdota2+(a_n-1)\Cdota3 \\[4pt]
&a_{n+1}=3a_n-1~\cdots\cdots ①
\end{align*}
が成り立つ。ここで,$a_1=1,~a_2=2$ だから①は $n=1$ のときも成り立つ。
①より,
\begin{align*}
a_{n+1}-\dfrac{1}{2}=3\left(a_n-\dfrac{1}{2}\right)
\end{align*}
数列$\left\{a_n-\dfrac{1}{2}\right\}$ は初項 $a_1-\dfrac{1}{2}=\dfrac{1}{2}$,公比3の等比数列となるから,
\begin{align*}
&a_n-\dfrac{1}{2}=\dfrac{1}{2}\Cdota3^{n-1} \\[4pt]
&a_n=\dfrac{3^{n-1}+1}{2}
\end{align*}
よって,求める入れ方は全部で $\dfrac{3^{n-1}+1}{2}$ 通り。

タイトルとURLをコピーしました