数学A / 場合の数

同じ玉を分ける(整数解の個数)

★★★ 応用重複組合せ

問題

区別のできない10個の玉を、3人 A, B, C に分ける。

(1) 1個ももらえない人がいてもよいとき、分け方は何通りか。

(2) 3人とも少なくとも1個はもらうとき、分け方は何通りか。

ヒントを見る

『区別のない玉を3人に配る』= $x + y + z =$ (個数)の $0$ 以上の整数解の個数。○と仕切りの並べ方に翻訳する。(2)『全員1個以上』は先に1個ずつ配ってから、残りを $0$ 以上で分ける。

解答・解説

方針

玉が区別できないので、分け方は『各人が何個もらうか』の数の組で決まる。つまり $x + y + z = 10$ の整数の組を数える重複組合せだ。

(1)は0以上の整数の組、(2)は1以上の整数の組。

(2)は『先に全員へ1個ずつ配ってしまう』と、残りを0以上で分ける(1)と同じ形になる。この『先渡し』がコツだ。

解答

⓪ 発想 — どう考え始めるか。 玉に区別がないから、分け方を決めるのは「誰が何個か」の数の組だけだ。

つまり $x + y + z = 10$ の整数解の個数を数えればよい。これは重複組合せ、すなわち ○ と仕切りの並べ方に翻訳できる。

(2)の「 $1$ 個以上」は、先に $1$ 個ずつ配ってしまう。すると「 $0$ 個以上」の型に戻る。条件を配り済みにして標準形へ帰着させる発想だ。

公式重複組合せ:

x + y + z = n

(

\geq 0

)の整数解は

_{n + 2} C_{2}

通り

玉が区別できないので、分け方は A, B, C のもらう個数 $x, y, z$ の組で決まる。つまり $x + y + z = 10$ の整数の組を数える。

(1) 各人0個以上なので、0以上の整数の組を数える。玉10個を ○、A・B・C の区切りを仕切り | 2本で表すと、○10個と | 2本の並べ方に対応する。

○ が玉(10個)、| が人の区切り(2本)。この例は A=4・B=3・C=3

よって

$_{10 + 2} C_{2} =_{12} C_{2} = \frac{12 \times 11}{2 \times 1} = 66 (通り)$

(2) 3人とも1個以上という条件は、先に1個ずつ配ってしまうと扱いやすい。まず A, B, C に1個ずつ配ると3個使い、残りは $10 - 3 = 7$ 個。これを改めて0個以上で3人に分ければ、全員が(最初の1個があるので)必ず1個以上になる。残り7個を0以上で分ける方法は

$_{7 + 2} C_{2} =_{9} C_{2} = \frac{9 \times 8}{2 \times 1} = 36 (通り)$

まとめ:『1個以上』を『先に1個ずつ渡して、残りを0個以上に』と読みかえるこの手は、 $x, y, z \geq 1$ を $x^{'}, y^{'}, z^{'} \geq 0$ ( $x = x^{'} + 1$ など)に置きかえたのと同じだ。条件を消して基本の形に戻すのが、重複組合せの応用の定番だ。

発展 — 一歩先へ。 (2)の答え $36$ は、 $10$ を $3$ 個の正の整数の順序つきの和に書く方法の数と同じだ。こうした順序つきの分け方を、整数の「組成」という。

一般に、正の整数 $r$ を $n$ 個の正の整数の順序つき和に書く方法は $(n - 1 r - 1)$ 通り。 $r$ 個の玉のあいだ $r - 1$ か所から、仕切りを入れる $n - 1$ か所を選ぶ、と見れば出る。

個数を問わず、 $r$ を何個かの正の整数の和に書く方法をすべて足すと $2^{r - 1}$ 通り。 $r - 1$ か所の各すきまで、仕切りを入れるか入れないかを選ぶからだ。順序を区別しない「分割」とは別物で、こちらはすきまの選び方で数えられる。

答

(1) 66通り (2) 36通り

別解

別解 — 「 $0$ 個の人がいる」場合を包除で除く(補集合のルート)。 (2)を先渡しせず、(1)の $66$ 通りから「誰かが $0$ 個」の分け方を引く。

まず「 $A$ が $0$ 個」の分け方を数える。 $A = 0$ なら残り $10$ 個を $B, C$ に $0$ 個以上で分けるので、 $B$ の個数が $0$ 〜 $10$ で $11$ 通り。 $B$ だけ、 $C$ だけが $0$ の場合も、同じく $11$ 通りずつ。

ただし「 $A, B$ がともに $0$ 」だと $C$ が $10$ 個で $1$ 通り。こうした $2$ 人が $0$ の場合を引きすぎるので、足し戻す。 $3$ 人とも $0$ は和が $10$ にならず、起こらない。

包除でまとめると

$66 - (1 3) \times 11 + (2 3) \times 1 - 0 = 66 - 33 + 3 = 36.$

先に $1$ 個ずつ配る本解と同じ $36$ 通り。少し手間だが、条件を「禁止事象」として包除で処理する練習になる。

ポイント

区別しない玉の分配 = $x_{1} + \dots + x_{n} = r$ の整数の組の数
0以上の整数の組 → $_{r + n - 1} C_{n - 1}$
1以上は「先に1個ずつ配る」= 置きかえで0以上に戻す

よくある間違い

玉を区別できるものと思い、 $3^{10}$ などの重複順列で数える(玉は区別しないので配分の数)。
(2)で「 $1$ 個以上」を忘れて $0$ 個以上のまま数え、 $66$ と答える。
(2)を包除で進めるとき「 $1$ 人が $0$ 個」を引きすぎたまま直さず、先渡しの簡単な手にも気づかない。