2015/05/03

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

分野: 場合の数  レベル: 入試対策

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

例題

例題1

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

重複組合せの例題

解答1(重要):「三種類の玉から4つ選ぶ方法」と「◯4つと仕切り2つを一列に並べる方法」は図のように1対1に対応するので,求める場合の数は $\dfrac{6!}{4!2!}=15$ 通り。

解答2(検算):3種類のものから重複を許して4個選ぶ場合の数なので,重複組合せの公式より${}_3\mathrm{H}_4={}_6\mathrm{C}_4=15$ 通り。

重複組合せの公式について

重複組合せの問題は先程の解答1のような「仕切りの考え方」で必ず解けます。そのため,${}_n\mathrm{H}_r$ という記号や,重複組合せの公式(コンビネーションで書く方法)を覚えていなくても全く問題はありません。

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

仕切りの考え方による重複組合せの公式の証明

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

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

例題2

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

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

解答2:(*)までは解答1と同じ。重複組合せの公式より${}_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)$ の $6$ 通り。

整数解の個数

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

例題3

$x+y+z+w=6$ という方程式について,
(1)非負整数解の個数を求めよ。
(2)正の整数解の個数を求めよ。

解答

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

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

まとめ

  • 重複組合せの公式よりも仕切りの考え方が重要
  • 「全てを1つ以上選ぶ」パターンの場合,予め1つずつ分配しておく
重複は「ちょうふく」と読むのが正しいですが,最近は「じゅうふく」と読むのもOKみたいですね。

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

分野: 場合の数  レベル: 入試対策