[婆茶留高校数学科☆HP] SubTopPageに戻る

【第2-2節】 順列・組合せ(書きかけ)

Copyright (C) virtual_high_school, 2021


【第01講】 順列
【第02講】 組合せ
【第03講】 いろいろな順列
【第04講】 最短経路
【第05講】 重複組合せ

【第01講】 順列

【問題】 1から4までの数が書かれた4枚のカードがある。ここから1枚取り出し数字を確認し元に戻して、また1枚取り出し…と繰り返す。取り出しを3回繰り返す場合、カードの出方は何通りあるか。---

【解】 下図のように考えればスロットマシンと同じだ。

積の法則により、$4 \times4 \times4 =4^3=64$(通り) …(答)

厳密に言うとホントのスロットマシンとの違いがある。具体例の1回目の「3」と1回目の「3」は同じカードだが、3のカードは1枚しかないのだ。ここは1~4の4枚セットのコピーを3組取ってスロットマシンの窓に放り込むと考えるとよい。
なお、言い遅れたが上の問題を「4種類から3つ重複を許して選んで1列に並べる重複順列」と言い、$_{4}\Pi_{3}$と書く。

【公式】 $n$種類から$r$個を重複を許して選んで1列に並べる重複順列は

$_{n}\Pi_{r}=\underbrace{n \times n \times \cdots \times n}_{r}=n^r$

【問題】 $n$個の要素からなる集合の部分集合は何個あるか。---

【解】 この集合を

$A=\{ a_{1},a_{2},a_{3},\cdots ,a_{n} \}$

とすれば、それの部分集合$B \subset A$は

$a_{1} \in B$ か $a_{1} \not\in B$ かのどちらかの2通り、
$a_{2} \in B$ か $a_{2} \not\in B$ かのどちらかの2通り、
$a_{3} \in B$ か $a_{3} \not\in B$ かのどちらかの2通り、
$\cdots \cdots \cdots $
$a_{n} \in B$ か $a_{n} \not\in B$ かのどちらかの2通り

で決まるから、

$_{2}\Pi_{n}=2^n$(個)

例えばすべて$\not\in B$なら、その部分集合は空集合$\emptyset$である。
【別解】 部分集合の要素の個数は$0$から$n$までのどれかである。和の法則によりこれらの場合の数を順に足して

$_{n}C_{0}+_{n}C_{1}+_{n}C_{2}+\cdots +_{n}C_{n}=1+n+\frac{n(n-1)}{2} +\cdots+1=2^n$ …(答)

後述する組合せと数学Ⅱで習う二項係数に関する公式を使った。

【問題】 あ~ちゃん、かしゆか、のっちの3人が次のように並ぶ方法は何通りか。(曲により立ち位置が異なるのです。)---
   
(1) 壁を背にステージ上に1列に並ぶ。
(2) 円形ステージ上に1列に並ぶ。
(3) 円形ステージ上に円形に並ぶ。

【解】 (1) スロットマシンのイメージで考える。
   
前問と異なるのは例えば「左」に「あ、か、の」の3通りあるうちの「の」を入れたら、2つ目の「中」には残りの「あ、か」の2通りの選び方になる。最後の「右」には1通りの入れ方しか残らない。よって

$3 \times 2 \times 1 =3!=6$(通り) …(答)

このように$n!=n \times (n-1) \times \cdots 3 \times 2 \times 1$($n$の階乗と言う)という記号を使って表すことができる。(注意:$1!=1$は1を1個掛けるのだからよいとして、$0!$は0を0個掛けるのだから不定になりそうだが、$0!=1$と決めておく。理由は後述。)

(2) 「あ-か-の」の並び方も、反対側にいるオーディンスからは「の-か-あ」の並び方に見えるから、この2つの並び方は同じと解釈しなければならない。
   
さっきは全部で6通りあったのだが、2通りずつが同一視されるから、実際に存在する順列は$6 \div 2=3$通りとなる。言い換えれば、6個の要素からなる集合を定義域とする関数があって、2つずつの要素が同じ要素に対応するのなら、$2:1$の対応だから値域は3個の要素からなる集合である。

【公式】 類別定理(仮称) $N$個のものを$m$個ずつ同一視したら

$N \div m$個

のものがあると解釈される。あるいは、$m$個ずつを束ねて1つの類(class)とすれば、

$N \div m$個

の類に分けられる。---

そこで結局こうなる。 3人のうち立ち位置が中の者だけに注目すればよく、3人のうちの誰にするかで、3通り …(答)

(3) 「あ」の立ち位置を初めに決める。この人を固定して、残り2人を並べる。2人を1列に並べるのと同じだから、$2!=2 \times 1=2$通り …(答)

この事実を

$n$人を円形に並べる円順列は$(n-1)!$通り

のように表現する。

【問題】 7人の班員から班長、美化係、保健係各1名を選ぶ。ただし兼任は認めない。決め方は名通りあるか。---

【解】 班長の選び方は7通り。兼任を認めないから、美化係は残る6人の6通りの選び方がある。保健係も同様に考える。積の法則により

$7 \times 6 \times 5=210$通り …(答)

【別解】 選任すべき役職を「班長、美化係、保健係、補欠1、補欠2、補欠3、補欠4」の各1名(兼任なし)とすると、その選び方は$7!$通りである。ところが補欠は何番であっても同一視できるから、$7!$通りのうち$4!$通りずつ同じものと解釈できるから、実質的な選び方は

$\frac{7!}{(7-3)!}=\frac{7!}{4!}=7 \times 6 \times 5=210$(通り) …(答)

上に出てきた場合の数を「$7$個から$3$個を選んで並べる順列」と言い、$_{7}P_{3}$ と書く。

【公式】 $n$個から$r$個を選んで並べる順列

$_{n}P_{r}=n \times (n-1) \times \cdots \times (n-r+1)=\frac{n!}{(n-r)!}$
 PageTopへ

【第02講】 組合せ

【問題】 7人の班員から清掃係3名を選ぶ。選び方は名通りあるか。---

【解】 7人から係1、係2、係3を決める方法は、積の法則または順列を使って

$_{7}P_{3}=\frac{7!}{(7-3)!}=7 \times 6 \times 5$(通り)

だが、実際には係1、係2、係3は区別されない(同一視される)。係1、係2、係3の並べ方が$3!$通りあるから、類別定理により

$_{7}C_{3}=\frac{_{7}P_{3}}{3!}=\frac{7!}{3!(7-3)!}=35$(通り) …(答)


いまフライングして記号を使ってしまったが、上の答のように選ぶ順序を問わないとき、「$7$人から$3$人を選ぶ組合せ」と呼び、$_{7}C_{3}$と書く。

【公式】 $n$個から$r$個を選んぶ組合せ

$_{n}C_{r}=\frac{n!}{r! (n-r)!}$

【問題】 4人のメンバーの頭文字 A, A, B, B を並べ替えてグループ名にしたいと考えている。
   
4文字を1列に並べる方法は何通りか。---

【解】 1, 2, 3, 4 と番号をついたスロットに A, A, B, B の文字を入れる訳だが、そこで逆転の発想! 仮に「番号取りの考え方」と呼んでおくが、スロットが主人公ではなく文字の方を主人公と考えて、文字 A が1~4の番号の中から2つ番号を取るのだ。だから

$_{4}C_{2}=\frac{4!}{2! 2!}=\frac{4 \times 3}{2 \times 1}=6$(通り) …(答)

【別解】 A1, A2, B1, B2 を1列に並べると考えると$4!$通り。だが実際にはA1, A2 は同一視されるから$2!$で割り、B1, B2 も同一視されるからだらに$2!$で割る。だから

$\frac{4!}{2! 2!}=6$(通り) …(答)

これを同じものを含む順列と言う。

【公式】 Aが$i$個、Bが$j$個、$\cdots$、Cが$k$個あって、全部合わせると$n=i+j+\cdots +k$個であるとする。これらを1列に並べる同じものを含む順列

$\frac{n!}{i! j! \cdots k!}$通り

これって、数学Ⅱで習う多項係数と同じだ。当然A, B の2種類しかなければ二項係数(=組合せ)と同じになる。

【問題】 下図の中に長方形は何個あるか。---
   

【解】 12個ではない。縦線(赤数字の1~5)を2つと、横線(青数字の1~4)を2つを選べば長方形が決定される。したがって積の法則により

$_{5}C_{2} \times _{4}C_{2}=\frac{5 \times 4}{2 \times 1} \times \frac{4 \times 3}{2 \times 1}=10 \times 6=60$(個) …(答)

【別解】和の法則を使う。下図のように、小さい長方形(ア型)が12個、横に2個連結した長方形(イ型)が9個、$2 \times 2$のウ型が6個、$\cdots$ ある。
   
なぜ個数がすぐ分かるかと言うと、例えばウ型の場合、赤丸の個数を数えて6個とすればよい。数えた結果を与えられた与えられた図の中に書き込んで、それらを足せばよい。

$(12+9+6+3)+(8+6+4+2)+(4+3+2+1)=60$
(個) …(答)

せっかくだから、もう少し分析すると

$(4 \times 3+3 \times 3+ 2 \times 3+ 1 \times 3)+ (4 \times 2+3 \times 2+ 2 \times 2+ 1 \times 2)+ (4 \times 1+3 \times 1+ 2 \times 1+ 1 \times 1)$
$=(4+3+2+1)(3+2+1)$
$=\frac{4 \times 5}{2} \times \frac{3 \times 4}{2}$
$={_{5}C_{2}} \times {_{4}C_{2}}$

だから、最初の解と一致する。
 PageTopへ


【第03講】 いろいろな順列

【問題】 男子5人、女子3人を1列に並べる。次の方法は何通りあるか。---
(1) 女子3人が隣り合う。
(2) 女子3人はどの2人も隣り合わない。

【解】(1) 女子3人をひもで縛る。(2人3脚のように。)これの並び方が$3!$通りある。

ひもで縛れば1人と見なせるから、あとは見掛け6人の並べ方になる。女子3人を並べて、6人を並べるから積の法則になり

$3! \times 6!=6 \times 720=4320$(通り) …(答)

(2) 男子を先に並べておいて、間に女子を挿入すると考える。隙間は6か所あるから


$5! \times _{6}P_{3}= 120 \times (6 \cdot 5 \cdot 4)=14400$(通り) …(答)

 PageTopへ


【第04講】 最短経路

【問題】 下図のような街路がある。A地点からB地点までの最短経路は何本あるか。---

【解】 最短は1つではない。同じ道のりの経路が複数ある。その個数を求めるのである。(だから最短とは遠回りしいないということである。)
1つの経路を分析すると、例えば

→↓→↓↓→→→

のように分解できる。つまり、→を5個、↓を3個一列に並べる順列の個数を求めればよい。同じものを含む順列と考えれば

$\frac{(5+3)!}{5! 3!}=\frac{8 \times 7 \times 6}{3 \times 2 \times 1}=56$(通り) …(答)

だし、8か所のあるスロットから5か所選んで「→」を入れればよいから、組合せで

$_{8}C_{5}=\frac{8!}{5! 3!}=56$(通り)

【別解】 56人のランナーをA地点からB地点に向けて競走すると考える。ただしどのランナーも他者と同じ経路は走らない。ランナーたちの走りをある交差点に立って眺めてみると、北から何人、西から何人か来る。その人数を合計すれば、それがA地点からその交差点までの最短経路の個数になる。そこで、各交差点に最短経路の個数を記入すれば下図のようになる。

この図を$-45^{\circ}$回転してみると、なんだパスカルの三角形だ。この図から求めるべき答は56通りと分かる。

別解のように和の法則で計算すると面倒だと思った諸君! 次の問題では和の法則を使わざるを得ない。


【問題】 下図のような街路がある。A地点からB地点までの経路は何本あるか。ただし東と南の方向にしか動けない。2か所の×は通行止めで立体交差が1か所ある。---

【解】
   (マウスをかぶせると途中計算が出ます。)
   29通り …(答)
 PageTopへ


【第05講】 重複組合せ

【問題】 1円玉、10円玉、100円玉を合わせて5枚使って支払いをする。合計金額はいろいろになるが、全部で何通りか。---

【解】 それぞれの枚数を $x, y,z$(枚)とすると合計金額は

$x+10y+100z$(円)

で、制約条件は

$x ,y, z \geq 0; x+y+z=5$

である。これは$X,Y,Z$の文字が書かれた玉を(どの種類の玉も十分たくさん) 袋に入れて、そこから計5個取り出す方法の数と同じである。これを$3$種類から$5$個を取る重複組合せと言う。
例えば

という重複組合せは

の表現することもできる。これは5個のまんじゅうと$3-1=2$個の仕切板を1列に並べる(=同じものを含む順列)方法の数だから

$\frac{(5+3-1)!}{5! (3-1)!}=_{5+3-1}C_{5}=21$(通り) …(答)


【公式】 $n$種類から$r$個を取る重複組合せ$_{n}H_{r}$は、まんじゅう$n$個、仕切板$r-1$個、合計$n+r-1$個と考えて

$_{n}H_{r}=_{n+r-1}C_{n}$

いま、まんじゅうと仕切板で考えたが、下図のように街路図で考えることもできる。

赤い矢印がまんじゅうで、青い矢印が仕切板に相当する。
 PageTopへ


★「婆茶留高校」は架空の存在であり、実在の人物、団体とは関係ありません。
<-- クリックして婆茶留高校へメール送信 mailto: virtual_h_s@yahoo.co.jp 
婆茶留高校数学科HP http://www.virtual-hs.com/ Powered by   Copyright(c) virtual_high_school, 2001-2021