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

【第01講】順列

【第02講】組合せ

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

【第04講】最短経路

【第05講】重複組合せ

【第01講】順列

【問題】 1から4までの数が書かれた4枚のカードがある。ここから１枚取り出し数字を確認し元に戻して、また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)!}$

【第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, 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}}$

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

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

【問題】男子5人、女子3人を１列に並べる。次の方法は何通りあるか。---
(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$(通り) …（答）

【第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通り …（答）