中等教育前期の数学/代数編/下巻/順列と組み合わせのソースを表示

== 階乗 ==
場合の数の計算方法の始めとして、n個の異なったものを並べ換える仕方の数を数える。
まず最初に並べるものはn個、次に並べるものは(n-1)個、その次に並べるものは(n-2)個 ... とだんだんと選べるものの数が減って行き、最後には1個しか残らなくなることに注目すると、この事柄に関する場合の数は 
:<math>
 n (n-1) (n-2) \times 3 \times 2 \times 1
</math>
となることが分かる。
ここで、
:<math>
 n! \equiv n (n-1) (n-2) \times 3 \times 2 \times 1
</math>
を定義するとこのときの場合の数は、n!であると言うことが出来る。

n!をnの階乗（かいじょう、factorial）と呼ぶ。

=== 問題例 ===
* 問題
:<math>
3!,4!,5!,6!,\cdots 10!
</math>
をそれぞれ計算せよ。

* 解答
:<math>
n! = 1 \times 2 \times \times n
</math>
を用いて計算すればよい。
答えは、
:<math>3! = 6</math>
:<math>4! = 24</math>
:<math>5! = 120</math>
:<math>6! = 720</math>
:<math>7! = 5040</math>
:<math>8! = 40320</math>
:<math>9! = 362880</math>
:<math>10! = 3628800</math>
となる。


* 問題
それぞれに1から5までの数字が書かれた5枚のカードが置いてある。
このカードを並べかえたとき、
(1)カードの並べ方の数、 (2)偶数となるカードの並べ方の数、 (3)奇数となるカードの並べ方の数 をそれぞれ計算しなさい。

* 解答
(1)
カードの数が5枚でそれぞれが区別できることから、カードの並べ方の数は
:<math>5!</math>
となり、120となる。

(2)
偶数を得るためには一の位である最も右に出るカードが、偶数となればよい。
このようなカードは2と4であり、それぞれに対して後の4枚は自由に選んでよい。
このため、このようなカードの並べ方は、
:<math>2 \times 4! = 48</math>
となる。

(3)
奇数を得るためには一の位である最も右に出るカードが、奇数となればよい。
このようなカードは1,3,5であり、それぞれに対して後の4枚は自由に選んでよい。
このため、このようなカードの並べ方は、
:<math>3 \times 4! = 72</math>
となる。一方、5枚のカードを並べかえて得られる数は必ず偶数か奇数の
どちらかであるので、(1)の結果から(2)の結果を引くことによっても
(III)の結果は得られるはずだが、実際にそれを計算すると
:<math>120 - 48 = 72</math>
となり、確かにそのようになっている。

* 問題
「0」,「1」,「2」,「3」,「5」と書かれた5枚のカードがある。これを並びかえたとき、
:(1)5桁の数、 (2) 5桁の偶数、(3) 5桁の奇数、(4) 5桁の5の倍数
はいくつできるかそれぞれ求めなさい。

* 解答
(1)
先頭が0になったときには5桁の数にならないことに注意すればよい。求める場合の数は
:<math>4 \times 4! = 96</math>
となる。

(2)
最初が0でなく最後が0か2である数を数えればよい。まず、最後が0であるときには、残りの4枚は任意であるので
:<math>4! = 24</math>
通りの組み合わせがある。

次に、最後が2であるときには最初は0であってはいけないので、
:<math>3 \times 3! = 18</math>
通りある。
2つを合わせた数が5桁の偶数となる場合の数である。答えは、
:<math>24 + 18 = 42</math>
となる。

(3)  
(1)の結果から(2)の結果を引けばよいが、ここではその結果が正しいかどうか
確かめるためにも5桁の奇数が得られる組み合わせを数え上げてみる。
5桁の奇数を得るためには最後の数は1,3,5のいずれかでなくてはならない。
このうちのどの場合についても5桁の数を得るためには最初の数が0で
あってはならないのでそれぞれの場合の数は、
:<math>3 \times 3 \times 3! = 54</math>
となりこれが5桁の奇数となる場合の数である。
(2)の結果と足し合わせると確かに(1)の結果と等しい96となる。

(4)
5の倍数を得るためには最後の数が0か5であればよい。
このとき最後が0になる場合の数は他の4つが任意であるため
:<math>4! = 24</math>
存在する。次に、最後が5になる場合の数は最初の数が0であってはならないため
:<math>3 \times 3! = 18</math>
だけ存在する。
よって答えは
:<math>24 + 18=42</math>
となる。

== 順列 ==
n個の異なったものからr個を選んで、順番をつけて並べる仕方の数を、<math> {}_n{}P_r </math>と書く。
また、このような計算の仕方を 順列（じゅんれつ、英：permutation） という。
この数は、最初に並べるものはn個、次に並べるものは(n-1)個、その次に並べるものは(n-2)個 ... 最後には(n-(r-1))個というように、だんだんとるものの数が減って行くことに注目すると、
:<math> {}_n{}P_r = n (n-1) (n-2) \times (n-r+1) = \frac{n!}{(n-r)!}</math>
が得られる。

=== 問題例 ===

* 問題

(1)
:<math>{} _5 P  _3</math>

(2)
:<math>{} _4 P  _2</math>

(3)
:<math>{} _7 P  _3</math>

(4)
:<math>{} _{10} P  _5</math>

(5)
:<math>{} _{10} P  _1</math>

(6)
:<math>{} _7 P  _0</math>
をそれぞれ計算しなさい。

* 解答
それぞれ
:<math>{} _n{}P _r = n (n-1) (n-2) \times (n-r+1) = \frac{n!}{(n-r)!}</math>
を用いて計算すればよい。

答えは、
(1)
:<math>{} _5 P  _3 = 5 \times 4 \times 3 = 60</math>

(2)
:<math>{} _4 P  _2 = 4 \times 3 = 12</math>

(3)
:<math>{} _7 P  _3 = 7\times 6\times 5 = 210</math>

(4)
:<math>{} _{10} P  _5 = 10\times 9\times 8\times 7\times 6 = 30240</math>

(5)
:<math>{} _{10} P  _1 = 10 </math>

(6)
:<math>{} _7 P  _0 = \frac {7!}{7!} = 1</math>
となる。

(5)と(6)については一般的に整数nに対して
:<math>{} _n P _1 = n</math>
:<math>{} _n P _0 = 1</math>
が得られる。このとき
:<math>{} _n P _0 = 1</math>
は元々の順列の定義からすると"n個のものの中から1つも選ばない場合の数"に対応しており、少々不自然なように思えるが、このように値を置いておくと便利であるため通常このように置く。ただし、あまり実際の場合の数の計算でこのような値を扱うことは多くはないといえる。

== 組み合わせ ==
n個の異なったものからr個を選んで、順番をつけずに並べる仕方の数を、<math> {}_n{}C_r </math>と書き、このような計算を 組み合わせ（くみあわせ、英：combination） という。
例えば、いくつもあるボールに番号がふってあるなどの方法で、それぞれのボールが区別できるn個のボールが入った箱の中からr個のボールを取りだす時、取りだしたボールを取りだした順に並べるとすると、この場合の数は順列<math>{} _n{}P _r</math>に対応する。

一方、取りだしたボールの種類が重要であり取りだした順番が特に必要でないときには、この場合の数は組み合わせ<math>{} _n{}C _r</math>に対応する。これらの数はお互いに異なった場合の数であり、互いに異なった計算法が必要となる。

<math>{} _n{}C _r</math>は、<math>{} _n{}P _r</math>通りの並べ方を作った後にそれらの並びを無視したものに等しい。ここで、r個を取りだして作った並びについて、並べ方を無視するとr!個の並びが同一視されることがわかる。

なぜなら、r個のお互いに区別できる数を自由に並び換える場合の数はr!であり、それらが全て同一視されるとすれば全体の場合の数は
r!の分だけ減ることになるからである。よって、
:<math> {}_nC_r =\frac { {}_nP_r }{r!} = \frac{n!}{(n-r)!r!}</math>
が得られる。


=== 問題例 ===
*問題

(1)
:<math>{} _5C _2</math>

(2)
:<math>{} _7C _3</math>

(3)
:<math>{} _{10}C _1</math>

(4)
:<math>{} _8C _0</math>

を計算しなさい。

*解答
それぞれについて
:<math>{}_nC _r =\frac { {}_nP _r }{r!} = \frac{n!}{(n-r)!r!}</math>
を用いて計算すればよい。

(1)
:<math>{} _5C _2 = \frac {5\times 4}{2\times 1} = 10</math>

(2)
:<math>{} _7C _3 = \frac { 7\times 6\times 5} { 3\times 2\times 1} = 35</math>

(3)
:<math>{} _{10}C _1 = \frac {10} {1} = 10</math>

(3)
:<math>{} _8C _0 = 1 </math>
となる。(IV)については一般に整数nに対して
:<math>{} _nC _0 = 1</math>
を定義する。

これはもともとの組み合わせの計算としてはn個の物体のなかから0個の物体を選ぶ場合の数に対応しており、
実際にはこのような場合の数を計算しようと考えることはあまりないと思われるが、計算の都合上のため定義を上のようにする。
また、上の計算では
:<math>{} _n{}C _r =\frac { {}_n{}P _r }{r!}</math>
の式をそのまま用いると、
:<math>{} _nC _0 = \frac {{} _nP _0} {0!} = \frac 1 {0!} = 1</math>
つまり、
:<math>0! = 1</math>
となっている。

実際には階乗の計算は整数nについてはnから1までを下がりながらかけ算していくという仕方で計算されていたので、上の結果は変に思える。
しかし実際には、より進んだ理論によってこの結果は正当化されるのであり、
この場合も{{ruby|便宜|べんぎ}}上
:<math>0! = 1</math>
を0の階乗の定義として受けいれるのである。

* 問題
5個のボールが入ったボール入れから2つのボールを取りだすとき(ボールはそれぞれ区別できるものとする。)2つのボールの選び方は、何通りあるか計算しなさい。

* 解答
ボールの取りだし方は組み合わせの数を用いて計算できる。
5つのボールの中から2つを取りだすのであるからその場合の数は、
:<math>{} _5C _2 = \frac {5!}{2!3!} = \frac { 5 \cdot 4 \cdot 3 \cdot 2\cdot 1}{(3 \cdot 2 \cdot 1)( \cdot 2 \cdot 1)}</math>
:<math>= 10</math>
となる。よって、ボールの取りだし方は10通りであることがわかる。

* 問題
6個の互いに区別できるボールが入った箱がある。
この中から (1)3つのボールと2つのボールを取りだす方法の場合の数、(2)2つのボールを取り出すことを2回くり返し、それぞれを別の互いに区別できる袋にいれる場合の数、(3)2つのボールを取り出すことを2回くり返し、それぞれを別の互いに区別できない袋にいれる場合の数、をそれぞれ計算しなさい。

* 解答
(1)
最初にボールを取りだすときには、6つのボールの中から3つのボールを取りだすことからその場合の数は
:<math>{} _6C _3</math>
だけある。また、次にそれを取り除いた中から2つのボールを取り除くときには
その取りだし方は、
:<math>{} _3C _2</math>
だけある。
よって、このときの場合の数は
:<math>{} _6C _3 \times {} _3C _2 </math>
だけになる。実際この値を計算すると、
:<math>{} _6C _3 \times {} _3C _2 = 20 \times 3 = 60</math>
となり、60通りであることが分かる。

(2)

(1)の場合と同様に6つのボールの中から2つのボールを
取りだすことからその場合の数は
:<math>{} _6C _2</math>
だけある。また、次にそれを取り除いた中から2つのボールを取り除くときには
その取りだし方は、
:<math>{} _4C _2</math>
だけある。
よって、このときの場合の数は
:<math>{} _6C _2 \times {} _4C _2 </math>
だけになる。実際この値を計算すると、
:<math>{} _6C _2 \times {} _4C _2 = 15 \times 6 = 90</math>
となり、90通りであることが分かる。

(3) 
(2)と同じ計算で値を求めることが出来るが、今回はボールをいれた袋が
互いに区別できないことに注意しなくてはならない。
このことによって、起こりうる場合の数は(II)の場合の半分になるので
求める場合の数は45通りとなる。


<math> {}_n{}C_r </math>について以下の式が成り立つ。
:<math> {}_nC_r = _n C _{n-r}</math>,
:<math> {}_n C _r = _{n-1} C_r + _{n-1} C _{r-1}</math>


導出
:<math> {}_n{}C_r = \frac{n!}{(n-r)!r!}</math>
を用いると、
:<math> {}_n{}C_{n-r} = \frac{n!}{(n-(n-r))!(n-r)!}</math>
:<math> = \frac{n!}{(r!(n-r)!}</math>
:<math> = {}_n{}C_r </math>
が得られ、示された。

同様に
:<math> {}_n{}C_r = \frac{n!}{(n-r)!r!}</math>
を用いると、
:<math> {}_{n-1} C_r + _{n-1} C _{r-1}</math>
:<math>= \frac {(n-1)!}{(n-1-r)!r!} +\frac {(n-1)!}{(n-r)!(r-1)!} </math>
:<math>= \frac {(n-r)}n  {}_n{}C_r +\frac r n  {}_n{}C_r</math>
:<math>=  {}_n{}C_r</math>
となり示された。

2つ目の式は、"n個のものからr個を選ぶ仕方の数は、次の数の和である。最初の1つを選ばずに他のn-1個からr個を選ぶ仕方の数と、最初の1つを選んで他のn-1個からr-1個を選ぶ仕方の数との和である。"ということを表している。


* 問題例
:<math>{} _nC _r =  _n C  _{n-r}</math>
を用いて
(1)
:<math>{} _5C _3</math>

(2)
:<math>{} _7C _4</math>

(3)
:<math>{} _{10}C _9</math>

(4)
:<math>{} _8C _5</math>
をそれぞれ計算しなさい。

* 解答
上の式を用いて計算することが出来る。もちろん直接計算しても
答えを得ることが出来るが、通常は簡単化してから計算した方が楽である。
(1)
:<math>{} _5C _3 = {} _5C _{5-3} = {} _5C _2 = 10</math>

(2)
:<math>{} _7C _4= {} _7C _{7-4}={} _7C _3 = 35</math>

(3)
:<math>{} _{10}C _9= {} _{10}C _{10-9}= {} _{10}C _1 = 10</math>

(4)
:<math>{} _8C _5= {} _8C _{8-5}= {} _8C _3= 56</math>
となる。 

* 問題
図のようなルートを左下の点から右上の点まで歩いて行く人がいる。
ただし、この人は右か上にしか進めないとする。このとき、
:(1) 左下から右上まで進む仕方の数
:(2) 点Aを通過して右上まで進む仕方の数
を計算せよ。ただし点Aは*と書かれている点のすぐ下の通路のことをさしている。
それぞれのルートは途切れていない縦4つ、横5つの{{ruby|碁盤目|ごばんもく}}上のルートに
なっていることに注意しなさい。

 
 ___________
 |_|_|_|_|_|
 |_|_|*|_|_|
 |_|_|_|_|_|
 |_|_|_|_|_|


* 解答

(1)
左下にいる人は9回進むことで右上の点に辿り着ける。そのため、左下にいる人が選びうるルートの数は9回のうちのどの回で右ではなく上を
選ぶかの場合の数に等しい。このような場合の数は、9回のうちから自由に4つの場所を選ぶ方法に等しく、組み合わせを用いて書くことが出来る。実際に9回のうちから自由に4つの場所を選ぶ方法は、
:<math>{} _9C _4</math>
で書かれる。この量を計算すると、
:<math>{} _9C _4 = 126</math>
であることがわかる。

(2)
点を通過して進むルートの数は点Aの左の点までいってから点Aを通過し、点Aの右の点を通って右上の点までいく仕方の数に等しい。
それぞれのルートの数は(1)の方法を用いて計算することができる。この数を実際に計算すると、
:<math>{} _4 C  _2 \times {} _4 C  _2 = 6 \times 6 = 36 </math>
となり、36通りであることが分かる。

[[Category:中学校数学|しゆんれつとくみあわせ]]
[[Category:中高一貫教育 数学|しゆんれつとくみあわせ]]