数学A / 場合の数

重複組合せ(果物の選び方)

★★★ 応用重複組合せ

問題

りんご、みかん、なしの3種類の果物が、それぞれ十分たくさんある。この中から合計8個を買う。同じ種類を何個買ってもよく、買わない種類があってもよい。買い方は全部で何通りあるか。

ヒントを見る

同じ種類を何個買ってもよい=順番でなく『各種類を何個』の配分。 $8$ 個の ○ と、種類の境目を表す仕切りを並べる問題に翻訳できる — 仕切りは何本必要?

解答・解説

方針

「3種類、合計8個、各種類は0個でもよい」— これは重複組合せの典型だ。

うまい数え方は、記号の並べ方に置きかえること。果物8個を ○ で、種類の区切りを 2本の仕切り | で表す。たとえば $◯ ◯ ∣ ◯ ◯ ◯ ∣∣ ◯ ◯ ◯$ なら「りんご2・みかん3・なし3」だ。

こうすると、買い方の数が「○と|の並べ方」の数と同じになる。

解答

⓪ 発想 — どう考え始めるか。 問題の形は「 $3$ 種類・合計 $8$ 個・ $0$ 個も可」。

果物そのものを並べるかわりに、○ $8$ 個と仕切り $2$ 本の列に置き換える。すると、買い方と記号列がちょうど $1$ 対 $1$ で対応する。

ものの配分を、記号の並べ替えに翻訳する。重複組合せの核心は、この対応を見つけることにある。

公式重複組合せ:

n

種類から重複を許して

r

個 →

_{n} H_{r} =_{n + r - 1} C_{r}

(○ と仕切り | の並べ方)

3種類から合計8個を選ぶ問題を、「記号の並べ方」に置きかえる。果物を ○ で表し、りんご・みかん・なしの3グループを2本の仕切り | で区切る。たとえば

○ が果物、| が仕切り。○ 8個と | 2個の並べ方(この例はりんご2・みかん3・なし3)

は「りんご2個、みかん3個、なし3個」を表す。買わない種類があるときは、その区画の ○ が0個になる(仕切りがとなり合う)だけで、ちゃんと表せる。

買わない種類は「仕切りがとなり合う」で表せる(この例はりんご3・みかん0・なし5)

こうすると、買い方は「○を8個、|を2個、合わせて10個を1列に並べる」並べ方とぴったり1対1で対応する。10か所のうち、仕切り | を置く2か所を選べば並びが決まるので

$_{10} C_{2} = \frac{10 \times 9}{2 \times 1} = 45 (通り)$

まとめ:これは「 $x + y + z = 8$ を満たす0以上の整数の組が何通りか」を数えるのと同じだ。一般に、 $n$ 種類から重複を許して $r$ 個選ぶ重複組合せは、仕切り $n - 1$ 本と ○ $r$ 個の並べ方 $_{n + r - 1} C_{n - 1}$ で求まる。ここでは $n = 3, r = 8$ で $_{10} C_{2}$ になる。

発展 — 一歩先へ。 この $45$ という数は、 $(x + y + z)^{8}$ を展開したときに現れる項の種類の数と同じだ。

展開すると $x^{i} y^{j} z^{k}$ ( $i + j + k = 8$ )の形の項が出る。指数の組 $(i, j, k)$ を選ぶことは、りんご・みかん・なしの個数を選ぶことにほかならない。だから項の種類は $45$ 通りになる。

このように「重複を許して選ぶ」数え上げは、多項式の展開や母関数と地続きだ。選び方を式の項に翻訳すると、代数の道具がそのまま数え上げに使える。

答

45通り

別解

別解 — りんごの個数で場合分けして足す(苦手な人向けの素朴なルート)。 仕切りの並べ方に翻訳せず、正面から数えてみる。

りんごの個数を $a$ 個と決める。 $a$ は $0$ から $8$ まで動く。

りんごを $a$ 個にすると、残りの $8 - a$ 個をみかんとなしの $2$ 種類に分けることになる。みかんを何個にするかで分け方が決まり、みかんは $0$ 個から $8 - a$ 個まで選べるので $9 - a$ 通り。

あとは $a$ を動かして足し合わせる。

$a = 0 \sum 8 (9 - a) = 9 + 8 + 7 + \dots + 1 = 45.$

仕切りの発想がぱっと出なくても、 $1$ つの種類を固定して残りを数えるだけでたどり着ける。本解と同じ $45$ 通りだ。

ポイント

重複組合せは「○(品物)と |(仕切り)の並べ方」に置きかえる
$n$ 種類から重複を許して $r$ 個 → $_{n + r - 1} C_{n - 1}$
「 $x_{1} + \dots + x_{n} = r$ の0以上の整数の組の数」と同じ

よくある間違い

○ と仕切りを区別のあるものと思い、順列 $_{10} P_{2}$ で数える(どちらも同種の記号なので組合せ)。
仕切りの本数を種類数と同じ $3$ 本にしてしまう(区切りは種類数 $- 1 = 2$ 本)。
「買わない種類があってもよい」を見落とし、各種類を $1$ 個以上として不要な先渡しを始める。