数学A 第1章 場合の数 — 組合せ

組合せについて

組合せの定義

4枚のカード , , , から 2枚のカードの(順序は考えずに)組をつくる場合の数は，すべて書き出すと

の6通りとなる．これは，順列の考え方を利用し，次のように計算することもできる．

まず，4枚のカードから2枚引いて順列を作ると，樹形図は図のようになり，その総数は 通りである．

しかし，2枚のカードの組を作る場合には，図の樹形図で例えば①，②は並ぶ順が異なるだけなので，これらは2つで1通りと数えなければならない． これら以外の順列にも同様のことがいえるので， 2枚のカードの組の総数は，順列の総数 を2で割ることにより

∴6通り

として計算できる．

このようにいくつかの組をつくる場合の数を定義しておこう．

組合せの計算

区別する 個のものから 個取り出して作る組の総数 も，先程の例と同じように考えることができる．

まず， 枚のカードから 枚引いて順列を作ると，その総数は 通りある．

順列ではなく， 枚のカードの組を作る場合には， 順列のうち 通りについては同一視することになるので， 順列の総数 を で割ることにより

順列 の計算参照

以上，まとめると

問題3組合せ〜その2〜

1. 図のように，横に4本，縦に7本の直行する平行線が引かれている． この中に長方形はいくつあるか求めよ．
2. 正十角形の対角線の本数を求めよ．

解答を見る

1. 横4本の平行線のうちから2本，縦7本の平行線のうちから2本をそれぞれ選べば，1個の長方形が定まる．
2. 10個の頂点のうち2個を選べば，1本の対角線または辺が定まる．辺の数は10本であるから，これを除いて

ボールと箱のモデル4

の定義は

「区別する5個のものから3個とりだして作る組の総数」

であったが，これはボールと箱のモデルを使って

「区別しない3個のボールを，区別する5個の箱に多くても1個配る場合の数」

といいかえることができる．これは，次のように説明できる．

準備として，3つのボールは区別しないでそれを , , とし， 箱は区別するので番号をつけ，それを

としておく．

3つの区別しないボールを，5つの区別する箱に高々1個配る場合の総数は，結局5つの箱からボールを入れるための箱を3つ選ぶ 選び方と等しくなり，これは「区別する5個のものから3個とりだして作る組の総数」と考えることができるので 通りとなる．

一般に，次のようにまとめることができる．

同じものを含む順列

同じものを含む順列の定義

例えば，6枚のカード を1列に 並べる順列の総数は次のように求めることができる．ただし，ここでは の3枚や， の2枚の並べ方の違いは区別しないものとする．

まず，カードを並べるための“部屋”を先に6つ用意しておく．

3枚の の入れる部屋の選び方は 通りあり， その選んだ部屋に を入れる．

そのそれぞれに対し，残りの部屋は3部屋であるから，2枚の の入れる部屋の選び方は 通りあり，その選んだ部屋に を入れる．

そのそれぞれに対し，残りの部屋は1つであるから，最後に を入れる．

以上から，6枚のカード を1列に 並べる順列の総数は積の法則より

∴60通り

となる．

ここで，数個の区別しないものを含む 個の順列を定義しておこう．

注 分かりやすくするため，2枚の のうち片側だけ とすると，例えば と は区別しないということである．

同じものを含む順列の計算

今みた例と同じように，一般の も，以下のように考えることができる．

まず，カードを並べるための場所を先にn個用意しておく．

個の同種のものの入れる場所の選び方は 通りあり，またそのそれぞれに対して 個の同種のものの入れる場所の選び方は 通りあり，またそのそれぞれに対して 個の同種のものの入れる場所の選び方は 通りあり， ，またそのそれぞれに対して 個の同種のものの入れる場所の選び方は 通りある．

以上から，同じものを含む 個の順列は，積の法則から

となる．

まとめると

の性質

の性質

組合せ について次の式が成り立つ．

問題6最短経路

図のように，東西に走る道路と南北に走る道路があるとする．南西の角にあるA地点から，北東の角にあるB地点に至る

最短経路について以下の問に答えよ．

1. 最短経路は全部で何通りあるか求めよ．
2. C地点を通る最短経路は何通りあるか．また，D地点を通る最短経路は何通りあるか，それぞれ求めよ．
3. C地点またはD地点を通る最短経路は何通りあるか求めよ．

解答を見る

北に1区画進むことを↑，東に1区画進むことを→で表すと，例えば図のように進む場合には

と表すことができる．

1. 北に1区画進むことを ，東に1区画進むことを で表すと，A地点からB地点への最短経路は，5個の と6個の ( ) を一列に並べる順列の総数に等しい．
3. 集合C,Dをそれぞれ

2項定理

を展開するということ

を展開すると

また， を展開すると

である．

ここでは，自然数 について， を展開した式を組合せを使って求める方法について考えてみよう． 以下では例として， の展開についてみていこう．

とは，5つの の積

のことである．この展開式は，5つの のそれぞれから， か のどちらかをとって，掛け合わせたものの和になる．

の係数はいくつになるのか

5つの のうち，1つから を選び，残りの4つから をとって掛け合わせると， が作られる．

図は，①から をとった場合のイメージである．

ここで， が作られる場合の数は，上の①から⑤の1ヶ所から を選べばよいので，組合せの考えを使って と数えることができる．

つまり， の展開式における の係数は である．

の係数はいくつになるのか

5つの のうち，2つから を選び，残りの3つから をとって掛け合わせると， が作られる．

図は，②と⑤から をとった場合のイメージである．

ここで， が作られる場合の数は，上の①から⑤の2ヶ所から を選べばよいので，組合せの考えを使って と数えることができる．

つまり， の展開式における の係数は である．

の展開式

以上の例から， の展開式における各項の係数は，それぞれ次のようになるのがわかる．

の係数は5つの のうち0ヶ所から を選ぶと考えて

の係数は5つの のうち1ヶ所から を選ぶと考えて

の係数は5つの のうち2ヶ所から を選ぶと考えて

の係数は5つの のうち3ヶ所から を選ぶと考えて

の係数は5つの のうち4ヶ所から を選ぶと考えて

の係数は5つの のうち5ヶ所から を選ぶと考えて

つまり

となる．

の展開式(2項定理)

一般に， の展開式における の係数は， 個の のうち， 個から を，残りの 個から を取り出す方法の総数 となる．このことから，次の式(2項定理(binomial theorem))が成り立つことがわかる．