earth
湘南理工学舎

 楽しく学ぶ…順列・組合せ

 順列・組合せ

(permutation(sequence without repetition)・combination)
 --目 次--
1.場の数とは
2.選び方・並べ方のいろいろ
[1]選び方
[2]重複順列(1)
[3]重複順列(2)
[4]重複順列(3)
[5]順列(階乗で表せる)
[6]順列
3.組み合わせ
[1]5人の中から3人選ぶ組み合わせは何通りか。
[2]組み合わせの性質(1)
[3]組み合わせの性質(2)
組合せと順列のまとめ
(閑話)パソコンの活用
   
1.場の数とは(number of places)
 例えばハートのトランプを並べる仕方は何通りあるかのようにある事柄には起こりうる数が何通りある。この数を「場の数」といいます。 その代表的なものに順列と組み合わせがあります。

   
2.選び方・並べ方のいろいろ
[1]選び方
2種類のカレーと4種類のドリンクの選び方は何通りか。 (「選び方の場の数」ともいう)
selection
 
 カレーショップでチキンカレーとポークカレーの2種類、ドリンクの4種類を選び、注文する仕方は何通りあるか。
カレーの選び方は2通り そのカレーに対して ドリンクの選び方は4通り です。
従って \(4 \times 2 =8 \) 通りの組み合わせがあります。
さらに食後のデザートに「アイスクリーム,ケーキ,フルーツ」の3種類を選ぶ、選択肢があれば
\(4 \times 2 \times 3 =24 \) 通りの組み合わせとなります。

[2]重複順列(1)
サイコロの目の出方は何通りか(場の数)。
 サイコロの1回目の振りでは6通り。(これはいいですよね)
その1回目の1通りに対して、2回目の振りでは6通りです。
すなわち1回目の各1通りについて6通りです。
従って、2回の振りでは \(6 \times 6=6^2=36 \) 通りあります。
n 回振れば \( 6^n \)通りあります。

[3]重複順列(2)
3つの数字を使い、出来上がる2桁の数は何通りか。
 (3つの数字の繰り返し(重複)を許して、2桁の整数を作る)
 \( \begin{bmatrix} 10の桁 & 1の桁 \\ 3通り  &  3通り  \end{bmatrix} \) ⇒\(\ 3^2 = 9\) 通り。

 
[4]重複順列(3)
3つの数字を使い、出来上がる3桁の数は何通りか。
 (3つ数字の繰り返し(重複)を許して、3桁の整数を作る)

  \( \begin{bmatrix} 100の桁&10の桁&1の桁 \\ 3通り&3通り&3通り  \end{bmatrix} \) ⇒\(\ 3^3 = 27\) 通り。


[2],[3],[4]のまとめ⇒重複順列
上記の[2],[3],[4]の並べ方、選び方を重複順列といいます。
一般的に「異なる n 個から重複(繰り返し)を許して r 個を並べる仕方は」:
❶  \(\underline{\ n^r \ } \) 通りある。
これを 重複順列 といいます。
また「n 個から r 個 をとる重複順列」という言いかたもあります。
・重複を許す並べ方
duplication
 
・重複を許さない並べ方
not to duplication
 

[5]順列(階乗で表せる) \(n!\) (premutation(factorial))
3枚のカードを1列に並べる仕方は何通りか。

重複は許さないで、並べる順番は区別する方法です。

permulation
 

・1番目は「A, B,C 」の 3 通り。
・2番目は1番目の各々について2 通り。
・3番目は2番目の各々について1 通り。
この全並べ方は \(3 \times 2 \times 1 = 6\) 通りです。

これを拡張して、次にカードが4枚(A,B,C,D )の場合の:
全並べ方は \(\color{red}{4} \times 3 \times 2 \times 1 = 24\) 通りとなります。
これは階乗の計算ですね。

一般に n 個のものを1列に並べる仕方は次の階乗で表せる。

❷:\( \underline{ n!=n・(n-1) \cdots 3・2・1} \)

\( n=0\) の時、\( 0!=1 \)と定義します。

[6]順列(permutation) \(_{n}P_{r} \)
5人の中から2人選んで、順序をつけて並べる仕方は何通りか。
選ぶ操作と順序づけして並べる操作
 結論をはじめからいうと、この並べ方を順列といいます。
重複を許さないが順序は考慮する並べ方です。
5人の名前はA,B,C,D とします。
 \(\fbox{A}\ \fbox{B}\ \fbox{C}\ \fbox{D}\ \fbox{E} \)

1人目にはA~B の 5 人が入る。(2人目は空白)
 \( (A,\Box)\ (B,\Box)\ (C,\Box)\ (D,\Box)\ (E,\Box) \)
2人目には1番目を除いた4 人が入る。
 \( AB, AC, AD, AE, BA, BC \ \cdots EC, ED\)
従って全ての並べ方は \( 5 \times 4 = 20 \) 通りです。
これの一般式が下式です。
\( \underline{n (n-1) }\)

 こんどは5人の中から3選んで並べる仕方はどうなるか。
\( (A,\Box\Box)\ (B,\Box\Box)\ (C,\Box\Box)\ (D,\Box\Box)\ \) \( (E,\Box\Box) \)
1番目にはA~B の 4 人が入る。
2番目には1番目を除いた4 人が入る。
同様にして、
3番目には1,2番目を除いた3 人が入る。
\( 5 \times 4 \times 3 = 60 \) 通りです。これの一般式が下式です。
\( \underline{ n (n-1)(n-2) } \) です。

以上をまとめると
一般的に「異なる n 個から(重複をゆるさず) r 個を選んで並べる仕方は」
 (以下を「エヌ・ピー・アール」などと呼んでいる)
❸: \( \underline{ {}_{n}P_{r}=n(n-1) \cdots (n-(r-1))} \)

\(\quad \underline{ =\frac{n!}{(n-r)!}} \)

通りあります。これを順列といいます。

\( ( \because =\frac{n(n-1) \cdots (n-(r-1))(n-r) \cdots 2 \cdot 1}{(n-r)(n-(r+1)) \cdots 2 \cdot 1} ) \)

【注記】
 \( {}_{n}P_{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!\)
 \( \quad ( 0!=1 )\)

 \( {}_{n}P_{0}=\frac{n!}{(n-0)!}=1\)

3.組み合わせ(combination) \({}_n \mathrm{ C }_r \)
[1]5人の中から3人選ぶ組み合わせは何通りか。
5人の名前はA,B,C,D とします。背中にカードを付けています。
\(\fbox{A}\ \fbox{B}\ \fbox{C}\ \fbox{D}\ \fbox{E} \)

結論を先に述べます… \( {}_n \mathrm{ C }_r={}_5 \mathrm{ C }_3  =10\) (※1)通りあります。

次の公式により求めます。
「コンビネーション n, r」などと呼んでいます。

❹: \( {}_n \mathrm{ C }_r\) \(=\frac{{}_{n}P_{r}}{r!}\) \(= \frac{順列}{重複順列} \) \(=\frac{ n(n-1) \cdots (n-(r-1))}{r!} \) \( =\frac{n!}{r! \ (n-r)!}\)


(※1): \( {}_5 \mathrm{ C }_3 = \frac{{}_{5}P_{3}}{3!}\) \(=\frac{5\cdot 4\cdot 3}{3\cdot2\cdot1}=10\)

\(r=0\), \(r=n\) のとき:
\({}_n \mathrm{ C }_0 = \) \(= \frac{ n!}{0!\ (n-0)!}= 1\)

\({}_n \mathrm{ C }_n = \) \(= \frac{ n!}{n!\ (n-n)!}= 1\)

次のようにも表せる。
右辺を2項係数といい、2項定理の係数です。
❺: \( \underline { {}_n \mathrm{ C }_r = \binom{ n }{ r } }\)

先に公式を書きましたが、これから 式❹ の導出を行います。
ここで、「3人の中から2人選ぶ組み合わせは何通りか。」をテーマにして進めます。
三人の順序を考慮せず、選ぶ方法を組み合わせといいます。
例えば{A,B}と{B,A}は同じもので、A,Bからなる集合として扱い\( \{A,B\} \)と表す。
3人から2人選んで並べる仕方は、前記[6]項より \(_{3}P_{2}=6 \) 通り。
また組み合わせ数は\(3\)通り。
\( \{A,B\} \cdots (A,B) (B,A) \)
\( \{A,C\} \cdots (A,C) (C,A) \)
\( \{B,C\} \cdots (B,C) (C,B) \)

これを次のように分解する

①3人から2人を選ぶ組み合わせの数⇒これを未知数\(\ x \) とします。
②選んだ2人を1列に並べる仕方⇒\(2!\ \) (前記[5]項の内容です)

[3人から2人を選び、並べる場合の数]\(= [\color{red}{ x }]\times \)[選んだ2人を1列に並べる場合の数]
すなわち:
\(_{3}P_{2}= x \times 2! \)

従って
\( x=\frac{_{3}P_{2}}{2!}\) \(= {}_3 \mathrm{ C }_2=\frac{6}{2}=3\)

上式から「3人から2人を選ぶ組み合わせの数 \( x \) を
  \(x= {}_3 \mathrm{ C }_2 \)  と表します。

一般に\(n \) 人から \(r \) 人を選ぶ組み合わせの数は
\(\underline{ {}_n \mathrm{ C }_r=\frac{_{n}P_{r}}{n!} }\)

[2]組み合わせの性質(1)
組合せの性質より次の式が成り立ちます。
❻: \(\underline{ {}_n \mathrm{ C }_r={}_n \mathrm{ C }_{(n-r)} }\)

\( \underline{=\frac{_{n}P_{r}}{n!} =\frac{_{n}P_{(n-r)}}{(n-r)!} }\)
  (❹より)

これは以下ようにして求められる。
\( {}_n \mathrm{ C }_{n-r} \) \(= \frac{n!}{(r-1)!(n-(n-r))!} \) \( =\frac{n!}{r!\ (n-r)!}\) \(={}_n \mathrm{ C }_r \) 


このことは、 5人から3人選ぶ場合の数を例にすると:
5人から3人選ぶ場合の数と、残る \((5-3)\) 人を選ぶ場合の数は同じであることを意味します。

 \( \overbrace{\fbox{A}\ \fbox{B}\ \fbox{C}}^{選ぶ} \) \( \overbrace{\ \fbox{D}\ \fbox{E} }^{選ばない} \)

別の言い方をすると:
5人から3人選ぶ場合の数と5人から「選ばない2人」を選ぶ場合の数は等しい。

\({}_5 \mathrm{ C }_3={}_5 \mathrm{ C }_{(5-3)}\)
右辺= \(\frac{_{5}P_{2}}{2!}=\frac{5\cdot4}{2}=10\)

この式の効用は次のように計算が簡単になります。
例えば、50人から48人を選ぶ組み合わせの場の数を求める。
\({}_{50} \mathrm{ C }_{48}={}_{50} \mathrm{ C }_{(50-48)}\) \(={}_{50} \mathrm{ C }_{2}\)  

右辺= \(\frac{_{50}P_{2}}{2!}=\frac{50\cdot49}{2}=1225\)
通りです。
時間のある方は、左辺を計算するか、イメージして下さい。 
左辺= \(\frac{_{50}P_{48}}{48!}=\frac{50\cdot49\cdots4\cdot3}{48\cdot47\cdots3\cdot2}\)

[3]組み合わせの性質(2)
組合せの性質より次の式が成り立ちます。
❼: \( \underline{ {}_n \mathrm{ C }_r= {}_{n-1} \mathrm{ C }_{(r-1)} + {}_{n-1} \mathrm{ C }_r } \)

これは以下ようにして求められる。
(ポイントは通分です)
与式
\(= \frac{(n-1)!}{(n-1)!((n-1)-(r-1))!}\) \(+ \frac{(n-1)!}{r!((n-1)-r)!} \)

\(= \frac{(n-1)!}{(n-r)!}\) \(+ \frac{(n-1)!}{r!(n-1-r)!} \)

 (第1項に \( \frac{r}{r} \) 、第2項に \( \frac{(n-r)}{(n-r)} \) を掛けて通分すると:)
\(= \frac{(n-1)!\ r}{r!(n-r)!} \) \(+ \frac{(n-1)!\ (n-r)}{r!(n-r)!} \)

  ( \( n(n-1)!=n!\) )
\( = \frac{n!}{r!(n-r)!}\) \(= {}_n \mathrm{ C }_r \)

この式の意味は次のように考えます。
n 人から r 人を選ぶ組み合わせにおいて、 次の2つのグループに分けて考えよう。
グループ1(G1):n 番目の人が選ばれているグループ。
① すでに n 番目の人を選んでいるので、n 番目人を除いた、(n - 1) 人から( r - 1 ) 人を選ぶ組み合わせ。

グループ2(G2): n 番目の人が選ばれていないグループ。
② n 番目人を除いた (n - 1) 人から r 人を選ぶ組み合わせ。

この結果が以下のようになります。
n 人から r 人を選ぶ組み合わせ=①+② 

これより❼が導き出せる
\( \underline{ {}_n \mathrm{ C }_r= {}_{n-1} \mathrm{ C }_{(r-1)} + {}_{n-1} \mathrm{ C }_r } \)

長々の説明でしたので以下にまとめます。
組合せと順列のまとめ

組合せ(combination)
n 個の中から r 個を選ぶ、選び方の場の数(何通りあるか)
\( {}_n \mathrm{ C }_r\) \(=\frac{{}_{n}P_{r}}{r!}\) \(= \frac{順列}{重複順列} \) \( =\frac{n!}{r! \ (n-r)!}\) \( \cdots ❹ \)

例:7人から2人を選ぶ方法は何通りか
\( {}_7 \mathrm{ C }_2\) \( =\frac{7!}{2! \ (7-2)!}\) \( =\frac{7\cdot6}{2!}\) \( =21 \)

順 列
n 個の中から r 個を選び、さらにそれを並べる場の数(何通りあるか)
ゆえに、組み合わせの数より多くなる。
\(_{n}P_{r} \) \(=\frac{n!}{(n-r)!} \) \( \cdots ❸ \)

例:7人から2人を選んで1列に並べる方法は何通りか
\(_{7}P_{2} \) \(=\frac{7!}{(7-2)!}=7\cdot6=42\)

coffe

  

[コーヒーブレイク/閑話]

【パソコンの活用】

数多くの順列、組み合わせを処理する場合はパソコンの活用が欠かせません。
エクセルによる順列、組み合わせの演算を紹介しましす。
ご存じの方はスルーして下さい!
順列: \({}_{n}P_{r}\)
PERMUT 関数を使います。
\({}_{5}P_{3}\)の場合:エクセルシートのセルに以下を入力する
「=PERMUT(5,3)」
リターンすると答えが表示されます。

組み合わせ: \({}_n \mathrm{ C }_r \)
COMBIN 関数を使います。
\({}_5 \mathrm{ C }_3\) の場合:エクセルシートのセルに以下を入力する
「=COMBIN(5,3)」
リターンすると答えが表示されます。