東北大学 1999年度 後期日程 第2次学力試験理系（後期）数学 第3問

(1)
各カードは $A,B,C$ の3つの箱のいずれかに入るので、空箱を許せば $3^n$ 通りである。

少なくとも1つの箱が空である場合を引く。ある1つの箱を空にする方法は3通りで、そのとき各カードは残り2箱のどちらかに入るので $2^n$ 通りである。ただし、2つの箱が空である場合、つまり全カードが1つの箱に入る場合は二重に引かれている。これは3通りである。したがって、どの箱にも少なくとも1枚入る入れ方は $3^n-3\cdot 2^n+3$ 通りである。

(2)
(1)で数えた入れ方のうち、どれかの箱に少なくとも1つのペアが入る場合を求める。余事象として、「どのペアも同じ箱に入らない」場合を数える。

まず空箱条件を考えない。各ペア $(2k-1,2k)$ について、2枚を異なる箱に入れる方法は $3\cdot 2=6$ 通りである。ペアは $l$ 個あるので $6^l$ 通りであり、残りの $n-2l$ 枚は自由に3箱へ入れられるので $6^l{3}^{n-2l}$ 通りである。

この中から、空箱があるものを除く。例えば箱 $A$ が空であるとする。このとき各ペアの2枚は、箱 $B,C$ に1枚ずつ入らなければならないので、各ペアについて2通りである。また、残りの $n-2l$ 枚は箱 $B,C$ のどちらかに入るので $2^{n-2l}$ 通りである。したがって、指定した1つの箱が空で、かつどのペアも同じ箱に入らない場合は $2^l{2}^{n-2l}=2^{n-l}$ 通りである。空にする箱は3通りある。

2つの箱が空である場合は、ペアの2枚を異なる箱に入れることができないため起こらない。よって、どのペアも同じ箱に入らず、かつ3箱すべてが非空である入れ方は $6^l{3}^{n-2l}-3\cdot 2^{n-l}$ 通りである。

したがって求める場合の数は、(1)からこの余事象を引いて $3^n-3\cdot 2^n+3-6^l{3}^{n-2l}+3\cdot 2^{n-l}$ である。

ペアが同じ箱に入る事象について包含排除を直接行う。選んだペアを1枚の超カードとみなす。

(1)

包除原理より、3箱すべてを使う入れ方は$$3^n-3\cdot 2^n+3.$$(2)

$j$ 個の指定したペアがそれぞれ同じ箱に入るとする。この $j$ ペアを各1個のまとまりと見れば、独立な対象は $n-j$ 個である。3箱すべてを使う入れ方は$$3^{n-j}-3\cdot 2^{n-j}+3.$$したがってペア事象の包含排除により求める数は$$\sum _{j=1}^l(-1{)}^{j+1}{}_l{\mathrm{C}}_j(3^{n-j}-3\cdot 2^{n-j}+3)\mathrm{.}$$二項展開で整理すると$$3^n-3\cdot 2^n+3-2^l{3}^{n-l}+3\cdot 2^{n-l}\mathrm{.}$$$$2^l{3}^{n-l}=6^l{3}^{n-2l}$$だから$$3^n-3\cdot 2^n+3-6^l{3}^{n-2l}+3\cdot 2^{n-l}\mathrm{.}$$