数学A / 場合の数

3つの箱に空なしで入れる(全射と包除原理)

実戦編数え上げ包除原理全射写像単元横断

問題

$n$ 個の異なる玉を、区別できる $3$ つの箱にどの箱も空にならないように入れる方法の総数を求めよ( $n \geq 3$ )。

ヒントを見る

全部で $3^{n}$ 通り。「どれかの箱が空」を引く。1つの箱を空にする=残り2箱に入れるで $2^{n}$ 、2つ空は $1^{n}$ 。包除で足し引き。

解答・解説

方針

条件なしの入れ方 $3^{n}$ から、少なくとも1つの箱が空になる場合を包除原理で引く。「箱 $A$ が空」は残り2箱に入れる $2^{n}$ 通り。

解答

⓪ 発想 — どう考え始めるか。 「どの箱も空でない」は直接数えにくい。条件なしから、空の箱がある場合を引く — 包除原理の出番だ。

条件なしは各玉に3択で $3^{n}$ 。「箱 $A$ が空」は残り2箱に入れて $2^{n}$ — これが3つの箱ぶん。

だが「 $A$ も $B$ も空」(残り1箱、 $1^{n}$ 通り)を2回引いているので、3つぶん足し戻す: $3^{n} - 3 \cdot 2^{n} + 3 \cdot 1^{n}$ 。

定理包除原理

∣ A \cup B \cup C ∣ = \sum ∣ A ∣ - \sum ∣ A \cap B ∣ + ∣ A \cap B \cap C ∣

① 全体と“空”の場合。 全部の入れ方は $3^{n}$ 。箱を $1, 2, 3$ とし、 $X_{i} =$ 「箱 $i$ が空」の入れ方。 $∣ X_{i} ∣ = 2^{n}$ (残り2箱に入れる)。 $∣ X_{i} \cap X_{j} ∣ = 1^{n} = 1$ (残り1箱に全部)。 $∣ X_{1} \cap X_{2} \cap X_{3} ∣ = 0$ (どこにも入れられない、 $n \geq 1$ )。

② 包除で“空あり”を数える。 $∣ X_{1} \cup X_{2} \cup X_{3} ∣ = 3 \cdot 2^{n} - 3 \cdot 1 + 0 = 3 \cdot 2^{n} - 3.$ ③ 余事象で答え。 空の箱がない入れ方は $3^{n} - (3 \cdot 2^{n} - 3) = 3^{n} - 3 \cdot 2^{n} + 3.$

まとめ 「どの箱も空でない」= 全体 $3^{n}$ から「空の箱がある」を包除で引く。 $3^{n} - 3 \cdot 2^{n} + 3$ 。これは $n$ 個の玉から $3$ 箱への全射の数でもある。数え上げ・包除・写像の融合。 $n = 3$ なら $27 - 24 + 3 = 6 = 3!$ 。

発展 — 一歩先へ。 箱を $m$ 個に増やすと、全射の数は $\sum_{k = 0}^{m} (- 1)^{k} (k m) (m - k)^{n}$ 、割る $m!$ でスターリング数 $S (n, m)$ — 「ラベルあり $\div m! =$ ラベルなし」の関係はそのまま拡張される。さらに全部の $m$ について $S (n, m)$ を足すとベル数(この単元の最終問題)— 数え上げの部品が1本の系譜でつながっている。

答

全部の入れ方 $3^{n}$ から「ある箱が空」を包除で除く。 $3^{n} - 3 \cdot 2^{n} + 3 \cdot 1^{n} = 3^{n} - 3 \cdot 2^{n} + 3$ 。

別解

分割してからラベルを貼る(2段階の構成)。 順序を変えて、先に中身のグループ分け、後から箱の名前を付ける。

$n$ 個の玉を「区別のない3つの非空グループ」に分ける方法の数を $S$ とする(スターリング数と呼ばれる)。グループが決まれば、3つの箱への割り当ては $3! = 6$ 通り。よって求める数は $6 S$ 。

逆に本解の包除の結果から $S = \frac{3 ^{n} - 3 \cdot 2 ^{n} + 3}{6}$ が読める。たとえば $n = 4$ : 全射は $81 - 48 + 3 = 36$ 通りで、 $S = 6$ — 4人を3グループに分ける6通り( ${2, 1, 1}$ 型の $(2 4) = 6$ )と一致する。

「ラベルあり(全射) $=$ ラベルなし(分割) $\times 3!$ 」という2段階の分解は、この後のグループ分け(ベル数)の問題と地続きで、区別の有無で数がどう変わるかの感覚を鍛えてくれる。

ポイント

全体 $3^{n}$ から「空の箱がある」を余事象で引く。
「箱 $i$ が空」 $= 2^{n}$ 、「2箱空」 $= 1$ を包除で足し引き。
答えは $3^{n} - 3 \cdot 2^{n} + 3$ (3箱への全射の数)。

よくある間違い

包除の足し戻しを忘れて $3^{n} - 3 \cdot 2^{n}$ で止める(2箱空の場合を2回引いている)。
「3箱とも空」の項( $0^{n} = 0$ )を形式的に書かず、包除の項数が合っているか不安になる( $n \geq 1$ なら0なので結果は同じ)。
玉が区別できる(異なる)という前提を見落とし、重複組合せ( $(2 n - 1)$ 型)で数え始める。