目次 ／ 場合の数と確率 ／ 数学A

第3章　順列

—— 「並べる」ときは、席を1つずつ埋めていく ——

第2章では、和の法則と積の法則で起こり方を数えました。この章では、その積の法則を「異なるものを並べる」場面に絞り、順列の記号 ${}_n\mathrm{P}_r$ と階乗 $n!$ を導入します。条件のついた並べ方（隣り合う・隣り合わない・0 を含む整数）、円形に並べる円順列、裏返せるじゅず順列、同じものをくり返し使ってよい重複順列まで、並べ方の数え方をひととおり身につけます。次の第4章では「選ぶ」組合せを学び、「並べる」と「選ぶ」の違いをはっきりさせます。

問題マップ記録を読み込み中…
基1基2基3基4基51234567891011121314151617181920
未回答 25× 0○ 01か月定着 0

順列と階乗

第2章の例題3(3)では、55 人から委員長と副委員長を1人ずつ選ぶ方法を 5×45 \times 4=20{}= 20 通りと数えました。「委員長」「副委員長」という2つの席に、異なる人を1人ずつ座らせる数え方です。55 人全員を1列に並べるなら、1番目の席は 55 通り、2番目は残りの 44 通り、…と進んで 5×4×3×2×15 \times 4 \times 3 \times 2 \times 1=120{}= 120 通りになります。こうした「異なるものを並べる」数え方には、専用の記号があります。

公式1：順列と階乗

異なる nn 個のものから異なる rr 個を取り出して1列に並べたものを、nn 個から rr 個取る順列といい、その総数を nPr{}_n\mathrm{P}_r で表す。

nPr\displaystyle {}_n\mathrm{P}_r=n(n−1)(n−2)⋯(n−r+1)⏟r 個の積\displaystyle {}= \underbrace{n(n - 1)(n - 2) \cdots (n - r + 1)}_{r \text{ 個の積}}

11 から nn までの自然数の積を nn の階乗といい、n!n! で表す。

n!\displaystyle n!=n(n−1)(n−2)⋯3⋅2⋅1,\displaystyle {}= n(n - 1)(n - 2) \cdots 3 \cdot 2 \cdot 1,nPn\displaystyle {}_n\mathrm{P}_n=n!\displaystyle {}= n!

0!0!=1{}= 1 と定めると、00≦r{}\leqq r≦n{}\leqq n のとき nPr{}_n\mathrm{P}_r=n!(n−r)!{}= \dfrac{n!}{(n - r)!} と書ける（nP0{}_n\mathrm{P}_0=1{}= 1）。

P は順列を表す英語 permutation の頭文字です。nPr{}_n\mathrm{P}_r は「nn から始めて 11 ずつ小さくしながら rr 個かける」と覚えます。たとえば 7P3{}_7\mathrm{P}_3=7×6×5{}= 7 \times 6 \times 5=210{}= 210 です。最後の数 nn−r{}- r+1{}+ 1 を求めなくても、「かける個数が rr 個」と数えれば間違えません。

n!n! は nn が大きくなるとあっという間に大きくなります。5!5!=120{}= 120、8!8!=40320{}= 40320、10!10!=3628800{}= 3628800 です。第2章の小話で、ルービックキューブの角の部品の置き方を 8×7×⋯×18 \times 7 \times \cdots \times 1=40320{}= 40320 通りと数えましたが、これは 8!8! のことでした。

0!0!=1{}= 1 は奇妙に見えますが、「00 個のものを並べる方法は、何も並べないという 11 通り」と考えると自然です。こう決めておくと、nPr{}_n\mathrm{P}_r=n!(n−r)!{}= \dfrac{n!}{(n - r)!} が rr=n{}= n のときにも成り立ちます。この形は、nPr{}_n\mathrm{P}_r が「n!n! の途中でかけ算を打ち切ったもの」であることを表しています。

陸上 100 m の決勝を思い浮かべてください。88 人が走り、金・銀・銅のメダルを渡します。金メダルは 88 人の誰かなので 88 通り、銀メダルは金メダルの人を除いた 77 通り、銅メダルはさらに除いた 66 通りです。表彰台の並び方は 8P3{}_8\mathrm{P}_3=8×7×6{}= 8 \times 7 \times 6=336{}= 336 通りです。同じ人が金と銀を同時にとることはないので、席が1つ埋まるごとに候補が1人ずつ減っていきます。

異なるものを並べる数は、席を1つずつ埋めながら候補が1つずつ減るかけ算で、nPr{}_n\mathrm{P}_r や n!n! で表せるということです。

例題1：順列の数

(1) 6P4{}_6\mathrm{P}_4，4!4!，7!5!\dfrac{7!}{5!} の値を求めなさい。

(2) 1010 チームが出場する大会で、優勝・準優勝・3位の決まり方は何通りあるか求めなさい。ただし、同順位はないものとする。

【解答】

(1) 6P4{}_6\mathrm{P}_4=6×5×4×3{}= 6 \times 5 \times 4 \times 3=360‾{}= \underline{360}、4!4!=4×3×2×1{}= 4 \times 3 \times 2 \times 1=24‾{}= \underline{24} です。

7!5!\dfrac{7!}{5!} は、分子と分母に共通な 5×4×3×2×15 \times 4 \times 3 \times 2 \times 1 を約分して 7×67 \times 6=42‾{}= \underline{42} です。これは 7P2{}_7\mathrm{P}_2 と同じ値です。

(2) 1010 チームから 33 チームを選び、「優勝」「準優勝」「3位」の順に並べる順列なので

10P3\displaystyle {}_{10}\mathrm{P}_3=10×9×8\displaystyle {}= 10 \times 9 \times 8=720 通り‾\displaystyle {}= \underline{720 \text{ 通り}}

です。

条件のついた順列

「この人は端に」「この2人はとなりに」のような条件がつくと、そのまま nPr{}_n\mathrm{P}_r を使うことはできません。条件の種類ごとに、決まった処理のしかたがあります。

公式2：条件のついた順列の数え方
  1. 条件のついた場所・ものから先に決め、残りを順列で並べて、積の法則でかける。
  2. 隣り合うものは、ひとまとめにして1つとみなして並べ、まとめた中の並べ方をかける。
  3. 隣り合わないものは、ほかのものを先に並べ、その間と両端のすき間に1つずつ入れる。

2と3の考え方を、男子 44 人と女子 33 人の 77 人を1列に並べる場面で見てみます。女子 33 人が隣り合うなら、女子 33 人を大きな1人とみなし、男子 44 人と合わせて 55 つのものを並べます。そのあと、まとまりの中で女子 33 人の並び方を決めます。

女子どうしが隣り合わないようにするには、先に男子 44 人を並べます。

□ 男 □ 男 □ 男 □ 男 □\square \ \text{男} \ \square \ \text{男} \ \square \ \text{男} \ \square \ \text{男} \ \square

男子の間と両端に 55 つのすき間ができます。異なるすき間に女子を1人ずつ入れれば、女子どうしが隣り合うことはありません。女子 33 人を 55 つのすき間に並べる方法は 5P3{}_5\mathrm{P}_3 通りです。両端のすき間を忘れやすいので注意しましょう。

集合写真を撮る場面にたとえられます。仲良しの2人が「絶対にとなりがいい」と言ったら、カメラマンは2人を「2人で1人分」として並べ、最後に2人のどちらが左かを決めます。反対に、背の高い人どうしを隣に並べたくなければ、先にほかの人を並べておき、その間に1人ずつ入ってもらいます。

条件のついた順列は、条件のあるものから決める、隣り合うものはまとめる、隣り合わないものはすき間に入れる、の3つで処理できるということです。

例題2：隣り合う・隣り合わない

男子 44 人と女子 33 人の合計 77 人が1列に並ぶとき、次の並び方は何通りあるか求めなさい。

(1) 女子 33 人が続いて並ぶ

(2) 女子どうしが隣り合わない

(3) 両端が男子である

【解答】

(1) 女子 33 人をひとまとめにすると、男子 44 人とまとまり1つの 55 つを並べるので 5!5!=120{}= 120 通りです。そのそれぞれに対して、まとまりの中の女子の並び方が 3!3!=6{}= 6 通りずつあります。

5!×3!\displaystyle 5! \times 3!=120×6\displaystyle {}= 120 \times 6=720 通り‾\displaystyle {}= \underline{720 \text{ 通り}}

(2) 先に男子 44 人を並べる方法は 4!4!=24{}= 24 通りです。男子の間と両端の 55 つのすき間から 33 つを選んで女子を1人ずつ入れる方法は 5P3{}_5\mathrm{P}_3=60{}= 60 通りです。

4!×5P3\displaystyle 4! \times {}_5\mathrm{P}_3=24×60\displaystyle {}= 24 \times 60=1440 通り‾\displaystyle {}= \underline{1440 \text{ 通り}}

(3) 条件のある両端から決めます。左端と右端に男子 44 人から 22 人を並べる方法は 4P2{}_4\mathrm{P}_2=12{}= 12 通りです。残りの 55 人を間の 55 か所に並べる方法は 5!5!=120{}= 120 通りです。

4P2×5!\displaystyle {}_4\mathrm{P}_2 \times 5!=12×120\displaystyle {}= 12 \times 120=1440 通り‾\displaystyle {}= \underline{1440 \text{ 通り}}

数字を並べて整数を作るときは、「最高位に 00 は置けない」という条件が隠れています。これも条件のある位から先に決めます。

例題3：0 を含む数字で整数を作る

00，11，22，33，44，55 の 66 個の数字から異なる 33 個を使って 33 桁の整数を作ります。

(1) 33 桁の整数は全部で何個できるか求めなさい。

(2) そのうち偶数は何個あるか求めなさい。

【解答】

(1) 百の位は 00 以外の 55 通りです。十の位は百の位で使った数字以外の 55 通り（00 も使える）、一の位は残りの 44 通りです。

5×5×4\displaystyle 5 \times 5 \times 4=100 個‾\displaystyle {}= \underline{100 \text{ 個}}

(2) 偶数になるのは一の位が 00，22，44 のときです。一の位が 00 かどうかで、百の位の候補の数が変わるので場合分けします。

  • 一の位が 00：百の位と十の位に残り 55 個の数字を並べるので 5P2{}_5\mathrm{P}_2=20{}= 20 個
  • 一の位が 22 か 44（22 通り）：百の位は 00 と一の位の数字以外の 44 通り、十の位は残りの 44 通りなので 2×4×42 \times 4 \times 4=32{}= 32 個

和の法則より 2020+32{}+ 32=52 個‾{}= \underline{52 \text{ 個}} です。

00 が「一の位にいるか」で百の位の候補が変わるので、1回のかけ算にはまとめられません。第2章の j17 と同じく、数が変わるところで場合分けします。

円順列

人がテーブルを囲むように、ものを円形に並べる場合を考えます。AA，BB，CC，DD の 44 人が円形のテーブルに座るとき、全員が1つずつ右の席へずれても、「誰の右隣が誰か」という関係は変わりません。円形の並びでは、回転して重なるものを同じ並び方とみなします。

公式3：円順列

異なる nn 個のものを円形に並べたものを円順列という。回転して一致する並び方を同じものとみなすと、その総数は

n!n\displaystyle \frac{n!}{n}=(n−1)!\displaystyle {}= (n - 1)!

である。

ABCD DABC CDAB BCDA 上から時計回り ABCD DABC CDAB BCDA どれも A → B → C → D（時計回り）で、回すと重なる 4 通りの並びで 1 つの円順列 → 4! ÷ 4 = 3! = 6 通り

44 人を1列に並べる 4!4!=24{}= 24 通りの並びを、「上の席から時計回りに座らせる」ことで円形の並びにします。図のように、ABCD\mathrm{ABCD}，DABC\mathrm{DABC}，CDAB\mathrm{CDAB}，BCDA\mathrm{BCDA} の 44 つの並びは、回すと重なる同じ円順列になります。どの円順列にも、こうした列の並びがちょうど 44 つずつ対応するので、円順列は 24÷424 \div 4=6{}= 6 通りです。

もう1つの考え方は、1人の席を固定する方法です。AA の席を決めてしまえば回転の自由がなくなり、残りの 33 人を AA から時計回りに並べる 3!3!=6{}= 6 通りがそのまま答えになります。一般に、1つを固定して残りの nn−1{}- 1 個を並べるので (n−1)!(n - 1)! 通りです。

中華料理店の回転テーブルを思い浮かべてください。料理ののったターンテーブルをいくら回しても、エビチリの右隣が麻婆豆腐であることは変わりません。変わるのは「どの料理が自分の前に来るか」だけで、並びそのものは同じです。円順列が数えているのは、この「となり合う関係」の違いです。

円順列は回転して重なる並びを同じとみなすので、1つを固定して残りを並べ、(n−1)!(n - 1)! 通りになるということです。

例題4：円順列

AA，BB を含む 66 人が円形のテーブルに座ります。

(1) 座り方は全部で何通りあるか求めなさい。

(2) AA と BB が向かい合って座る方法は何通りあるか求めなさい。ただし、テーブルの席は等間隔に 66 つあるものとする。

【解答】

(1) 異なる 66 個の円順列なので (6−1)!(6 - 1)!=5!{}= 5!=120 通り‾{}= \underline{120 \text{ 通り}} です。

(2) AA の席を固定します。BB は AA の向かいの席に決まるので 11 通りです。残りの 44 人を空いている 44 席に並べる方法は 4!4!=24{}= 24 通りなので、24 通り‾\underline{24 \text{ 通り}} です。

AA を固定したあとの席は、AA から見て「右隣」「向かい」などと区別できるので、もう回転を気にする必要はありません。

じゅず順列

ビーズを円形につないで作る首飾りや腕輪は、回すだけでなく、裏返すこともできます。裏返すと、時計回りの並びが反時計回りの並びに変わります。

公式4：じゅず順列

異なる nn 個（nn≧3{}\geqq 3）のものを円形に並べ、回転しても裏返しても一致するものを同じとみなすとき、その総数は

(n−1)!2\frac{(n - 1)!}{2}

である。これをじゅず順列という。

円順列 (n−1)!(n - 1)! 通りの中には、A\mathrm{A}→B{}\to \mathrm{B}→C{}\to \mathrm{C}→D{}\to \mathrm{D}（時計回り）と A\mathrm{A}→D{}\to \mathrm{D}→C{}\to \mathrm{C}→B{}\to \mathrm{B}（時計回り）のように、裏返すと重なるものが2つずつ組になって入っています。nn≧3{}\geqq 3 なら、ある円順列を裏返したものは必ず別の円順列になる（A\mathrm{A} の時計回りの隣が B\mathrm{B} から D\mathrm{D} に変わる）ので、ちょうど半分にすればよいのです。

nn=3{}= 3 のときは 2!2\dfrac{2!}{2}=1{}= 1 通りです。33 個の玉を輪にすると、どの2つも隣り合うので、並べ方は1通りしかありません。

ビーズのブレスレットで考えます。赤・青・黄・白・黒の 55 個のビーズを輪にしたブレスレットは、手首に着けるときに表裏どちらを外側にしてもかまいません。机の上で「赤 → 青 → 黄 → 白 → 黒」と時計回りに見えるブレスレットを裏返すと、「赤 → 黒 → 白 → 黄 → 青」と見えます。円形のテーブルなら別の座り方ですが、ブレスレットとしては同じ1本です。

裏返せる円形の並びは、円順列を裏返しで重なる2つずつの組にまとめて、(n−1)!÷2(n - 1)! \div 2 通りになるということです。

例題5：じゅず順列

(1) 色の異なる 66 個の玉をつないで首飾りを作る方法は何通りあるか求めなさい。

(2) 色の異なる 55 個の玉をつないで腕輪を作る方法は何通りあるか求めなさい。

【解答】

(1) 円順列は (6−1)!(6 - 1)!=120{}= 120 通りで、首飾りは裏返せるので

5!2\displaystyle \frac{5!}{2}=1202\displaystyle {}= \frac{120}{2}=60 通り‾\displaystyle {}= \underline{60 \text{ 通り}}

(2) 同じように

4!2\displaystyle \frac{4!}{2}=242\displaystyle {}= \frac{24}{2}=12 通り‾\displaystyle {}= \underline{12 \text{ 通り}}

です。

円形のテーブルは裏返せないので円順列、首飾りや腕輪は裏返せるのでじゅず順列、と使い分けます。

重複順列

ここまでは「異なるもの」を1回ずつ並べてきました。同じものを何回使ってもよいときは、席が埋まっても候補が減りません。

公式5：重複順列

異なる nn 種類のものから、同じものをくり返し取ってよいとして rr 個を1列に並べたものを、nn 個から rr 個取る重複順列という。その総数は

nrn^r

である。

どの席にも nn 種類すべてが使えるので、積の法則で n×n×⋯×nn \times n \times \cdots \times n（rr 個）=nr= n^r です。第2章でパスワードの数を 5×5×55 \times 5 \times 5=53{}= 5^3 と数えたのは、55 種類の文字から 33 個取る重複順列でした。第2章の j11 の「00〜44 で作る 33 桁の整数（くり返し可）」も、百の位の条件を除けば同じ形です。

重複順列は、「人が部屋を選ぶ」ような場面にもよく出てきます。44 人を AA，BB，CC の 33 部屋に入れる（空き部屋があってもよい）とき、1人ずつ「どの部屋に入るか」を 33 通りから選ぶので 343^4=81{}= 81 通りです。434^3 ではありません。何が何を選ぶのか（人が部屋を選ぶ）を確かめ、「選ぶ側の数」を指数にします。

トランプを引く場面で、順列と重複順列の違いを確かめましょう。11 から 55 までのカードを1枚引いて数字を記録する、を 33 回くり返します。引いたカードを戻さないなら、2回目の候補は 44 枚、3回目は 33 枚に減って 5P3{}_5\mathrm{P}_3=60{}= 60 通りです。毎回カードを戻してよく混ぜるなら、毎回 55 枚から引けるので 535^3=125{}= 125 通りです。

同じものをくり返し使えるときは候補が減らないので、nn 種類から rr 個並べる数は nrn^r になるということです。

例題6：重複順列

(1) 3つの選択肢から1つを選んで答える問題が 55 問あります。答え方は何通りあるか求めなさい。

(2) 44 人を AA，BB，CC の 33 つの部屋に入れる方法は何通りあるか求めなさい。ただし、空き部屋があってもよいものとする。

【解答】

(1) どの問題も 33 通りずつ答えられるので、33 種類から 55 個取る重複順列です。

35\displaystyle 3^5=243 通り‾\displaystyle {}= \underline{243 \text{ 通り}}

(2) 44 人のそれぞれが 33 部屋から1つを選ぶので

34\displaystyle 3^4=81 通り‾\displaystyle {}= \underline{81 \text{ 通り}}

です。部屋が人を選ぶのではないので、434^3 にはなりません。

基礎確認問題（全5問）

まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。

問1

7P3{}_7\mathrm{P}_3 の値を求めなさい。

つまずいたときは：
答えを見る
答え

210‾\underline{210}（7×6×57 \times 6 \times 5）

自己採点：
記録を読み込み中…

問2

5!5! と 5P2{}_5\mathrm{P}_2 の値を求めなさい。

つまずいたときは：
答えを見る
答え

5!5!=120‾{}= \underline{120}，5P2{}_5\mathrm{P}_2=20‾{}= \underline{20}（5×45 \times 4）

自己採点：
記録を読み込み中…

問3

66 人が円形のテーブルに座る方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

120 通り‾\underline{120 \text{ 通り}}（円順列 (6−1)!(6 - 1)!=5!{}= 5!）

自己採点：
記録を読み込み中…

問4

空の箱があってもよいものとして、異なる 55 個の玉を AA，BB の 22 つの箱に入れる方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

32 通り‾\underline{32 \text{ 通り}}（どの玉も 22 通りの重複順列 252^5）

自己採点：
記録を読み込み中…

問5

11，22，33，44，55 の 55 個の数字から異なる 33 個を使ってできる 33 桁の整数の個数を求めなさい。

つまずいたときは：
答えを見る
答え

60 個‾\underline{60 \text{ 個}}（5P3{}_5\mathrm{P}_3=5×4×3{}= 5 \times 4 \times 3）

自己採点：
記録を読み込み中…

実践問題（全20問）

難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。

問1　★

99 人の中から、議長・副議長・書記を1人ずつ選ぶ方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

504504 通り

解説

99 人から 33 人を選び、「議長」「副議長」「書記」の順に並べる順列です。同じ人が2つの役を兼ねることはないので、候補が1人ずつ減ります。

9P3\displaystyle {}_9\mathrm{P}_3=9×8×7\displaystyle {}= 9 \times 8 \times 7=504 通り‾\displaystyle {}= \underline{504 \text{ 通り}}
自己採点：
記録を読み込み中…

問2　★

(1) nP2{}_n\mathrm{P}_2=56{}= 56 を満たす自然数 nn を求めなさい。

(2) nP3{}_n\mathrm{P}_3=3⋅nP2{}= 3 \cdot {}_n\mathrm{P}_2 を満たす自然数 nn を求めなさい。

つまずいたときは：
答えを見る
答え

(1) nn=8{}= 8　(2) nn=5{}= 5

解説

(1) nP2{}_n\mathrm{P}_2=n(n−1){}= n(n - 1) なので n(n−1)n(n - 1)=56{}= 56 です（nn≧2{}\geqq 2）。

n2\displaystyle n^2−n\displaystyle {}- n−56\displaystyle {}- 56=0\displaystyle {}= 0⟹(n−8)(n+7)\displaystyle {}\Longrightarrow \quad (n - 8)(n + 7)=0\displaystyle {}= 0

nn≧2{}\geqq 2 より n=8‾\underline{n = 8} です。確かめると 8×78 \times 7=56{}= 56 です。

(2) nP3{}_n\mathrm{P}_3 が意味をもつので nn≧3{}\geqq 3 です。

n(n−1)(n−2)\displaystyle n(n - 1)(n - 2)=3n(n−1)\displaystyle {}= 3n(n - 1)

nn≧3{}\geqq 3 より n(n−1)n(n - 1)≠0{}\neq 0 なので、両辺を n(n−1)n(n - 1) で割って nn−2{}- 2=3{}= 3、よって n=5‾\underline{n = 5} です。確かめると 5P3{}_5\mathrm{P}_3=60{}= 60，3⋅5P23 \cdot {}_5\mathrm{P}_2=3×20{}= 3 \times 20=60{}= 60 です。

自己採点：
記録を読み込み中…

問3　★

a\mathrm{a}，b\mathrm{b}，c\mathrm{c}，d\mathrm{d}，e\mathrm{e} の 55 文字を1列に並べます。

(1) a\mathrm{a} が先頭にくる並べ方は何通りあるか求めなさい。

(2) a\mathrm{a} と b\mathrm{b} が両端にくる並べ方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 2424 通り　(2) 1212 通り

解説

(1) 先頭は a\mathrm{a} の 11 通りに決まり、残りの 44 文字を2番目〜5番目に並べるので 4!4!=24 通り‾{}= \underline{24 \text{ 通り}} です。

(2) 両端に a\mathrm{a}，b\mathrm{b} を置く方法は「左端 a\mathrm{a}・右端 b\mathrm{b}」と「左端 b\mathrm{b}・右端 a\mathrm{a}」の 2!2!=2{}= 2 通りです。間の 33 か所に残りの 33 文字を並べる方法は 3!3!=6{}= 6 通りです。

2×6\displaystyle 2 \times 6=12 通り‾\displaystyle {}= \underline{12 \text{ 通り}}
自己採点：
記録を読み込み中…

問4　★

00，11，22，33，44 の 55 個の数字から異なる 33 個を使って 33 桁の整数を作ります。

(1) 33 桁の整数は全部で何個できるか求めなさい。

(2) そのうち奇数は何個あるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 4848 個　(2) 1818 個

解説

(1) 百の位は 00 以外の 44 通り、十の位は百の位で使った数字以外の 44 通り（00 も使える）、一の位は残りの 33 通りです。

4×4×3\displaystyle 4 \times 4 \times 3=48 個‾\displaystyle {}= \underline{48 \text{ 個}}

(2) 奇数になるのは一の位が 11 か 33 のときで、22 通りです。条件のある位から決めます。

  • 一の位：11 か 33 の 22 通り
  • 百の位：00 と一の位の数字を除いた 33 通り
  • 十の位：残りの 33 通り（00 も使える）
2×3×3\displaystyle 2 \times 3 \times 3=18 個‾\displaystyle {}= \underline{18 \text{ 個}}

一の位に 00 が来ることはないので、例題3(2)のような場合分けは要りません。

自己採点：
記録を読み込み中…

問5　★

AA，BB を含む 77 人が円形に並びます。

(1) 並び方は全部で何通りあるか求めなさい。

(2) AA と BB が隣り合う並び方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 720720 通り　(2) 240240 通り

解説

(1) 異なる 77 個の円順列なので (7−1)!(7 - 1)!=6!{}= 6!=720 通り‾{}= \underline{720 \text{ 通り}} です。

(2) AA と BB をひとまとめにすると、まとまり1つと残り 55 人の合計 66 つの円順列になり、(6−1)!(6 - 1)!=5!{}= 5!=120{}= 120 通りです。まとまりの中で AA，BB の並び方が 22 通りあるので

5!×2\displaystyle 5! \times 2=120×2\displaystyle {}= 120 \times 2=240 通り‾\displaystyle {}= \underline{240 \text{ 通り}}
自己採点：
記録を読み込み中…

問6　★

色の異なる 77 個の玉をつないで首飾りを作る方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

360360 通り

解説

円順列は (7−1)!(7 - 1)!=720{}= 720 通りです。首飾りは裏返すことができ、裏返すと重なる円順列が2つずつ組になっているので

6!2\displaystyle \frac{6!}{2}=7202\displaystyle {}= \frac{720}{2}=360 通り‾\displaystyle {}= \underline{360 \text{ 通り}}
自己採点：
記録を読み込み中…

問7　★

11，22，33 の 33 個の数字を使って 44 桁の整数を作ります。同じ数字をくり返し使ってよいとき、44 桁の整数は何個できるか求めなさい。

つまずいたときは：
答えを見る
答え

8181 個

解説

00 が含まれていないので、どの位も 11，22，33 の 33 通りです。33 種類から 44 個取る重複順列で

34\displaystyle 3^4=81 個‾\displaystyle {}= \underline{81 \text{ 個}}
自己採点：
記録を読み込み中…

問8　★

66 人が1回じゃんけんをするとき、66 人の手の出し方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

729729 通り

解説

66 人のそれぞれが、グー・チョキ・パーの 33 通りから1つを選びます。人を区別して数えると、33 種類から 66 個取る重複順列なので

36\displaystyle 3^6=729 通り‾\displaystyle {}= \underline{729 \text{ 通り}}

「人が手を選ぶ」ので、指数は人数の 66 です。

自己採点：
記録を読み込み中…

問9　★★

男子 33 人と女子 44 人の合計 77 人が1列に並びます。男女が交互に並ぶ並び方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

144144 通り

解説

77 か所に男女が交互に並ぶには、人数の多い女子が両端に来て

女 男 女 男 女 男 女\text{女} \ \text{男} \ \text{女} \ \text{男} \ \text{女} \ \text{男} \ \text{女}

の形になるしかありません（男子から始めると男子が 44 人必要になります）。女子 44 人を女子の 44 か所に並べる方法が 4!4!=24{}= 24 通り、男子 33 人を男子の 33 か所に並べる方法が 3!3!=6{}= 6 通りです。

4!×3!\displaystyle 4! \times 3!=24×6\displaystyle {}= 24 \times 6=144 通り‾\displaystyle {}= \underline{144 \text{ 通り}}
自己採点：
記録を読み込み中…

問10　★★

a\mathrm{a}，b\mathrm{b}，c\mathrm{c}，d\mathrm{d}，e\mathrm{e}，f\mathrm{f} の 66 文字を1列に並べます。

(1) a\mathrm{a} と b\mathrm{b} が隣り合う並べ方は何通りあるか求めなさい。

(2) a\mathrm{a} と b\mathrm{b} が隣り合わない並べ方は何通りあるか求めなさい。

(3) a\mathrm{a} が b\mathrm{b} より左にある並べ方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 240240 通り　(2) 480480 通り　(3) 360360 通り

解説

(1) a\mathrm{a} と b\mathrm{b} をひとまとめにすると 55 つのものの順列で 5!5!=120{}= 120 通り、まとまりの中の並べ方が 22 通りなので

5!×2\displaystyle 5! \times 2=240 通り‾\displaystyle {}= \underline{240 \text{ 通り}}

(2) 全体は 6!6!=720{}= 720 通りです。「隣り合う」と「隣り合わない」は同時には起こらず、合わせると全体になるので

720\displaystyle 720−240\displaystyle {}- 240=480 通り‾\displaystyle {}= \underline{480 \text{ 通り}}

すき間に入れる方法でも、c\mathrm{c}〜f\mathrm{f} を先に並べて 4!4!=24{}= 24 通り、その 55 つのすき間に a\mathrm{a}，b\mathrm{b} を入れて 5P2{}_5\mathrm{P}_2=20{}= 20 通りで、24×2024 \times 20=480{}= 480 通りと確かめられます。

(3) どの並べ方も、a\mathrm{a} と b\mathrm{b} の場所を入れかえると、「a\mathrm{a} が左」と「b\mathrm{b} が左」がちょうど入れかわります。この入れかえで2つずつ組になるので、「a\mathrm{a} が左」は全体のちょうど半分です。

7202\displaystyle \frac{720}{2}=360 通り‾\displaystyle {}= \underline{360 \text{ 通り}}
自己採点：
記録を読み込み中…

問11　★★

a\mathrm{a}，b\mathrm{b}，c\mathrm{c}，d\mathrm{d}，e\mathrm{e} の 55 文字をすべて使ってできる文字列を、辞書式配列で abcde\mathrm{abcde} から順に並べます。

(1) cbeda\mathrm{cbeda} は何番目か求めなさい。

(2) 7070 番目の文字列を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 6060 番目　(2) cebda\mathrm{cebda}

解説

(1) cbeda\mathrm{cbeda} より前にある文字列を、先頭から順に数えます。

  • a\mathrm{a} で始まるもの：残り 44 文字の並べ方で 4!4!=24{}= 24 個
  • b\mathrm{b} で始まるもの：2424 個
  • ca\mathrm{ca} で始まるもの：3!3!=6{}= 6 個
  • cba\mathrm{cba}，cbd\mathrm{cbd} で始まるもの：2!2!=2{}= 2 個ずつで 44 個
  • cbe\mathrm{cbe} で始まるもののうち cbead\mathrm{cbead}：11 個

前にあるのは 2424+24{}+ 24+6{}+ 6+4{}+ 4+1{}+ 1=59{}= 59 個なので、cbeda\mathrm{cbeda} は 60 番目‾\underline{60 \text{ 番目}} です。

(2) 先頭の文字ごとに 2424 個ずつなので、a\mathrm{a} が 11〜2424 番目、b\mathrm{b} が 2525〜4848 番目、c\mathrm{c} が 4949〜7272 番目です。7070 番目は c\mathrm{c} で始まります。

c\mathrm{c} のあとの2文字目ごとに 3!3!=6{}= 6 個ずつで、ca\mathrm{ca} が 4949〜5454、cb\mathrm{cb} が 5555〜6060、cd\mathrm{cd} が 6161〜6666、ce\mathrm{ce} が 6767〜7272 番目です。ce\mathrm{ce} で始まる6個を並べると

ceabd (67),\displaystyle \mathrm{ceabd}\ (67),ceadb (68),\displaystyle \mathrm{ceadb}\ (68),cebad (69),\displaystyle \mathrm{cebad}\ (69),cebda (70)\displaystyle \mathrm{cebda}\ (70)

なので、7070 番目は cebda‾\underline{\mathrm{cebda}} です。

自己採点：
記録を読み込み中…

問12　★★

00，11，22，33，44，55 の 66 個の数字から異なる 44 個を使って 44 桁の整数を作ります。

(1) 44 桁の整数は全部で何個できるか求めなさい。

(2) そのうち 55 の倍数は何個あるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 300300 個　(2) 108108 個

解説

(1) 千の位は 00 以外の 55 通り、残りの百・十・一の位には、千の位で使った数字を除く 55 個から 33 個を並べるので 5P3{}_5\mathrm{P}_3=60{}= 60 通りです。

5×60\displaystyle 5 \times 60=300 個‾\displaystyle {}= \underline{300 \text{ 個}}

(2) 55 の倍数は一の位が 00 か 55 のときです。一の位が 00 かどうかで千の位の候補の数が変わるので、場合分けします。

  • 一の位が 00：残り 55 個の数字から千・百・十の位に 33 個を並べて 5P3{}_5\mathrm{P}_3=60{}= 60 個
  • 一の位が 55：千の位は 00 と 55 以外の 44 通り、百・十の位は残り 44 個から 22 個を並べて 4P2{}_4\mathrm{P}_2=12{}= 12 通りなので 4×124 \times 12=48{}= 48 個

和の法則より 6060+48{}+ 48=108 個‾{}= \underline{108 \text{ 個}} です。

自己採点：
記録を読み込み中…

問13　★★

両親と子ども 44 人の合計 66 人が円形のテーブルに座ります。

(1) 両親が隣り合う座り方は何通りあるか求めなさい。

(2) 両親が隣り合わない座り方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 4848 通り　(2) 7272 通り

解説

(1) 両親をひとまとめにすると、まとまり1つと子ども 44 人の合計 55 つの円順列で (5−1)!(5 - 1)!=24{}= 24 通りです。まとまりの中で父と母の並び方が 22 通りあるので

4!×2\displaystyle 4! \times 2=48 通り‾\displaystyle {}= \underline{48 \text{ 通り}}

(2) 66 人の円順列は全部で (6−1)!(6 - 1)!=120{}= 120 通りです。そこから (1) を引いて

120\displaystyle 120−48\displaystyle {}- 48=72 通り‾\displaystyle {}= \underline{72 \text{ 通り}}

確かめとして、父の席を固定すると、母の座れる席は残り 55 席のうち父の両隣を除いた 33 席です。残りの子ども 44 人の並び方は 4!4!=24{}= 24 通りなので、3×243 \times 24=72{}= 72 通りで一致します。

自己採点：
記録を読み込み中…

問14　★★

66 人を2つに分けます。どちらにも少なくとも1人は入るものとします。

(1) 66 人を部屋 AA，BB に分ける方法は何通りあるか求めなさい。

(2) 66 人を区別のない2つのグループに分ける方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 6262 通り　(2) 3131 通り

解説

(1) 空き部屋があってもよいとすると、66 人のそれぞれが AA，BB の 22 通りから選ぶので 262^6=64{}= 64 通りです。このうち、全員が AA に入る 11 通りと全員が BB に入る 11 通りは条件を満たしません。

64\displaystyle 64−2\displaystyle {}- 2=62 通り‾\displaystyle {}= \underline{62 \text{ 通り}}

(2) (1) の分け方で部屋の名前 AA，BB を入れかえると、グループの分け方としては同じものになります。(1) の 6262 通りは、この入れかえで2つずつ組になっているので

622\displaystyle \frac{62}{2}=31 通り‾\displaystyle {}= \underline{31 \text{ 通り}}

(1) の段階で「どちらも1人以上」にしておくのが大切です。先に 64÷264 \div 2=32{}= 32 としてから 11 を引く方法でも同じ答えになりますが、何を引いているのかを意識しましょう。

自己採点：
記録を読み込み中…

問15　★★

11，22，33，44 の 44 個の数字を、同じ数字をくり返し使ってよいとして並べ、33 桁の整数を作ります。

(1) 33 桁の整数は全部で何個できるか求めなさい。

(2) そのうち、同じ数字を2回以上使っているものは何個あるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 6464 個　(2) 4040 個

解説

(1) どの位も 44 通りなので、重複順列で 434^3=64 個‾{}= \underline{64 \text{ 個}} です。

(2) 「同じ数字を2回以上使う」の反対は「33 つの位の数字がすべて異なる」です。これは 44 個から 33 個取る順列なので 4P3{}_4\mathrm{P}_3=24{}= 24 個です。第2章の公式5と同じく、全体から引きます。

64\displaystyle 64−24\displaystyle {}- 24=40 個‾\displaystyle {}= \underline{40 \text{ 個}}
自己採点：
記録を読み込み中…

問16　★★

a\mathrm{a}，b\mathrm{b}，c\mathrm{c}，d\mathrm{d}，e\mathrm{e}，f\mathrm{f}，g\mathrm{g} の 77 文字を1列に並べます。a\mathrm{a}，b\mathrm{b}，c\mathrm{c} の 33 文字が、左からこの順に並ぶ（隣り合わなくてもよい）並べ方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

840840 通り

解説

先に d\mathrm{d}，e\mathrm{e}，f\mathrm{f}，g\mathrm{g} の 44 文字を、77 か所のうち 44 か所に並べます。その方法は 7P4{}_7\mathrm{P}_4=7×6×5×4{}= 7 \times 6 \times 5 \times 4=840{}= 840 通りです。

残った 33 か所には、左から a\mathrm{a}，b\mathrm{b}，c\mathrm{c} の順に入れるしかないので 11 通りです。よって 840 通り‾\underline{840 \text{ 通り}} です。

別の考え方として、77 文字の並べ方 7!7!=5040{}= 5040 通りを、a\mathrm{a}，b\mathrm{b}，c\mathrm{c} の3文字の場所だけを入れかえたもの同士でまとめると、3!3!=6{}= 6 通りずつの組になり、各組に「この順」のものがちょうど1つあります。5040÷65040 \div 6=840{}= 840 通りと一致します。

自己採点：
記録を読み込み中…

問17　★★★

55 人を AA，BB，CC の 33 つの部屋に入れます。どの部屋にも少なくとも1人は入るような入れ方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

150150 通り

解説

空き部屋があってもよい入れ方は 353^5=243{}= 243 通りです。ここから、空き部屋がある入れ方を第1章の包除原理で数えて引きます。

部屋 AA が空になる入れ方の集合を XAX_A などとします。

  • n(XA)n(X_A)：55 人が BB，CC から選ぶので 252^5=32{}= 32 通り。XBX_B，XCX_C も同じ
  • n(XA∩XB)n(X_A \cap X_B)：全員が CC に入るので 11 通り。ほかの2部屋の組も同じ
  • n(XA∩XB∩XC)n(X_A \cap X_B \cap X_C)=0{}= 0（55 人がどこにも入らないことはない）
n(XA∪XB∪XC)\displaystyle n(X_A \cup X_B \cup X_C)=3×32\displaystyle {}= 3 \times 32−3×1\displaystyle {}- 3 \times 1+0\displaystyle {}+ 0=93\displaystyle {}= 93

よって、どの部屋にも少なくとも1人いる入れ方は

243\displaystyle 243−93\displaystyle {}- 93=150 通り‾\displaystyle {}= \underline{150 \text{ 通り}}

「空き部屋が1つ」は 3×(25−2)3 \times (2^5 - 2)=90{}= 90 通り、「空き部屋が2つ」は 33 通りで、9090+3{}+ 3=93{}= 93 と確かめることもできます。

自己採点：
記録を読み込み中…

問18　★★★

立方体の 66 つの面を、異なる 66 色をすべて使って塗り分けます。立方体を回転させて一致する塗り方は同じものとみなすとき、塗り方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

3030 通り

解説

回転で重なるものを同じとみなすので、円順列と同じく「1つを固定する」考え方を使います。

まず、ある1色（たとえば赤）の面が上になるように立方体を置きます。どの塗り方も、回せば必ず赤を上にできるので、上は赤に固定してかまいません。

  • 下の面：残り 55 色のどれか 11 色で 55 通り
  • 側面の 44 面：残りの 44 色を、上下の軸のまわりの回転で重なるものを同じとみなして並べるので、44 個の円順列で (4−1)!(4 - 1)!=6{}= 6 通り
5×6\displaystyle 5 \times 6=30 通り‾\displaystyle {}= \underline{30 \text{ 通り}}

立方体の回転は、どの面を上にするか（66 通り）とそのまま横に何回回すか（44 通り）で 2424 通りあり、66 色がすべて異なれば、どの塗り方にも回転で重なる塗り方がちょうど 2424 個ずつあります。6!÷246! \div 24=720÷24{}= 720 \div 24=30{}= 30 通りと確かめられます。

自己採点：
記録を読み込み中…

問19　★★★

男子 44 人と女子 44 人が円形のテーブルに座ります。男子 AA と女子 BB はこの中の1人ずつです。

(1) 男女が交互に座る座り方は何通りあるか求めなさい。

(2) 男女が交互に座り、さらに AA と BB が隣り合う座り方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 144144 通り　(2) 7272 通り

解説

(1) 先に男子 44 人を1つおきの席に円形に並べます。男子だけの円順列で (4−1)!(4 - 1)!=6{}= 6 通りです。男子の並びが決まると、男子と男子の間の 44 席は区別できるので、女子 44 人をそこに並べる方法は 4!4!=24{}= 24 通りです。

3!×4!\displaystyle 3! \times 4!=6×24\displaystyle {}= 6 \times 24=144 通り‾\displaystyle {}= \underline{144 \text{ 通り}}

(2) 男子の並び方は (1) と同じく 3!3!=6{}= 6 通りです。女子の 44 席のうち AA の隣にあるのは AA の右隣と左隣の 22 席なので、BB の座り方は 22 通りです。残りの女子 33 人を残りの 33 席に並べる方法は 3!3!=6{}= 6 通りです。

3!×2×3!\displaystyle 3! \times 2 \times 3!=6×2×6\displaystyle {}= 6 \times 2 \times 6=72 通り‾\displaystyle {}= \underline{72 \text{ 通り}}

BB が座れる女子の 44 席のうち 22 席が AA の隣なので、(1) のちょうど半分になっています。

自己採点：
記録を読み込み中…

問20　★★★

00，11，22，33，44，55 の 66 個の数字から異なる 44 個を使って 44 桁の整数を作るとき、33 の倍数は何個できるか求めなさい。

つまずいたときは：
答えを見る
答え

9696 個

解説

33 の倍数は、各位の数字の和が 33 の倍数になる数です。そこで、まず「どの 44 個の数字を使うか」を決めます。

66 個の数字の和は 00+1{}+ 1+2{}+ 2+3{}+ 3+4{}+ 4+5{}+ 5=15{}= 15 で 33 の倍数です。使う 44 個の和が 33 の倍数になるのは、使わない2個の和が 33 の倍数になるときです。和が 33 の倍数になる2個の組は

{0, 3},\displaystyle \{0,\ 3\}, {1, 2},\displaystyle \ \{1,\ 2\}, {1, 5},\displaystyle \ \{1,\ 5\}, {2, 4},\displaystyle \ \{2,\ 4\}, {4, 5}\displaystyle \ \{4,\ 5\}

の 55 組です（33 で割った余りが 00 と 00、または 11 と 22 の組）。

  • {0, 3}\{0,\ 3\} を使わないとき：11，22，44，55 で、00 を含まないので 4!4!=24{}= 24 個
  • 残りの 44 組を使わないとき：使う数字に 00 が含まれます。44 個の並べ方 4!4!=24{}= 24 通りから、千の位が 00 になる 3!3!=6{}= 6 通りを引いて 1818 個ずつ

和の法則より

24\displaystyle 24+4×18\displaystyle {}+ 4 \times 18=24\displaystyle {}= 24+72\displaystyle {}+ 72=96 個‾\displaystyle {}= \underline{96 \text{ 個}}

「使う数字の組を決める」段階と「並べる」段階に分けると、00 の扱いを組ごとにまとめて処理できます。

自己採点：
記録を読み込み中…

数学小話コーナー

あみだくじは順列を作る機械

掃除当番やプレゼント交換で使うあみだくじ。縦線を人数分引いて、下に当番や景品を書き、間に横線を好きなだけ足していきます。不思議なのは、横線をどんなにでたらめに引いても、2人が同じ行き先にたどり着くことは決してないことです。

理由は、横線1本の働きにあります。横線は、となり合う2本の縦線を通る人を「入れかえる」だけです。上から下へたどる途中で、入れかえを何回くり返しても、行き先がかぶることはありません。あみだくじは、上の nn 人を下の nn か所に1人ずつ割り当てる、つまり nn 人の順列を1つ作る機械なのです。

逆に、n!n! 通りのどの順列も、横線をうまく引けば作れます。たとえば 44 人の行き先を「完全に逆順」（左から 11 番目の人が右端へ、…）にしたいとします。となり合う2人の入れかえだけで逆順にするには、どの2人も一度は追い越し合わなければならず、その組は 4×3÷24 \times 3 \div 2=6{}= 6 組あります。実際、横線 66 本で逆順のあみだくじが作れ、55 本以下では作れません。

豆知識

「あみだ」の名は、もともと縦線ではなく、中心から放射状に線を引いたくじの形が阿弥陀仏の後光に似ていたからだといわれます（※諸説あり）。室町時代ごろには、くじの結果に応じて出し合ったお金で、皆で食べ物を買って分け合う遊びとして行われていたようです（※諸説あり）。

5040 通りを鳴らし切る鐘

イギリスの教会には、66〜88 個ほどの鐘を塔につるし、鳴らす順番を少しずつ変えていく転調鳴鐘（チェンジ・リンギング）という伝統があります。鐘を高い音から 11，22，33，… と番号で呼び、全部の鐘を1回ずつ鳴らす1巡を1つの「列」とします。たとえば 44 個の鐘なら、12341234 の次に 21432143、その次に 24132413、… と、1列ごとに順番を変えていきます。

決まりは主に3つです。

  • どの鐘も、次の列では前後に最大1つしか動けない（重い鐘の揺れの速さは急に変えられないため）
  • 同じ列を2回鳴らしてはいけない
  • 最初の列 1234⋯1234\cdots から始め、最後にまた最初の列に戻る

「前後に1つしか動けない」は、1つめの小話のあみだくじの横線と同じ、となり合う2つの入れかえです。となり合う入れかえだけを使って、n!n! 通りの順列を1回ずつ残らず通る道筋を見つけられれば、「すべての列を鳴らし切った」ことになります。77 個の鐘なら 7!7!=5040{}= 5040 列で、休まず鳴らしても約 33 時間かかります。記録に残る初めての完奏は 1715 年ごろのノリッジの教会とされています（※諸説あり）。

17 世紀の鳴鐘家ファビアン・ステッドマンは、1668 年の『ティンティナロギア』などで、こうした並べかえの手順を体系的にまとめました。順列を「入れかえの積み重ね」として扱う発想は、のちに数学で「群」と呼ばれる考え方の先がけの1つとして紹介されることがあります。

豆知識

88 個の鐘ですべての列を鳴らすと 8!8!=40320{}= 40320 列です。1963 年にイギリスの鐘の鋳造所で、交代なしでこれを鳴らし切り、およそ 1818 時間かかったという記録があります（※細かい数字は資料によって違います）。

セールスマンは何通りの道を回るか

セールスマンが、自分の町を出発して nn−1{}- 1 か所の町を1回ずつ訪ね、自分の町に戻ってくるとします。移動の合計距離がいちばん短い回り方を探すのが、巡回セールスマン問題です。

回り方は何通りあるでしょうか。出発する町は決まっているので、残りの nn−1{}- 1 か所を訪ねる順番を並べて (n−1)!(n - 1)! 通りです。ただし、同じ道順を逆向きにたどっても距離は同じなので、22 で割って

(n−1)!2 通り\frac{(n - 1)!}{2} \text{ 通り}

を比べればよいことになります。「円形に並べて、回転と裏返しで同じとみなす」――じゅず順列の式そのものです。

55 都市なら 4!2\dfrac{4!}{2}=12{}= 12 通りで、手で全部書き出せます。1010 都市では 9!2\dfrac{9!}{2}=181440{}= 181440 通り、2020 都市では 19!2\dfrac{19!}{2} で約 6.1×10166.1 \times 10^{16} 通りになります。1秒間に1億通りの道を調べるコンピューターでも、2020 都市を全部調べ切るのに約 1919 年かかる計算です。都市が1つ増えるたびに、回り方の数はそれまでの何倍にも膨らみます。nn 都市から nn+1{}+ 1 都市になると、ちょうど nn 倍です。

そのため、実際には全部を調べるのではなく、「明らかに長くなる道順はまとめて調べるのをやめる」といった工夫を重ねて最短の道を探します。こうした方法の進歩で、数万都市という規模の問題でも最短の道順が求められた例があります。

豆知識

宅配便の配送ルート、工場で基板に穴を開けるドリルの動く順番、天体望遠鏡で星を観測する順番など、「たくさんの地点を1回ずつ効率よく回る」問題はあちこちにあり、どれも巡回セールスマン問題の仲間です。

厳密定義（発展）

※ここは発展ページです。本文では、席を1つずつ埋める考え方で順列を数え、円順列は「回転で重なるものを同じとみなす」と説明しました。ここでは、順列を集合の言葉で定め、第2章の和の法則・積の法則から公式を証明します。「同じとみなす」を正確に扱うための「割り算の法則」も示します。

順列の定義と個数

定義1：順列

nn 個の要素をもつ集合 AA と 00≦r{}\leqq r≦n{}\leqq n を満たす整数 rr について、AA の要素を rr 個並べた組 (a1, a2, …, ar)(a_1,\ a_2,\ \ldots,\ a_r) で、どの2つの成分も異なるものを、AA の rr 個の順列という。その全体の集合の要素の個数を nPr{}_n\mathrm{P}_r で表す。rr=0{}= 0 のときは、何も並べない組 ( )(\ ) だけを考え、nP0{}_n\mathrm{P}_0=1{}= 1 とする。

組 (a1, …, ar)(a_1,\ \ldots,\ a_r) は第2章の定義2（直積）と同じく順番を区別します。順列の集合は、直積 A×A×⋯×AA \times A \times \cdots \times A から「同じ成分を2回以上含む組」を除いたものです。

定理1：順列の個数

11≦r{}\leqq r≦n{}\leqq n のとき

nPr\displaystyle {}_n\mathrm{P}_r=n(n−1)(n−2)⋯(n−r+1)\displaystyle {}= n(n - 1)(n - 2) \cdots (n - r + 1)

証明　jj 番目の成分 aja_j は、それまでの a1,a_1, …,\ \ldots, aj−1\ a_{j-1} と異なる AA の要素である。a1,a_1, …,\ \ldots, aj−1\ a_{j-1} がどのように決まっていても、それらはすべて異なるので、aja_j の候補は AA の nn 個からその jj−1{}- 1 個を除いた nn−j{}- j+1{}+ 1 個である。候補の中身は前の成分によって変わるが、個数は一定なので、第2章の定理3（積の法則の一般形）より、nPr{}_n\mathrm{P}_r は

n×(n−1)×⋯×(n−r+1)n \times (n - 1) \times \cdots \times (n - r + 1)

である。（証明終）

定義2：階乗

自然数 nn に対して n!n!=n(n−1)⋯2⋅1{}= n(n - 1) \cdots 2 \cdot 1 と定め、nn の階乗という。さらに 0!0!=1{}= 1 と定める。

定理1で rr=n{}= n とすると nPn{}_n\mathrm{P}_n=n!{}= n! です。また 11≦r{}\leqq r≦n{}\leqq n のとき

n!(n−r)!\displaystyle \frac{n!}{(n - r)!}=n(n−1)⋯(n−r+1)⋅(n−r)!(n−r)!\displaystyle {}= \frac{n(n - 1) \cdots (n - r + 1) \cdot (n - r)!}{(n - r)!}=nPr\displaystyle {}= {}_n\mathrm{P}_r

が成り立ちます（rr=n{}= n のときは分母が 0!0!=1{}= 1 です）。rr=0{}= 0 のときも n!n!\dfrac{n!}{n!}=1{}= 1=nP0{}= {}_n\mathrm{P}_0 となり、定義1の約束と合います。0!0!=1{}= 1 は、この式が端の場合にも崩れないように選んだ約束です（数と式 第7章の厳密定義ページでも、二項係数について同じ約束をしました）。

割り算の法則

円順列やじゅず順列では、「回転で重なるもの」を1つにまとめて数えました。まとめたグループがどれも同じ大きさなら、個数は割り算で求まります。

定理2：割り算の法則

有限集合 SS が、どの2つも共通な要素をもたない空でない部分集合 G1,G_1, G2,\ G_2, …,\ \ldots, Gm\ G_m に分けられていて、どの GiG_i も要素の個数がちょうど kk 個であるとする。このとき

m\displaystyle m=n(S)k\displaystyle {}= \frac{n(S)}{k}

証明　SS=G1∪⋯∪Gm{}= G_1 \cup \cdots \cup G_m で、どの2つも共通な要素をもたないので、第2章の定理1（和の法則）より

n(S)\displaystyle n(S)=n(G1)\displaystyle {}= n(G_1)+⋯\displaystyle {}+ \cdots+n(Gm)\displaystyle {}+ n(G_m)=k+⋯+k⏟m 個\displaystyle {}= \underbrace{k + \cdots + k}_{m \text{ 個}}=mk\displaystyle {}= mk

である。両辺を kk で割ればよい。（証明終）

グループ1つを「同じとみなすもの」の集まりとすると、mm が「同じとみなしたあとの個数」です。定理2を使うには、どのグループもちょうど kk 個であることを確かめる必要があります。本文の j14(2)（部屋の名前の入れかえで2つずつ組にする）や j18（立方体の回転で 2424 個ずつ）も、この形の数え方です。

円順列とじゅず順列

AA={a1, …, an}{}= \{a_1,\ \ldots,\ a_n\} の nn 個の順列 (x1, x2, …, xn)(x_1,\ x_2,\ \ldots,\ x_n) を、円周上に時計回りに置いたものと考えます。1つずらす操作

(x1, x2, …, xn)\displaystyle (x_1,\ x_2,\ \ldots,\ x_n)⟼(x2, x3, …, xn, x1)\displaystyle {}\longmapsto (x_2,\ x_3,\ \ldots,\ x_n,\ x_1)

を何回か行って互いに移り合う順列を「同じ円順列」とします。

定理3：円順列の個数

異なる nn 個（nn≧1{}\geqq 1）のものの円順列は (n−1)!(n - 1)! 通りである。

証明　順列 xx=(x1, …, xn){}= (x_1,\ \ldots,\ x_n) を jj 回ずらしたものを x(j)x^{(j)} とする（x(0)x^{(0)}=x{}= x）。nn 回ずらすと元に戻るので、xx と同じ円順列になる順列は x(0),x^{(0)}, x(1),\ x^{(1)}, …,\ \ldots, x(n−1)\ x^{(n-1)} である。

これらが互いに異なることを示す。00≦i{}\leqq i<j{}< j≦n{}\leqq n−1{}- 1 として、x(i)x^{(i)} と x(j)x^{(j)} の先頭の成分はそれぞれ xi+1x_{i+1} と xj+1x_{j+1} で、成分がすべて異なるので xi+1x_{i+1}≠xj+1{}\neq x_{j+1} である。よって x(i)x^{(i)}≠x(j){}\neq x^{(j)} となる。

したがって、n!n! 個の順列全体は、同じ円順列ごとのグループに分かれ、どのグループもちょうど nn 個である。定理2より、円順列の個数は n!n\dfrac{n!}{n}=(n−1)!{}= (n - 1)! である。（証明終）

証明で「成分がすべて異なる」ことを使いました。同じものを含む場合（たとえば赤玉2個と白玉2個）は、ずらしても変わらない並び（赤白赤白を2つずらす）があり、グループの大きさがそろわないので、この割り算は使えません。

定理4：じゅず順列の個数

異なる nn 個（nn≧3{}\geqq 3）のものについて、回転と裏返しで一致するものを同じとみなすと、その個数は (n−1)!2\dfrac{(n - 1)!}{2} である。

証明　裏返しは、時計回りの並びを逆向きに読むことにあたる。円順列 XX を裏返したものを X′X' とする。裏返しを2回行うと元に戻るので (X′)′(X')'=X{}= X であり、円順列全体は {X, X′}\{X,\ X'\} という組に分かれる。

nn≧3{}\geqq 3 のとき XX≠X′{}\neq X' を示す。XX の中で、ある要素 aa の時計回りの隣を bb、反時計回りの隣を cc とする。nn≧3{}\geqq 3 なので bb≠c{}\neq c である。X′X' では、aa の時計回りの隣は cc になる。回転しても「aa の時計回りの隣」は変わらないので、X′X' を回転しても XX にはならない。よって XX≠X′{}\neq X' である。

したがって、(n−1)!(n - 1)! 個の円順列は、ちょうど2個ずつのグループに分かれる。定理2より、求める個数は (n−1)!2\dfrac{(n - 1)!}{2} である。（証明終）

nn=1,{}= 1, 2\ 2 のときは、裏返しても同じ円順列になるので、答えは 11 通りです（公式 (n−1)!2\dfrac{(n - 1)!}{2} は 12\dfrac{1}{2} になって合いません）。公式4に nn≧3{}\geqq 3 の条件がついているのはこのためです。

写像として見た重複順列と順列

最後に、重複順列と順列を「対応」の言葉で見直します。

定義3：写像

集合 RR の各要素 xx に、集合 AA の要素をちょうど1つずつ対応させる規則 ff を、RR から AA への写像といい、f:Rf : R→A{}\to A と書く。異なる xx にはいつも異なる要素が対応するとき、ff を単射という。

RR={1, 2, …, r}{}= \{1,\ 2,\ \ldots,\ r\} のとき、写像 ff を決めることは、組 (f(1), f(2), …, f(r))(f(1),\ f(2),\ \ldots,\ f(r)) を決めることと同じです。「11 番目の席に f(1)f(1)、22 番目の席に f(2)f(2)、…」と並べるのだと考えてください。

定理5：写像の個数

n(R)n(R)=r{}= r，n(A)n(A)=n{}= n とする。

  1. RR から AA への写像は nrn^r 個ある（重複順列）。
  2. RR から AA への単射は、rr≦n{}\leqq n のとき nPr{}_n\mathrm{P}_r 個あり、rr>n{}> n のとき 11 個もない。

証明　RR={1, …, r}{}= \{1,\ \ldots,\ r\} としてよい。写像と組 (f(1), …, f(r))(f(1),\ \ldots,\ f(r)) は1対1に対応する。

  1. 組は直積 A×⋯×AA \times \cdots \times A（rr 個）の要素なので、第2章の定理2をくり返し使って nrn^r 個である。
  2. 単射に対応する組は、成分がすべて異なる組、つまり定義1の順列である。rr≦n{}\leqq n なら定理1より nPr{}_n\mathrm{P}_r 個ある。rr>n{}> n なら、成分がすべて異なる rr 個の組は AA の異なる要素を rr 個含むが、AA には nn<r{}< r 個しかないので存在しない。（証明終）

本文の例題6(2)（44 人を 33 部屋に入れる）は、「人の集合 → 部屋の集合」という写像の個数 343^4 でした。「何が何を選ぶのか」は、写像の向き（どちらが RR でどちらが AA か）を確かめることにあたります。定理5の2は、44 人を 33 部屋に「どの2人も別の部屋」には入れられない、という当たり前のことを述べています。

第4章の組合せ nCr{}_n\mathrm{C}_r は、「rr 個の順列を、並べる順番だけが違うもの同士でまとめる」ことで定理2から導けます。どのグループも r!r! 個ずつになることが鍵です。

この章の学習が終わったら

学習完了テストを受ける