重複組合せの公式と例題(玉,整数解の個数)

重複組合せの公式

nn 種類のものから重複を許して rr 個選ぶ場合の数は n+r1Cr{}_{n+r-1}\mathrm{C}_r 通り。

重複組合せ(ちょうふくくみあわせ)について詳しく解説します。

重複組合せとは

重複組合せ,つまり「重複を許して」選ぶ組合せが何通りあるかを考えます。

例題1

青,赤,黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

重複組合せの例題です。

  • 青,赤,黒それぞれ何回でも使えます(重複を許す)
  • 順番は区別しません(順列ではなく組合せ)。例えば「青青赤青」と「青青青赤」は区別せず同じパターンとみなします。
解答(頑張って数える方法)

以下の15通りです。

  • 青青青青,赤赤赤赤,黒黒黒黒
  • 青青青赤,青青青黒,赤赤赤青,赤赤赤黒,黒黒黒青,黒黒黒赤
  • 青青赤赤,赤赤黒黒,黒黒青青
  • 青青赤黒,赤赤黒青,黒黒青赤

もれなくダブリなく数えるのは大変ですね…。

重複組合せの公式を使う

実は,重複組合せは以下の公式で計算できます。

nn 種類のものから重複を許して rr 個選ぶ場合の数は n+r1Cr{}_{n+r-1}\mathrm{C}_r

例題1の解答(重複組合せの公式を使う)

青,赤,黒の3種類から重複を許して4個選ぶ場合の数なので,重複組合せの公式 n+r1Cr{}_{n+r-1}\mathrm{C}_rn=3,r=4n=3,r=4 とすればよい。

つまり,3+41C4=6C4=15{}_{3+4-1}\mathrm{C}_4={}_6\mathrm{C}_4=15

15通り列挙するより簡単です!

→高校数学の問題集 ~最短で得点力を上げるために~のT50も参照してください。

重複組合せの公式の証明

まずは,例題1の場合でなぜ 6C4{}_{6}\mathrm{C}_4 になるか説明します。

例題1(再掲)

青,赤,黒の三種類の玉がたくさんある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ。

重複組合せの例題

「三種類の玉から4つ選ぶ方法」と「◯4つと仕切り2つを一列に並べる方法」は図のように1対1に対応するので,求める場合の数は 6!4!2!=6C4\dfrac{6!}{4!2!}={}_6\mathrm{C}_4 通り。

公式の証明は,上の例を一般化するだけです。

重複組合せの公式の証明

nn 種類のものから重複を許して rr 個選ぶ方法」と「rr 個の◯と n1n-1 個の仕切りを一列に並べる方法」は1対1に対応するので,そのような場合の数は n+r1Cr{}_{n+r-1}\mathrm{C}_r となる。

重複組合せの記号

nn 種類のものから重複を許して rr 個選ぶ場合の数を nHr{}_n\mathrm{H}_r と書くことがあります。

重複組合せの公式より nHr=n+r1Cr{}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_rです。

ただし,重複組合せの問題はさきほど述べた「仕切りの考え方」で必ず解けます。そのため,nHr{}_n\mathrm{H}_r という記号や,重複組合せの公式を覚える必要は全くありません。

むしろ,重複組合せの公式は仕切りの考え方を使って証明するので,仕切りの考え方を覚えておく方が重要です。

どれも1つ以上選ぶパターン

例題2

青,赤,黒の三種類の玉がたくさんある。この中から5つ玉を選ぶときに得られる色のパターンのうち,どの色の玉も一つ以上選ぶものが何通りあるか求めよ。

解答1(重要):最初に三種類の玉を1つずつ取ってくる。残り二つの玉の選び方を数えればよい(*)。それはさきほどと同様に,「玉2つと仕切り2つを一列に並べる方法」の数に等しいので 4!2!2!=6\dfrac{4!}{2!2!}=6 通り。

解答2:(*)までは解答1と同じ。重複組合せの公式より 3H2=4C2=6{}_3\mathrm{H}_2={}_{4}\mathrm{C}_2=6 通り。

解答3:これくらいなら全部列挙して検算するべきですね。

(青,赤,黒)= (2,2,1),(2,1,2),(1,2,2),(3,1,1),(1,3,1),(1,1,3)(2,2,1),(2,1,2),(1,2,2),(3,1,1),(1,3,1),(1,1,3)66 通り。

整数解の個数

重複組合せの応用として整数解の個数を求める問題は頻出です。玉の場合と全く同じ考え方でOKです。

例題3

x+y+z+w=6x+y+z+w=6 という方程式について,

(1)非負整数解の個数を求めよ。

(2)正の整数解の個数を求めよ。

解答

(1)6個のものを4つに割り当てる状況。「6個の◯と3つの仕切りを一列に並べる方法」と「非負整数解」は1対1に対応するので,9!6!3!=84\dfrac{9!}{6!3!}=84 通り。

(2)最初に x,y,z,wx,y,z,w11 ずつ分配。「残った2個の◯と3つの仕切りを一列に並べる方法」と「正の整数解」は1対1に対応するので 5!2!3!=10\dfrac{5!}{2!3!}=10 通り

重複組合せのまとめ

  • 重複組合せの公式よりも仕切りの考え方が重要
  • 「全てを1つ以上選ぶ」パターンの場合,予め1つずつ分配しておく
  • 整数解の個数も重複組合せで解けることがある

重複は「ちょうふく」と読むのが正しいですが,最近は「じゅうふく」と読むのもOKみたいですね。

Tag:数学Aの教科書に載っている公式の解説一覧