MENU
  1. トップ
  2. 基礎体系
  3. 基礎数学
  4. 基礎 数学A
  5. 【基礎 数学(数学A)】Module 1：場合の数(1) 順列

【基礎 数学(数学A)】Module 1：場合の数(1) 順列

当ページのリンクには広告が含まれています。

本モジュールの目的と構成

数学Aで我々が最初に対峙する「場合の数」という分野は、単なる計算技術の習得に留まらず、物事を論理的かつ体系的に整理し、数え上げるための思考の「方法論」そのものを鍛え上げるための絶好の訓練場です。ここで培われる思考法は、後続の「組合せ」や「確率」の学習における盤石な土台となるだけでなく、大学での学問や社会における問題解決の場面においても、その真価を発揮する普遍的な知的能力へと繋がっていきます。

本モジュールでは、この「場合の数」の根幹をなす「順列」の概念を、その最も基本的な原則から、複雑な応用問題に至るまで、深く掘り下げていきます。単に公式を暗記し、機械的に適用するのではなく、それぞれの公式が「なぜ」その形でなければならないのか、その背後にある論理構造を徹底的に解明することに主眼を置きます。これにより、未知の問題に直面した際に、自ら思考し、最適な解法を導き出すことのできる、真の実践力を養成することを目指します。

本モジュールは、以下の学習項目を通じて、順列の体系的理解を構築します。

  1. 和の法則と積の法則: 全ての場合の数、順列、組合せ、確率の思考の根底に流れる、最も基本的かつ強力な二大原理を学びます。これらの法則をいつ、どのように使い分けるのかを明確に理解することが、全てのスタートラインとなります。
  2. 順列 (nPr) の定義と計算: 「順序」を考慮して並べるという、順列の核心的な概念を定義し、その計算方法を積の法則から導出します。
  3. 階乗 (n!) の概念: n個の異なるものを全て並べる場合の数を表す「階乗」を学び、これが順列計算の基盤となることを理解します。
  4. 円順列: 直線的な並びから解放され、円形に配置する場合の考え方を学びます。「固定」という独創的な発想が、どのように重複カウントを防ぐのかを探求します。
  5. 重複順列: 同じものを繰り返し用いることが許される場合の順列です。この概念が、パスワードや記号の系列など、現代的な問題にも広く応用されることを見ます。
  6. 同じものを含む順列: 区別できない要素が含まれる場合の並べ方を学びます。なぜ特定の階乗で「割る」という操作が必要になるのか、その本質を理解します。
  7. 辞書式配列法: 順列を特定の規則（アルファベット順や数字の大小順）に従って並べる方法論です。与えられた順列が何番目に来るのか、あるいは特定の位置に来る順列は何かを論理的に突き止める技術を習得します。
  8. 条件付き順列（隣り合う、隣り合わない）: 「特定の要素が隣り合う」「隣り合わない」といった、現実の問題で頻出する制約条件を処理するための戦略的アプローチ（「ひとかたまり」にする、「後から挿入する」など）を学びます。
  9. 完全順列（攪乱順列）: 全ての要素が元の位置からずれてしまうという、特殊ながらも興味深い順列のパターンを探求します。漸化式を用いた思考法にも触れます。
  10. 塗り分け問題: これまで学んだ順列の知識を総動員し、地図の領域などを特定の色で塗り分けるという、応用的な問題解決に挑戦します。

このモジュールを通じて、読者の皆様が獲得するのは、単なる数学の知識ではありません。それは、複雑な事象を正確に分解し、整理し、数え上げるという、論理的思考の「方法論」そのものです。この知的な冒険が、皆様の思考の世界をより広く、深く、そして豊かにすることを確信しています。

目次

1. 和の法則と積の法則

場合の数を学ぶ旅は、ここから始まります。これから我々が対峙するであろう、いかなる複雑な順列や組合せの問題も、その根源をたどれば、これから学ぶ「和の法則」と「積の法則」という、二つの極めてシンプルかつ強力な原理に行き着きます。これらは単なる計算ルールではなく、物事をどのように分類し、どのように一連のプロセスとして捉えるかという、思考の基本的な枠組みを提供するものです。これらの法則の本質を深く理解し、両者を的確に使い分ける能力こそが、場合の数の世界を自由に探検するための羅針盤となります。

1.1. 和の法則：排反な事象の統合

和の法則 (Sum Rule) は、複数の選択肢群が存在し、それらの選択肢群が互いに重複しない（同時に起こり得ない）場合に、総数を求めるための基本法則です。論理学的な言葉で言えば、事象が排反である場合に適用されます。

【定義】

2つの事柄A、Bがあり、それらが同時に起こることがないとする。事柄Aの起こり方が \(m\) 通り、事柄Bの起こり方が \(n\) 通りあるとき、AまたはBのいずれかが起こる場合の数は、\(m + n\) 通りである。

この法則の核心は「同時に起こらない」という点にあります。言い換えれば、選択肢Aを選んだ場合、選択肢Bを選ぶ可能性は完全に消滅し、その逆もまた然り、という状況です。これらの選択肢は、完全に独立した別の世界線に存在するかのように、互いに交わることがありません。したがって、全体の総数を求めるには、それぞれの世界の選択肢の数を単純に足し合わせれば良いのです。

具体例1：通学路の選択

自宅から学校へ行く方法として、電車を利用する方法が3路線あり、バスを利用する方法が4路線あるとします。電車とバスを同時に利用することはできない（排反な事象）とすると、自宅から学校へ行く方法は全部で何通りあるでしょうか。

  • 事柄A: 電車を利用する（3通り）
  • 事柄B: バスを利用する（4通り）

「電車を利用する」ことと「バスを利用する」ことは、同時に起こり得ません。したがって、和の法則を適用できます。

求める場合の数は、 \(3 + 4 = 7\) 通りとなります。

この例は非常に単純ですが、和の法則の思考プロセスを明確に示しています。「通学する」という大きな目的を、「電車ルート」と「バスルート」という、互いに排反な2つのカテゴリに分類し、それぞれのカテゴリ内の場合の数を数え上げた後、最後にそれらを統合（足し算）する、という流れです。

和の法則の適用を見抜くための思考のポイント

  • 「または」「あるいは」「〜か、〜」 という接続詞で問題文が構成されている場合、和の法則が適用できる可能性が高いです。
  • 場合分け を行ったとき、それぞれのケースが互いに重複しない（排反である）ことを確認した上で、各ケースの結果を足し合わせるのは、和の法則の典型的な応用です。
  • 全体を、互いに素な（共通部分のない）集合 に分割し、各集合の要素数を足し合わせるイメージを持つと、より本質的な理解に繋がります。

発展：3つ以上の事柄に対する和の法則

和の法則は、3つ以上の互いに排反な事柄に対しても同様に拡張できます。

事柄A, B, Cがどの2つも同時に起こらない場合、Aの起こり方が \(m\) 通り、Bの起こり方が \(n\) 通り、Cの起こり方が \(l\) 通りあるならば、AまたはBまたはCのいずれかが起こる場合の数は、\(m + n + l\) 通りとなります。

具体例2：サイコロの目の和

大小2つのサイコロを同時に投げるとき、目の和が4になるか、または6になる場合は何通りあるでしょうか。

  1. 場合分け1：目の和が4になる場合(大, 小) = (1, 3), (2, 2), (3, 1) の 3通り です。
  2. 場合分け2：目の和が6になる場合(大, 小) = (1, 5), (2, 4), (3, 3), (4, 2), (5, 1) の 5通り です。

「目の和が4になる」という事象と、「目の和が6になる」という事象は、同時に起こることはあり得ません（排反）。したがって、和の法則により、求める場合の数は、

\(3 + 5 = 8\) 通りとなります。

このように、複雑な問題も「互いに排反なケースに場合分けし、それぞれを数え上げてから足し合わせる」という和の法則の思考フレームワークを用いることで、整然と解き明かすことができるのです。

1.2. 積の法則：連続する試行の連結

積の法則 (Product Rule) は、ある一連のプロセスが複数のステップから成り立っており、各ステップでの選択が他のステップの選択肢の数に影響を与えない場合に、全体の総数を求めるための基本法則です。

【定義】

事柄Aの起こり方が \(m\) 通りあり、その各々の場合に対して、事柄Bの起こり方が \(n\) 通りあるとき、AとBがともに起こる場合の数は、\(m \times n\) 通りである。

この法則の核心は「その各々の場合に対して」という部分にあります。これは、最初のステップでどの選択肢（\(m\) 通りのうちの1つ）を選んだとしても、次のステップで選べる選択肢の数（\(n\) 通り）は常に変わらない、ということを意味します。思考のイメージとしては、最初の選択から枝が \(m\) 本伸び、その各々の枝の先からさらに \(n\) 本の枝が伸びていく**樹形図（決定木）**を想像すると分かりやすいでしょう。最終的な場合の総数は、この樹形図の末端の枝の総数に等しく、それは掛け算によって計算できます。

具体例1：コーディネートの選択

シャツを5種類、ズボンを3種類、靴を2種類持っているとします。これらを1種類ずつ選んで身につけるとき、コーディネートは全部で何通り作れるでしょうか。

この問題は、「シャツを選ぶ」「ズボンを選ぶ」「靴を選ぶ」という3つのステップからなる一連のプロセスと考えることができます。

  • ステップ1: シャツを選ぶ（5通り）
  • ステップ2: ズボンを選ぶ（3通り）
  • ステップ3: 靴を選ぶ（2通り）

ここで重要なのは、どのシャツを選んだとしても、選べるズボンの種類は常に3通りであり、どのシャツとズボンを選んだとしても、選べる靴の種類は常に2通りである、という点です。したがって、積の法則を適用できます。

求めるコーディネートの総数は、\(5 \times 3 \times 2 = 30\) 通りとなります。

これは、5本の枝からなる木があり、それぞれの枝から3本の小枝が伸び、さらにその先の各小枝から2本の葉が出ている様子を想像するのと同じです。葉の総数が30枚になる、というわけです。

積の法則の適用を見抜くための思考のポイント

  • 「〜し、そして〜する」「〜して、次に〜する」 といった、一連の連続した動作やステップとして問題を捉えられる場合、積の法則が適用できる可能性が高いです。
  • 樹形図 を描いたときに、各階層での枝分かれの数が一定である状況を想像できれば、それは積の法則の世界です。
  • 問題を複数の独立した選択のステップに分解し、それぞれのステップの選択肢の数を掛け合わせる、という思考プロセスが有効です。

具体例2：約数の個数

自然数 72 の正の約数は全部で何個あるでしょうか。

この問題を解く鍵は、素因数分解です。

\(72 = 2^3 \times 3^2\)

72の正の約数は、必ず \(2^a \times 3^b\) の形で表せます。ここで、\(a\) と \(b\) が取りうる値の範囲を考えます。

  • 素因数2の指数 \(a\) は、\(2^0, 2^1, 2^2, 2^3\) のいずれかなので、\(a\) の選び方は 0, 1, 2, 3 の4通りです。
  • 素因数3の指数 \(b\) は、\(3^0, 3^1, 3^2\) のいずれかなので、\(b\) の選び方は 0, 1, 2 の3通りです。

約数を一つ作ることは、「2の指数 \(a\) を選ぶ」というステップと、「3の指数 \(b\) を選ぶ」というステップを連続して行うプロセスと見なせます。\(a\) の選び方（4通り）の各々に対して、\(b\) の選び方（3通り）が考えられるため、積の法則が適用できます。

したがって、72の正の約数の個数は、\(4 \times 3 = 12\) 個となります。

この問題は、一見すると積の法則と結びつきにくいかもしれませんが、問題を「独立した選択肢の組み合わせ」として再構成することで、積の法則が強力なツールとなることを見事に示しています。

1.3. 法則の戦略的選択：和と積の使い分け

場合の数の問題を解く際には、和の法則と積の法則が複雑に組み合わさって現れることがほとんどです。問題を解くプロセスは、しばしば、大きな問題を和の法則によって排反なケースに分割（場合分け）し、分割された各ケースの内部を積の法則によって計算し、最後に和の法則によってそれらの結果を合計する、という階層的な構造を取ります。

思考のフレームワーク

  1. 全体像の把握: 問題が何を求めているのかを正確に理解する。
  2. 分割（和の法則）: 全体を、互いに重複しない（排反な）いくつかの大きなカテゴリやケースに分類できないか検討する。「〜の場合」「〜でない場合」や「〜が1個の場合」「〜が2個の場合」といった場合分けがこれにあたります。
  3. 分析（積の法則）: 分割された各ケースの内部で、事象が一連のステップとして考えられないか検討する。各ステップでの選択肢の数を数え、それらを掛け合わせる。
  4. 統合（和の法則）: 各ケースで計算した結果を、最後に足し合わせる。

具体例：3桁の奇数

0, 1, 2, 3, 4, 5 の6個の数字から、異なる3個の数字を選んで3桁の整数を作るとき、奇数は何個作れるか。

この問題は、まず「奇数である」という条件に着目し、それを満たすための構造を考えます。

ステップ1：構造の分析

3桁の整数が奇数であるための条件は、「一の位が奇数である」ことです。

使用できる数字の中で、奇数は 1, 3, 5 の3つです。

ここから、一の位の数字によって場合分けを行う、という和の法則の視点が生まれます。しかし、この問題では、どの奇数を一の位に選んでも、その後の百の位と十の位の選び方のプロセスは同じ構造を持つため、より効率的な積の法則の視点、つまり「位を決定するステップ」として問題を分解する方法が有効です。

ステップ2：積の法則による思考

3桁の整数を作るというプロセスを、以下の3つのステップに分解します。

  • ステップA: 一の位を決める
  • ステップB: 百の位を決める
  • ステップC: 十の位を決める

ただし、これらのステップには制約条件が絡むため、制約の強い場所から先に決定するのが定石です。

  1. 一の位の決定:奇数でなければならないため、候補は 1, 3, 5 の3通りです。
  2. 百の位の決定:3桁の整数であるため、百の位は 0 であってはなりません。また、一の位で使った数字も使えません。
    • もし一の位で 1 を使ったとすると、百の位で使えるのは {0, 2, 3, 4, 5} から 0 を除いた {2, 3, 4, 5} の4通りです。
    • もし一の位で 3 を使ったとしても、百の位で使えるのは {0, 1, 2, 4, 5} から 0 を除いた {1, 2, 4, 5} の4通りです。このように、一の位でどの奇数を選んだとしても、百の位の選択肢は常に4通りであることが分かります。
  3. 十の位の決定:一の位と百の位で使った2つの数字以外なら、どれでも使えます。0も使用可能です。全部で6個の数字から2個を使ったので、残りは \(6 – 2 = 4\) 個。したがって、十の位の選択肢は4通りです。

ステップ3：計算

各ステップの選択肢の数が確定しました。

  • 一の位：3通り
  • 百の位：4通り
  • 十の位：4通り

これらは一連のプロセスなので、積の法則を適用します。

求める奇数の個数は、\(3 \times 4 \times 4 = 48\) 個となります。

この例題のように、問題を解く際には、まず積の法則の視点で「一連のステップ」に分解できないかを考え、その過程で「もし〜だったら」と選択肢の数が変わってしまうようなら、そこで初めて和の法則による「場合分け」を検討する、という思考の流れが極めて有効です。

和の法則と積の法則は、単なる足し算と掛け算ではありません。それらは、複雑な事象を構造化し、論理的に整理するための二つの基本的な思考ツールなのです。この二つの法則を自在に操れるようになったとき、場合の数の世界の扉は、あなたの前に大きく開かれることでしょう。

2. 順列 (nPr) の定義と計算

和の法則と積の法則という二大原理を手に、我々は次なるステップへと進みます。それは、場合の数の分野で中心的な役割を果たす「順列」です。順列とは、単に要素を選ぶだけでなく、その並び順までを考慮に入れる考え方です。この「順序を区別する」という視点が、場合の数の世界をより豊かで精密なものにします。ここでは、順列の厳密な定義から、その計算方法を積の法則とどう結びつけるかまでを深く探求していきます。

2.1. 順列 (Permutation) とは何か

順列 (Permutation) とは、いくつかの異なるものの中から、特定個数を取り出して一列に並べるときの、その並べ方の総数を指します。英語の “Permutation” は、ラテン語で「完全な変更」や「交換」を意味する言葉に由来しており、要素の配置を入れ替えるというニュアンスをよく表しています。

順列の核心的な特徴は、以下の二点に集約されます。

  1. 異なるものから選ぶ: 大前提として、並べる元となる要素は、すべて互いに区別できるものである必要があります。
  2. 順序を考慮する: 選んだ要素をどのような順番で並べるかを区別します。例えば、AとBを選んで並べる場合、「A, B」という並びと「B, A」という並びは、異なる2通りの順列として数えます。

この「順序を考慮する」という点が、後に学ぶ「組合せ（Combination）」との決定的な違いとなります。組合せでは、単にどの要素が選ばれたかという「メンバー構成」のみが問題となり、並び順は問いません。

記号 \(nPr\) の導入

異なる \(n\) 個のものから \(r\) 個を取り出して並べる順列の総数は、記号 \(_n\mathrm{P}_r\) または \(P(n, r)\) と表されます。

この P は Permutation の頭文字です。

  • \(n\): 並べる元の総数（Number）
  • \(r\): 取り出して並べる個数（Number to arrange）

\(nPr\) と書かれたとき、それは「n個の区別できるアイテムのストックから、r個のアイテムを選び出し、r個の空のスロットに一列に配置する方法は何通りあるか？」という問いを数学的に表現したものだと理解してください。当然、取り出す個数 \(r\) は元の総数 \(n\) を超えることはできず（\(1 \le r \le n\)）、\(n\) と \(r\) は自然数です。

具体例で見る順列

4人の生徒（A, B, C, D）の中から、3人を選んで一列に並ばせ、リレーの走者（第1走者、第2走者、第3走者）を決めるとします。この場合の総数は、\(_4\mathrm{P}_3\) と表されます。

実際に書き出してみましょう。

  • (A, B, C), (A, C, B)
  • (A, B, D), (A, D, B)
  • (A, C, D), (A, D, C)
  • (B, C, D), (B, D, C)
  • … など

(A, B, C) は、第1走者がA, 第2走者がB, 第3走者がCであることを意味します。

(A, C, B) は、第1走者がA, 第2走者がC, 第3走者がBであることを意味します。

選ばれたメンバーは同じ {A, B, C} ですが、走る順番が異なるため、これらは順列としては明確に区別される2通りです。

2.2. 積の法則からの導出

では、\(_n\mathrm{P}_r\) は具体的にどのように計算すればよいのでしょうか。ここで、前のセクションで学んだ「積の法則」がその力を発揮します。\(n\) 個の異なるものから \(r\) 個を取り出して一列に並べるというプロセスを、\(r\) 個のステップに分解して考えてみましょう。

\(r\) 個の空の箱が一列に並んでいると想像してください。

[ 1番目 ] [ 2番目 ] [ 3番目 ] … [ r番目 ]

この箱に、\(n\) 個の異なるボールを入れていくと考えます。

  • ステップ1：1番目の箱に入れるボールを選ぶ\(n\) 個のボールの中からどれでも選べるので、選択肢は \(n\) 通りです。
  • ステップ2：2番目の箱に入れるボールを選ぶ1番目の箱には既に1つのボールが入っているので、残りのボールは \(n-1\) 個です。したがって、選択肢は \((n-1)\) 通りです。
  • ステップ3：3番目の箱に入れるボールを選ぶ1番目と2番目の箱にボールが1つずつ入っているので、残りのボールは \(n-2\) 個です。したがって、選択肢は \((n-2)\) 通りです。

このプロセスを、\(r\) 番目の箱まで続けます。

  • ステップ \(k\) 番目 (\(1 \le k \le r\))\(k-1\) 番目までの箱にボールが入っているので、使われたボールは \(k-1\) 個です。残っているボールは \(n – (k-1)\) 個。したがって、選択肢は \((n – k + 1)\) 通りです。
  • ステップ \(r\) 番目（最後のステップ）\(r-1\) 個のボールが既に使用されているので、残りは \(n-(r-1) = n-r+1\) 個です。したがって、最後の箱に入れるボールの選択肢は \((n-r+1)\) 通りです。

この一連のプロセスは、まさに積の法則が適用できる典型的な状況です。したがって、\(_n\mathrm{P}_r\) の総数は、これらのステップの選択肢の数をすべて掛け合わせることで得られます。

【\(_n\mathrm{P}_r\) の計算式】

\[_n\mathrm{P}_r = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1)\]

この式は、「\(n\) から始めて、1ずつ減らしながら、\(r\) 個の数を掛け合わせる」と覚えると実用的です。

具体例の計算

先ほどの4人の生徒から3人を選んでリレーの走者を決める問題（\(_4\mathrm{P}_3\)）を計算してみましょう。

\(n=4, r=3\) ですから、

\(_4\mathrm{P}_3 = 4 \times (4-1) \times (4-2) = 4 \times 3 \times 2\)

\(4\) から始めて、3個の数を掛け合わせます。

\(_4\mathrm{P}_3 = 4 \times 3 \times 2 = 24\)

したがって、リレーの走者の決め方は 24通り あることが分かります。

別の具体例：会員番号の作成

1から9までの9個の数字から、異なる4個の数字を使って4桁の会員番号を作成します。何通りの会員番号が作成できるでしょうか。

これは、9個の異なる数字から4個を取り出して一列に並べる順列そのものです。

したがって、求める場合の数は \(_9\mathrm{P}_4\) となります。

\(n=9, r=4\) ですから、9から始めて4個の数を掛け合わせます。

\(_9\mathrm{P}_4 = 9 \times 8 \times 7 \times 6 = 3024\)

よって、3024通り の会員番号が作成できます。

2.3. 順列計算の実践と注意点

順列の計算自体は単純な掛け算ですが、問題を正しく順列の問題として認識することが重要です。

順列としてモデル化できる問題のキーワード

  • 「一列に並べる」「整列させる」
  • 「順位をつける」「役職を割り当てる」（会長、副会長、書記など、役職が区別される場合）
  • 「（異なる数字や文字を使って）〜桁の整数（文字列）を作る」
  • 「席に座らせる」（座席が区別される場合）

これらのキーワードが出てきた場合、それは「順序」が重要であることを示唆しており、順列の考え方が適用できる可能性が高いです。

注意点：\(r\) の個数の誤解

\(_n\mathrm{P}_r = n \times (n-1) \times \cdots \times (n-r+1)\) の最後の項は \((n-r)\) ではないことに注意してください。掛け合わせる数の個数が \(r\) 個であることを意識するのが最も確実です。

例えば \(_7\mathrm{P}_3\) であれば、\(7, 6, 5\) の3個を掛けるので \(7 \times 6 \times 5 = 210\) となります。最後の項は \(5 = 7-3+1\) となっており、公式と一致します。

ミニケーススタディ：順列か、それ以外か？

問題A: 10人のクラスから、学級委員長、副委員長、書記を1人ずつ選出する方法は何通りか。ただし、兼任は認めない。

思考プロセス:

  1. 選ばれる役職（委員長、副委員長、書記）は、互いに区別されるか？ → YES。A君が委員長でB君が副委員長の場合と、B君が委員長でA君が副委員長の場合は、明確に異なる結果である。
  2. これは「順序」を考慮していると言えるか？ → YES。「委員長の席」「副委員長の席」「書記の席」という3つの異なるポジションに、10人の中から3人を配置する問題と見なせる。
  3. したがって、これは10個の異なるものから3個を取り出して並べる順列である。解法: \(_10\mathrm{P}_3 = 10 \times 9 \times 8 = 720\) 通り。

問題B: 10人のクラスから、掃除当番を3人選出する方法は何通りか。

思考プロセス:

  1. 選ばれる立場（掃除当番）は、互いに区別されるか？ → NO。A君, B君, C君が選ばれることと、B君, A君, C君が選ばれることは、最終的な当番のメンバー構成としては全く同じである。
  2. これは「順序」を考慮していない。
  3. したがって、これは順列の問題ではない。（これは後に学ぶ「組合せ」の問題となる。）

このように、問題の状況が「順序」を区別すべきものかどうかを慎重に吟味することが、適切な解法を選択するための第一歩となります。順列の概念は、この「順序の区別」という一点において、その本質的な特徴を持っているのです。次のセクションでは、この順列の計算をより洗練された形で表現するための「階乗」という概念を導入します。

3. 階乗 (n!) の概念

順列 \(_n\mathrm{P}_r\) の計算に慣れてくると、特に \(r=n\) という特殊なケース、つまり「\(n\) 個の異なるものすべてを一列に並べる」という状況が頻繁に現れることに気づきます。この非常に基本的で重要な操作を簡潔に表現するために、数学では「階乗」という特別な記号を用います。階乗は、順列だけでなく、組合せや確率、さらには解析学などのより高度な数学分野においても頻繁に登場する、極めて基本的な概念です。

3.1. 階乗 (Factorial) の定義

階乗 (Factorial) とは、1からある正の整数 \(n\) までのすべての整数を掛け合わせた積のことです。記号では \(n!\) と表し、「nの階乗」と読みます。

【定義】

\(n\) を正の整数とするとき、

\[

n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1

\]

と定義される。

具体例

  • \(1! = 1\)
  • \(2! = 2 \times 1 = 2\)
  • \(3! = 3 \times 2 \times 1 = 6\)
  • \(4! = 4 \times 3 \times 2 \times 1 = 24\)
  • \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
  • \(6! = 6 \times 5! = 6 \times 120 = 720\)
  • \(7! = 7 \times 6! = 7 \times 720 = 5040\)

階乗の値は、\(n\) が大きくなるにつれて急速に増大するという特徴があります。

階乗と順列の関係

階乗の定義は、まさに「\(n\) 個の異なるものから \(n\) 個すべてを取り出して一列に並べる順列」の総数、すなわち \(_n\mathrm{P}_n\) の計算式そのものです。

\(_n\mathrm{P}_n = n \times (n-1) \times \cdots \times (n-n+1) = n \times (n-1) \times \cdots \times 1 = n!\)

したがって、以下の関係が成り立ちます。

\[

_n\mathrm{P}_n = n!

\]

例えば、A, B, C, D の4文字をすべて使って作られる文字列の総数は、

\(_4\mathrm{P}_4 = 4! = 4 \times 3 \times 2 \times 1 = 24\) 通りとなります。

この関係は非常に重要です。\(n\) 個のものの並べ方の総数が \(n!\) であるという事実は、今後の様々な問題で基本的な構成要素として利用されます。

3.2. 0の階乗 (0!) の謎

階乗は正の整数 \(n\) について定義されましたが、数学の様々な場面で、便宜上 0の階乗 (\(0!\)) を定義する必要が生じます。結論から言うと、\(0!\) は 1 と定義されます。

\[

0! = 1

\]

これはなぜでしょうか。多くの初学者が疑問に思う点ですが、いくつかの観点からこの定義の妥当性を説明することができます。

説明1：整合性のための定義（順列の公式からのアプローチ）

順列 \(_n\mathrm{P}_r\) の計算式を、階乗を用いて書き換えることを考えてみましょう。

\(_n\mathrm{P}_r = n \times (n-1) \times \cdots \times (n-r+1)\)

この式の右辺に、\((n-r) \times \cdots \times 1\) 、すなわち \((n-r)!\) を掛けて、同時に割ってみます。

\[

_n\mathrm{P}_r = \frac{n \times (n-1) \times \cdots \times (n-r+1) \times (n-r) \times \cdots \times 1}{(n-r) \times \cdots \times 1}

\]

すると、分子は \(n!\)、分母は \((n-r)!\) となるため、以下の美しい式が得られます。

【順列の階乗による表現】

\[

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

\]

この式は、順列の計算を非常にエレガントに表現しており、様々な証明などにも利用されます。

さて、この式が \(r=n\) の場合にも成り立つと考えてみましょう。

\(_n\mathrm{P}_n = n!\) でしたから、

\(n! = \frac{n!}{(n-n)!} = \frac{n!}{0!}\)

この等式が成り立つためには、分母の \(0!\) が1でなければなりません。

\(n! = \frac{n!}{1}\)

このように、\(_n\mathrm{P}_r\) の階乗表現の式が、\(r=n\) という境界のケースでも矛盾なく成り立つようにするために、\(0!=1\) と定めるのが数学的に自然である、と考えることができます。

説明2：空集合からのアプローチ

場合の数の文脈では、「\(n!\) は \(n\) 個のものを並べる方法の数」と解釈されます。

では、「0個のものを並べる方法」は何通りでしょうか。

これは直感的には奇妙に聞こえますが、「何もしない」という一通りの方法が存在すると考えることができます。

何もない空間に、何もないものを並べる方法は、ただその「何もない状態」そのものが一通りある、という解釈です。これは数学における「空集合の順列は1通り」という考え方に対応します。

説明3：再帰的な定義からのアプローチ

階乗には、\(n! = n \times (n-1)!\) という関係があります。例えば、\(5! = 5 \times 4!\) です。

この関係式を \(n=1\) の場合に適用してみましょう。

\(1! = 1 \times (1-1)! = 1 \times 0!\)

\(1! = 1\) ですから、\(1 = 1 \times 0!\) となります。この式が成り立つためには、やはり \(0!=1\) である必要があります。

これらの理由から、\(0!=1\) という定義は、単なる気まぐれな約束事ではなく、数学体系全体の整合性を保つために不可欠な、論理的な帰結なのです。

3.3. 階乗を用いた計算の実践

階乗の記号を導入したことで、順列の計算がより簡潔に、そして構造的に表現できるようになります。

例題1：\(_7\mathrm{P}_3\) を階乗で計算する

\(n=7, r=3\) ですから、\((n-r) = 4\) です。

\[

_7\mathrm{P}_3 = \frac{7!}{(7-3)!} = \frac{7!}{4!}

\]

これを計算する際、\(7!\) や \(4!\) の値をすべて計算する必要はありません。約分を利用します。

\[

\frac{7!}{4!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1} = 7 \times 6 \times 5 = 210

\]

これは、\(n\) から \(r\) 個を掛けるという元の計算方法と結果が一致していることを確認できます。階乗による表現は、特に文字式を含む証明問題などでその威力を発揮します。

例題2：特定の並び方

男子4人、女子3人が一列に並ぶとき、女子3人が続いて並ぶような並び方は何通りあるか。

この問題は、後のセクション「条件付き順列」で詳しく扱いますが、階乗の概念を使って解くことができます。

思考プロセス:

  1. 「ひとかたまり」と見なす: 女子3人を一つのグループとして、まるで一人の大きな人物のように考えます。これを「W」というブロックとします。
  2. 全体の並びを考える: すると、問題は「男子4人（M1, M2, M3, M4）と女子ブロックWの計5つのものを一列に並べる」ことと等価になります。この5つのものの並べ方は \(5!\) 通りです。例: M1, M2, W, M3, M4
  3. 内部の並びを考える: 次に、女子ブロックWの内部に注目します。このブロックの中では、女子3人が自由に並ぶことができます。女子3人の並べ方は \(3!\) 通りです。例: W = (女1, 女2, 女3), (女1, 女3, 女2), …

計算:

全体の並び（ステップ2）の各々の場合に対して、女子ブロック内部の並び（ステップ3）が存在します。これは積の法則が適用できる状況です。

したがって、求める場合の数は、

\(5! \times 3! = (5 \times 4 \times 3 \times 2 \times 1) \times (3 \times 2 \times 1) = 120 \times 6 = 720\)

答えは 720通り となります。

このように、階乗は単なる計算記号ではなく、「\(n\) 個のものを並べるパターン数」という具体的な意味を持つ構成単位（ビルディングブロック）として機能します。複雑な順列の問題も、この階乗というブロックを組み合わせることで、見通しよく解けるようになるのです。

4. 円順列

これまで我々が考えてきた順列は、人や物を「一列に」並べる、いわゆる線順列 (Linear Permutation) でした。そこには明確な「先頭」と「最後尾」が存在し、すべての位置は絶対的なものとして区別されていました。しかし、世の中の配置は直線的なものばかりではありません。円卓を囲んで座る、ビーズを繋いでネックレスを作るなど、円形に物を配置する状況も数多く存在します。このような円形の配置を数え上げるのが円順列 (Circular Permutation) です。円順列の考え方の核心は、「回転して同じになるものは、1通りと見なす」という点にあります。

4.1. 円順列の基本的な考え方

\(n\) 個の異なるものを円形に並べる場合の数を考えてみましょう。

まずは、4人（A, B, C, D）が円卓に座る場合を例に取ります。

誤ったアプローチ：単純な線順列

もし、これを単に4人が一列に並ぶ問題だと考えると、その総数は \(_4\mathrm{P}_4 = 4! = 24\) 通りとなります。しかし、円卓では状況が異なります。

例えば、一列に並んだ以下の4つの順列を考えてみましょう。

  1. (A, B, C, D)
  2. (B, C, D, A)
  3. (C, D, A, B)
  4. (D, A, B, C)

これらを円卓に配置すると、どうなるでしょうか。

[図：(A,B,C,D), (B,C,D,A), (C,D,A,B), (D,A,B,C)をそれぞれ円形に配置した図。すべて同じ配置になることを示す]

驚くべきことに、これら4つの異なる線順列は、円卓に配置すると、すべて全く同じ配置になってしまいます。(1)を時計回りに90度回転させると(2)に、さらに90度回転させると(3)になり、というように、すべて回転によって移り変わることができます。円順列では、このような回転して重なるものは同一の並び方として扱います。

重複の構造

線順列で考えると、1つの円順列に対して、それをどこから読み始めるか（誰を先頭と見なすか）の数だけ、重複して数え上げていることが分かります。

上記の例では、1つの円卓の配置（例：Aの右隣がB, Bの右隣がC, …）に対して、

  • Aを先頭と見なした線順列 (A, B, C, D)
  • Bを先頭と見なした線順列 (B, C, D, A)
  • Cを先頭と見なした線順列 (C, D, A, B)
  • Dを先頭と見なした線順列 (D, A, B, C)という、4つの異なる線順列が対応してしまっています。これは、他のどのような円卓の配置についても同様です。つまり、線順列の総数 \(4!\) は、円順列の総数を4倍に過剰カウントしているのです。

したがって、正しい円順列の総数を求めるには、線順列の総数を重複度（この場合は4）で割ればよい、という発想に至ります。

【円順列の公式（導出1：割り算）】

異なる \(n\) 個のものを円形に並べる円順列の総数は、

\[

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

\]

この公式によれば、4人の円順列の総数は、\((4-1)! = 3! = 6\) 通りとなります。

4.2. 「固定」による考え方

円順列を求めるためのもう一つの、そしてより直感的で応用範囲の広い考え方が、「1つの要素を固定して考える」という方法です。

なぜ回転すると同じ並びが生まれてしまうのでしょうか。それは、円には絶対的な基準となる「位置」がないからです。どこが「1番目の席」であるという区別がありません。

そこで、この問題を解決するために、我々は人為的に基準点を作ってしまいます。

思考プロセス

  1. 1人を特定の位置に固定する:\(n\) 人のうち、特定の1人（例えばAさん）を選び、円卓のある特定の席に座らせてしまいます。このAさんは、これから並び方を数える上での「基準点」となります。Aさんを固定するこの操作自体は、場合の数を数える上では1通りと見なします（なぜなら、どこの席に固定しても回転すれば同じだからです）。[図：円卓の一番上の席にAを座らせる]
  2. 残りの人々を線順列として考える:Aさんが1つの席に固定されたことで、残りの \(n-1\) 個の席には、「Aさんの右隣の席」「Aさんの右隣の右隣の席」…「Aさんの左隣の席」というように、すべて区別がつくようになります。もはや、この配置を回転させることはできません。なぜなら、回転させると基準であるAさんの位置が変わってしまうからです。[図：Aが固定された円卓の、残りの3つの席に番号(1,2,3)を振る]
  3. 残りの人々の並びを計算する:したがって、問題は「残った \(n-1\) 人を、区別できる \(n-1\) 個の席に並べる」という、単純な線順列の問題に帰着します。その総数は、\((n-1)!\) 通りです。

【円順列の公式（導出2：固定法）】

異なる \(n\) 個のものを円形に並べる円順列の総数は、

\[

(n-1)!

\]

この「固定法」は、単に公式を覚える以上に、円順列の本質、すなわち「基準を設けることで回転による重複をなくす」という考え方を体現しており、より複雑な問題に応用する際に非常に強力な武器となります。

具体例：役員会

6人の役員が円卓を囲んで会議をします。座り方は何通りあるでしょうか。

これは、異なる6人の円順列の問題です。

  • 割り算法: \(\frac{6!}{6} = 5! = 120\) 通り。
  • 固定法: 役員のうち1人（例えばAさん）を固定する。残りの5人を残りの5つの席に並べる方法なので、\(5! = 120\) 通り。

どちらの考え方でも、答えは 120通り となります。

4.3. 応用：じゅず順列（ネックレス順列）

円順列の考え方をさらに一歩進めたものに、**じゅず順列（ネックレス順列）**があります。これは、円形に並べたものを、裏返す（ひっくり返す）ことができる場合、裏返して同じになるものも同一と見なす順列です。

円卓の座席は裏返せませんが、ビーズを糸でつないで作ったネックレスは、机の上でひっくり返すことができます。

考え方

  1. まず円順列を考える:異なる \(n\) 個のビーズで作る円順列の総数は、\((n-1)!\) 通りです。
  2. 裏返して重なるものを検討する:これらの \((n-1)!\) 通りの円順列のうち、ほとんどのものは、裏返すと別の円順列になります。例えば、(A, B, C, D) という時計回りの円順列は、裏返すと (A, D, C, B) という時計回りの円順列（つまり、反時計回りに(A,B,C,D)と並んだもの）になり、これらは元の円順列とは区別されます。[図：(A,B,C,D)の円順列と、それを裏返した(A,D,C,B)の円順列を示す]つまり、裏返すことのできない円順列の世界では別々に数えられていた2つのものが、じゅず順列の世界ではペアになって「1通り」と見なされることになります。したがって、基本的には、円順列の総数を2で割れば、じゅず順列の総数が得られると考えられます。

【じゅず順列の公式（基本）】

異なる \(n\) 個のもので作られるじゅず順列の総数は、

\[

\frac{(n-1)!}{2} \quad (n \ge 3)

\]

注意点：左右対称な配置

ただし、この「2で割る」という操作には注意が必要です。円順列の中には、裏返しても全く同じ配置になるもの、つまり左右対称な配置が存在する場合があります。

このような配置は、もともとペアを作る相手がおらず、単独で存在しています。したがって、すべての円順列を単純に2で割ってしまうと、数え方がおかしくなってしまいます。

厳密には、

  1. 左右非対称な円順列の数を数え、それを2で割る。
  2. 左右対称な円順列の数を数える。
  3. 1と2の結果を足し合わせる。という手順が必要になります。しかし、高校数学の範囲では、多くの場合、単純に \(\frac{(n-1)!}{2}\) で計算できる問題が出題されるか、あるいは \(n\) の値が小さく、具体的に書き出して対称なものを確認できる問題がほとんどです。

具体例：ビーズのブレスレット

異なる5色のビーズを糸に通してブレスレットを作るとき、何通りの作り方があるか。

これは5個のじゅず順列です。

  1. まず、5色のビーズの円順列の総数を求めます。\((5-1)! = 4! = 24\) 通り。
  2. 5個の要素で左右対称な配置は存在しません（厳密な証明は難しいですが、奇数個の場合は比較的対称になりにくいです）。したがって、この24通りは、すべて裏返すと異なる並びになる12組のペアから成ると考えられます。
  3. じゅず順列の総数は、円順列の総数を2で割ります。\(\frac{24}{2} = 12\) 通り。

答えは 12通り となります。

円順列はじゅず順列は、単なる公式の適用に留まらず、「何を同一と見なすか」という同値関係の考え方を学ぶ上で非常に重要です。問題の条件（回転のみを同一視するのか、裏返しも同一視するのか）を正確に読み取り、適切な思考モデルを選択する訓練を積むことが大切です。

5. 重複順列

これまでの順列では、「異なる \(n\) 個のものから」という大前提がありました。一度使ったものは、二度と使えませんでした。しかし、現実の世界では、同じものを繰り返し使うことが許される状況が数多く存在します。例えば、数字を繰り返し使って良い電話番号、同じ文字を何度も使えるパスワードなどがその典型です。このように、繰り返しを許して一列に並べる順列を重複順列 (Permutation with Repetition) と呼びます。

5.1. 重複順列の概念と計算

重複順列とは、\(n\) 種類のものから、重複を許して \(r\) 個を取り出し、一列に並べる順列のことです。

通常の順列 \(_n\mathrm{P}_r\) との違いは、「重複を許す」という一点のみです。この条件緩和が、計算方法に決定的な違いをもたらします。

計算方法の導出（積の法則）

重複順列の総数を求めるのは、実は通常の順列よりも単純です。ここでも積の法則が活躍します。

\(n\) 種類のものから重複を許して \(r\) 個を取り出し、一列に並べるプロセスを考えてみましょう。

\(r\) 個の空の箱が並んでいるとします。

[ 1番目 ] [ 2番目 ] [ 3番目 ] ... [ r番目 ]

  • ステップ1：1番目の箱に入れるものを選ぶ\(n\) 種類の中からどれでも選べるので、選択肢は \(n\) 通りです。
  • ステップ2：2番目の箱に入れるものを選ぶここが重要なポイントです。 重複を許すので、1番目で何を選んだかに関わらず、2番目でも再び \(n\) 種類すべての中から選ぶことができます。したがって、選択肢は \(n\) 通りです。
  • ステップ3：3番目の箱に入れるものを選ぶ同様に、ここでも選択肢は \(n\) 通りです。

このプロセスを \(r\) 番目の箱まで続けます。

どのステップにおいても、常に \(n\) 通りの選択肢が存在します。

  • ステップ \(r\) 番目（最後のステップ）やはり選択肢は \(n\) 通りです。

この一連のプロセスは積の法則そのものです。\(n\) を \(r\) 回掛け合わせることになります。

【重複順列の公式】

\(n\) 種類のものから重複を許して \(r\) 個を取り出して並べる重複順列の総数は、

\[

n^r

\]

と表されます。重複順列の総数を表す特別な記号として \(_n\Pi_r\) が使われることもありますが、\(n^r\) の方が一般的で直感的です。

具体例1：3桁の番号

1, 2, 3, 4 の4つの数字を使い、重複を許して3桁の番号を作るとき、何通りの番号が作れるか。

これは、4種類のものから重複を許して3個を取り出し、一列に並べる重複順列です。

\(n=4, r=3\) です。

  • 百の位の選び方：4通り
  • 十の位の選び方：4通り
  • 一の位の選び方：4通り

したがって、積の法則により、\(4 \times 4 \times 4 = 4^3 = 64\) 通りとなります。

具体例2：じゃんけん

5人が1回じゃんけんをするとき、手の出し方は全部で何通りあるか。ただし、誰がどの手を出したかを区別するものとします。

これは、5人の人物（A, B, C, D, E）が、それぞれ「グー、チョキ、パー」の3種類の手の中から1つを選ぶ、と考えることができます。

  • Aさんの手の出し方：3通り
  • Bさんの手の出し方：3通り
  • Cさんの手の出し方：3通り
  • Dさんの手の出し方：3通り
  • Eさんの手の出し方：3通り

各人の手の出し方は独立しています。Aさんがグーを出したからといって、Bさんが出せる手に制約はありません。これは、3種類の手 {グー, チョキ, パー} から重複を許して5個を取り、5人の人に割り当てる（並べる）重複順列と見なすことができます。

\(n=3, r=5\) です。

したがって、手の出し方の総数は、\(3 \times 3 \times 3 \times 3 \times 3 = 3^5 = 243\) 通りとなります。

注意：「nとrは何か」を明確に

重複順列の問題で最も混乱しやすいのは、\(n^r\) の \(n\) と \(r\) にどの数字を当てはめるか、という点です。

上のじゃんけんの例で、これを \(5^3\) と間違えてしまうケースがよくあります。

見極めるための思考法

  • 「選ばれる側」「繰り返し使える側」が \(n\) になる。じゃんけんの例では、{グー, チョキ, パー} が「繰り返し使える選択肢」です。これが \(n=3\) です。
  • 「選ぶ側」「場所」「ポジション」が \(r\) になる。じゃんけんの例では、5人の人が「手を選ぶ側」です。5つのポジションに手が入ると考えられます。これが \(r=5\) です。

この関係を常に意識することで、\(n\) と \(r\) の混同を防ぐことができます。

5.2. 重複順列の多様なモデル

重複順列の概念は、一見するとそうは見えない様々な問題の背景に潜んでいます。いくつかの典型的なモデルを理解することで、応用力が飛躍的に向上します。

モデル1：集合の要素の割り当て

\(r\) 個の区別できるボールを、\(n\) 個の区別できる箱に自由に入れる方法。ただし、空の箱があってもよい。

思考プロセス

1つ1つのボールの視点に立って考えます。

  • 1個目のボール: どの箱に入れるか？ \(n\) 個の箱から選べるので、\(n\) 通りの選択肢があります。
  • 2個目のボール: どの箱に入れるか？ これも同様に \(n\) 通りの選択肢があります。
  • …
  • \(r\) 個目のボール: やはり \(n\) 通りの選択肢があります。

ボール1からボールrまでの選択は一連のプロセスなので、積の法則を適用します。

総数は、\(n \times n \times \cdots \times n\) (\(r\) 回) = \(n^r\) 通りとなります。

これは、「繰り返し使える選択肢（箱）」が \(n\)、「選択する側（ボール）」が \(r\) という、重複順列の構造そのものです。

具体例：部屋割り

3人の旅行者を、A, Bの2つの部屋に割り当てる方法は何通りあるか。ただし、全員が同じ部屋に入ってもよい。

  • 繰り返し使える選択肢（箱）：部屋A, 部屋B の \(n=2\) 種類
  • 選択する側（ボール）：旅行者1, 旅行者2, 旅行者3 の \(r=3\) 人

したがって、総数は \(2^3 = 8\) 通りです。

モデル2：部分集合の個数

要素数が \(n\) である集合の部分集合は、全部で何個あるか。

思考プロセス

集合を \(A = {a_1, a_2, \cdots, a_n}\) とします。

部分集合を1つ作るということを、各要素 \(a_i\) に対して、「その部分集合に含めるか、含めないか」の2択を決定していくプロセスと考えます。

  • 要素 \(a_1\) の選択：含める / 含めない の 2通り
  • 要素 \(a_2\) の選択：含める / 含めない の 2通り
  • …
  • 要素 \(a_n\) の選択：含める / 含めない の 2通り

\(n\) 個の要素それぞれについて独立に2通りの選択ができるので、積の法則により、

部分集合の総数は、\(2 \times 2 \times \cdots \times 2\) (\(n\) 回) = \(2^n\) 個となります。

これは、2種類のもの {含める, 含めない} から、重複を許して \(n\) 個（\(n\) 個の要素の分だけ）を取り出して一列に並べる重複順列と解釈できます。

具体例

集合 {x, y, z} の部分集合の個数

要素数は3なので、\(2^3 = 8\) 個。

実際に書き出すと、∅, {x}, {y}, {z}, {x, y}, {y, z}, {z, x}, {x, y, z} の8個となり、一致します。

モデル3：二項対立の連続

コイントスを10回行うときの、表裏の出方の総数。

各回のコイントスは、「表」か「裏」の2択です。

1回目：2通り

2回目：2通り

…

10回目：2通り

したがって、総数は \(2^{10} = 1024\) 通りとなります。

これも、{表, 裏} の \(n=2\) 種類から、重複を許して \(r=10\) 回取り出す重複順列です。

重複順列は、その計算の単純さとは裏腹に、非常に広範な応用モデルを持つ強力なツールです。問題文の表面的な表現に惑わされず、その背後にある「繰り返し使える \(n\) 種類の選択肢から、\(r\) 回の選択を行う」という本質的な構造を見抜くことが、重複順列をマスターする鍵となります。

6. 同じものを含む順列

これまでの順列は、すべて「異なるもの」を並べることを前提としていました。しかし、SUCCESS のように同じ文字が含まれる単語のアナグラムや、赤玉3個と白玉2個を並べる問題など、現実には区別できない「同じもの」を含むケースが頻繁に登場します。このような場合、単純に \(n!\) を計算してしまうと、同じものを区別した場合の並べ方まで数えてしまうため、過剰なカウントが生じます。ここでは、その重複をいかにして合理的に解消し、正しい場合の数を導き出すかを探求します。

6.1. なぜ「割り算」が必要なのか

同じものを含む順列の基本的な考え方は、「一旦すべてを区別できるものとして並べ、その後で、区別をなくすことによって生じる重複分を割り算で消去する」というものです。

具体例からのアプローチ：aab の並べ替え

a, a, b の3文字を並べ替える方法を考えてみましょう。

もし、2つの a が区別できるもの、例えば \(a_1, a_2\) だと仮定します。

すると、並べる文字は \(a_1, a_2, b\) の3つの異なる文字となり、その順列の総数は \(3! = 6\) 通りです。

実際に書き出してみましょう。

  1. (\(a_1, a_2, b\))
  2. (\(a_2, a_1, b\))
  3. (\(a_1, b, a_2\))
  4. (\(a_2, b, a_1\))
  5. (\(b, a_1, a_2\))
  6. (\(b, a_2, a_1\))

さて、ここで \(a_1\) と \(a_2\) の区別をなくし、両方を単なる a に戻してみましょう。

  • (1)と(2)は、どちらも (a, a, b) となり、同じものになります。
  • (3)と(4)は、どちらも (a, b, a) となり、同じものになります。
  • (5)と(6)は、どちらも (b, a, a) となり、同じものになります。

なぜこのような重複が起こったのでしょうか。それは、元の \(a_1, a_2\) という2つの要素の内部での並べ替え（\(a_1, a_2\) と \(a_2, a_1\) の \(2! = 2\) 通り）を、我々が区別して数えてしまっていたからです。区別をなくすということは、この \(2!\) 通りの内部順列をすべて「1通り」と見なすことに他なりません。

したがって、\(3!\) 通りという過剰なカウントを修正するためには、この重複度である \(2!\) で割る必要があります。

正しい場合の数 = \(\frac{3!}{2!} = \frac{6}{2} = 3\) 通り。

実際に、(a, a, b), (a, b, a), (b, a, a) の3通りであり、計算結果と一致します。

一般化への道

この考え方を一般化してみましょう。

\(n\) 個のもののうち、\(p\) 個が同じもの、\(q\) 個が別の同じもの、\(r\) 個がさらに別の同じもの…である場合を考えます。（ただし、\(p+q+r+\cdots = n\)）

思考プロセス

  1. すべてを区別して並べる（仮定）:まず、\(n\) 個のものがすべて異なると仮定して、一列に並べます。その場合の数は \(n!\) 通りです。
  2. 重複度を考える:この \(n!\) 通りの中には、実際には同じ並びになるものが多数含まれています。
    • \(p\) 個の同じもの（例えば、\(p\) 個の a）は、仮定の世界では \(a_1, a_2, \dots, a_p\) として区別されていました。これらの内部での並べ替えは \(p!\) 通りあります。これらは実際にはすべて同じ並びなので、\(p!\) 通りを1通りと見なす必要があります。
    • 同様に、\(q\) 個の同じものの内部での並べ替えは \(q!\) 通りあります。
    • \(r\) 個の同じものの内部での並べ替えは \(r!\) 通りあります。
    • …
  3. 重複度で割る:これらの重複は互いに独立して発生するため、積の法則により、1つの実際の順列に対して、仮定の世界では \(p! \times q! \times r! \times \cdots\) 通りの順列が対応してしまっています。したがって、正しい場合の数を求めるには、全体の \(n!\) をこの総重複度で割ります。

【同じものを含む順列の公式】

\(n\) 個のもののうち、\(p\) 個が同じ、\(q\) 個が同じ、\(r\) 個が同じ、…であるとき、これらすべてを並べる順列の総数は、

\[

\frac{n!}{p! q! r! \cdots} \quad (\text{ただし } p+q+r+\cdots = n)

\]

この式は、後に学ぶ組合せ \(_n\mathrm{C}_r\) の計算式の一般化と見ることもでき、多項定理などにも繋がる非常に重要な形です。

6.2. 計算の実践

例題1：SUCCESS

SUCCESS という単語の7文字をすべて使って作られる文字列は何通りあるか。

思考プロセス

  1. 文字の構成を分析する:
    • 総文字数 \(n=7\)
    • S: 3個 (\(p=3\))
    • U: 1個
    • C: 2個 (\(q=2\))
    • E: 1個（1個の文字は、階乗で言えば \(1!=1\) なので、計算上は無視できます）
  2. 公式を適用する:求める場合の数は、\[\frac{7!}{3! \cdot 2!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)}\]計算のコツは、大きな階乗を先に約分することです。\[= \frac{7 \times 6 \times 5 \times 4}{2 \times 1} = 7 \times 6 \times 5 \times 2 = 420\]答えは 420通り となります。

例題2：最短経路問題

下図のような格子状の道路がある。地点Aから地点Bまで、遠回りをしないで（右または上へのみ進む）行く最短経路は何通りあるか。

[図：横に5マス、縦に3マスの格子状の道路。左下隅がA、右上隅がB]

思考プロセス

  1. 移動の構成要素を分析する:AからBへ最短で行くためには、
    • 右に5回（→）
    • 上に3回（↑）移動する必要があります。どのような経路をたどったとしても、この移動の構成は変わりません。
  2. 順列の問題として再構成する:この問題は、「5個の『→』という記号と、3個の『↑』という記号、合計8個の記号を一列に並べる順列の問題」と見なすことができます。例えば、
    • →→→→→↑↑↑ という順列は、最初に右に5回進み、次に上に3回進む経路に対応します。
    • →↑→↑→↑→→ という順列は、右、上、右、上…と交互に進む経路に対応します。経路の総数は、この8個の記号の並べ方の総数と一対一で対応します。
  3. 同じものを含む順列の公式を適用する:
    • 総移動回数（総文字数）： \(n = 5 + 3 = 8\)
    • 同じもの「→」の個数： \(p=5\)
    • 同じもの「↑」の個数： \(q=3\)
    求める経路の総数は、\[\frac{8!}{5! \cdot 3!} = \frac{8 \times 7 \times 6 \times 5!}{5! \times (3 \times 2 \times 1)} = \frac{8 \times 7 \times 6}{6} = 56\]答えは 56通り となります。ちなみに、\(\frac{8!}{5!3!}\) は、組合せの計算 \(_8\mathrm{C}_3\)（または \(_8\mathrm{C}_5\)）と全く同じ形をしています。これは偶然ではなく、8回の移動ステップのうち、どの3回を「上向き（↑）」にするかを選ぶ（あるいはどの5回を「右向き（→）」にするかを選ぶ）組合せの問題としても解釈できるからです。この事実は、順列と組合せが密接に関連していることを示唆しています。

6.3. 「組合せ」との関係性（プレビュー）

同じものを含む順列の考え方は、実は組合せの概念を導き出すための重要なステップとなります。

\(n\) 個の異なるものから \(r\) 個を選ぶ組合せ \(_n\mathrm{C}_r\) を考えてみましょう。

これは、

  • 選ばれる \(r\) 個の印（○）
  • 選ばれない \(n-r\) 個の印（×）合計 \(n\) 個の印を一列に並べる順列の問題と考えることができます。

例えば、{A, B, C, D, E} の5人から3人を選ぶ組合せを考えます。

これは、5つのポジションに、3個の「○」（選ばれる）と2個の「×」（選ばれない）を配置する問題と同じです。

○ ○ ○ × × という並びは、A, B, C が選ばれ、D, E が選ばれないことを意味します。

○ × ○ × ○ という並びは、A, C, E が選ばれ、B, D が選ばれないことを意味します。

この並べ方の総数は、同じものを含む順列の公式から、

\[

\frac{5!}{3! \cdot 2!}

\]

となり、これはまさしく \(_5\mathrm{C}_3\) の計算式そのものです。

このように、同じものを含む順列の「重複を割り算で消去する」という発想は、順序を問わない「組合せ」の世界への扉を開く鍵となります。この考え方をしっかりとマスターしておくことが、次のモジュールへのスムーズな移行を約束します。

7. 辞書式配列法

順列を単に数え上げるだけでなく、特定の規則に従って体系的にリストアップしたい場合があります。その最も代表的な方法が辞書式配列法 (Lexicographical Order) です。これは、英単語が辞書にアルファベット順で並んでいるように、文字や数字を特定の順序（アルファベット順、数の大小順など）に従って並べる方法です。この方法論を理解することで、単なる総数の計算から一歩進んで、順列の構造そのものをより深く分析する能力が身につきます。

7.1. 辞書式配列の原理

辞書式配列の原理は非常にシンプルです。「先頭（左側）に来る要素を可能な限り小さく（またはアルファベット順で先に）保つ」というものです。

例えば、文字 {a, b, c} から作られる順列を辞書式に並べてみましょう。

基準となる順序は a < b < c です。

  1. 先頭の文字を固定する:まず、先頭の文字として最も小さい a を選びます。残りの文字は {b, c} です。この2文字で作られる順列は (b, c) と (c, b) です。これを a の後ろに繋げると、
    • a, b, c
    • a, c, bとなります。
  2. 次の文字に進む:先頭が a のパターンをすべてリストアップしたので、次に小さい b を先頭に選びます。残りの文字は {a, c} です。この2文字で作られる順列は (a, c) と (c, a) です。これを b の後ろに繋げると、
    • b, a, c
    • b, c, aとなります。
  3. 最後の文字に進む:最後に、残った c を先頭に選びます。残りの文字は {a, b} です。この2文字で作られる順列は (a, b) と (b, a) です。これを c の後ろに繋げると、
    • c, a, b
    • c, b, aとなります。

これらをすべて統合すると、{a, b, c} の順列の辞書式配列が完成します。

  1. abc
  2. acb
  3. bac
  4. bca
  5. cab
  6. cba

このプロセスから分かるように、辞書式配列は、まず最初の位置の要素を固定し、残りの部分について再帰的に順列を考え、それがすべて尽きたら最初の位置の要素を次に進める、という系統的な構造を持っています。この構造を理解することが、辞書式配列に関する問題を解く鍵となります。

7.2. 特定の順列が何番目かを求める問題

辞書式配列法で最も典型的な問題の一つが、「与えられた順列が、すべての順列を辞書式に並べたときに何番目に来るか」というものです。

例題1：cbaed は何番目か

a, b, c, d, e の5文字をすべて使ってできる順列を辞書式に並べるとき、cbaed は何番目になるか。

思考プロセス

cbaed よりも前に来る順列がいくつあるかを数え上げ、それに1を足すことで順位を求めます。

  1. 先頭が a で始まる順列:先頭の文字が a の場合、cbaed よりも必ず前に来ます。残りの4文字 {b, c, d, e} を自由に並べることができるので、その総数は \(4! = 24\) 通りです。
  2. 先頭が b で始まる順列:同様に、先頭の文字が b の場合も、cbaed よりも前に来ます。残りの4文字 {a, c, d, e} を自由に並べることができるので、その総数は \(4! = 24\) 通りです。
  3. 先頭が c で始まる順列:いよいよ、目的の cbaed と同じ先頭文字 c に到達しました。ここからは、2番目の文字に注目します。先頭が c で、2番目の文字が cbaed の b よりも小さい場合を考えます。c の次に使える文字は {a, b, d, e} です。b よりも小さいのは a だけです。
    • ca で始まる順列:c と a を使ったので、残りの3文字 {b, d, e} を自由に並べることができます。その総数は \(3! = 6\) 通りです。これらは cbaed よりも前に来ます。
  4. cb で始まる順列:次に、先頭が cb となる場合を考えます。目的の cbaed と2文字目まで一致しました。3番目の文字に注目します。c, b の次に使える文字は {a, d, e} です。cbaed の3番目の文字は a です。a が最も小さい文字なので、cba よりも前に来る cb… という形の順列は存在しません。
  5. cba で始まる順列:3文字目まで一致しました。4番目の文字に注目します。c, b, a の次に使える文字は {d, e} です。cbaed の4番目の文字は e です。e よりも小さい d を4番目に置く場合を考えます。
    • cbad で始まる順列:残りの1文字 e を5番目に置くしかありません。つまり cbade です。これは1通りです。この順列は cbaed よりも前に来ます。
  6. cbae で始まる順列:4番目の文字が e の場合を考えます。残りの1文字 d を5番目に置くしかありません。これで、目的の順列 cbaed に到達しました。

計算のまとめ

cbaed よりも前に来る順列の総数は、

  • a で始まるもの：\(4! = 24\)
  • b で始まるもの：\(4! = 24\)
  • ca で始まるもの：\(3! = 6\)
  • cbad で始まるもの：\(1! = 1\) (※ cbade のこと)

合計：\(24 + 24 + 6 + 1 = 55\) 通り。

したがって、cbaed の前に55通りの順列が存在するので、cbaed 自体は 56番目 となります。

7.3. 特定の番号の順列を求める問題

逆の問題、「辞書式配列で100番目に来る順列は何か」という問題も重要です。

例題2：100番目の順列は？

a, b, c, d, e の5文字をすべて使ってできる順列を辞書式に並べるとき、100番目の順列を求めよ。

思考プロセス

今度は、階乗の塊を使って、100という数がどのグループに属するかを特定していきます。

  1. 先頭文字の特定:
    • 先頭が a で始まる順列は \(4! = 24\) 通りあります。(1番目から24番目まで)
    • 先頭が b で始まる順列も \(4! = 24\) 通りあります。(25番目から48番目まで)
    • 先頭が c で始まる順列も \(4! = 24\) 通りあります。(49番目から72番目まで)
    • 先頭が d で始まる順列も \(4! = 24\) 通りあります。(73番目から96番目まで)
    • 先頭が e で始まる順列も \(4! = 24\) 通りあります。(97番目から120番目まで)
    100番目の順列は、97番目から120番目のグループに属するので、先頭の文字は e であることが確定します。
  2. 2番目の文字の特定:先頭が e で始まる順列の中で、何番目かを知る必要があります。96番目までが d で始まる順列だったので、e で始まる最初の順列 eabcd は97番目です。我々が探しているのは100番目なので、e で始まる順列の中では \(100 – 96 = 4\) 番目の順列です。さて、e を除いた残り4文字 {a, b, c, d} を辞書式に並べ、その4番目を求めれば良いことになります。
    • e の次に a が来る順列（ea… の形）：残りの3文字 {b, c, d} の並べ方なので \(3! = 6\) 通りあります。我々が探している4番目は、このグループの中にあります。したがって、2番目の文字は a であることが確定します。
  3. 3番目の文字の特定:ea で始まる順列の中で、4番目のものを探します。残りの3文字 {b, c, d} を辞書式に並べ、その4番目を求めます。
    • ea の次に b が来る順列（eab… の形）：残りの2文字 {c, d} の並べ方は cd と dc の \(2! = 2\) 通りです。( eabcd, eabdc )
    • ea の次に c が来る順列（eac… の形）：残りの2文字 {b, d} の並べ方は bd と db の \(2! = 2\) 通りです。( eacbd, eacdb )
    eaで始まる順列をリストアップすると、
    1. eabcd
    2. eabdc
    3. eacbd
    4. eacdb ← これが4番目です。
    したがって、e で始まる順列の4番目は eacdb です。

結論

100番目の順列は eacdb となります。

辞書式配列の問題は、一見すると地道な作業に思えますが、その実、階乗を用いて「かたまり」として順列を処理する、極めて論理的な思考を要求します。大きな位（左側）から順番に決定していくという系統的なアプローチを身につけることが、この種の問題を迅速かつ正確に解くための鍵となります。

8. 条件付き順列（隣り合う、隣り合わない）

実際の順列の問題では、「特定の人々が隣り合うように」あるいは「隣り合わないように」といった、配置に関する様々な制約条件が付加されることがほとんどです。これらの条件付き順列の問題を解くためには、これまで学んだ順列の基本原則に加え、条件を巧みに処理するためのいくつかの定石的なテクニックを習得する必要があります。ここでは、最も代表的な「隣り合う」と「隣り合わない」という2つの条件を攻略するための戦略的思考法を学びます。

8.1. 「隣り合う」条件：ひとかたまり（ブロック化）戦略

条件：「特定の要素が隣り合う」

この条件を処理するための最も強力な戦略は、「隣り合うべき要素をひとつの『かたまり』または『ブロック』と見なし、一時的に一体化して考える」ことです。

思考プロセス

  1. ブロック化 (Bundling):隣り合うように指定された \(k\) 個の要素を、ロープで縛るかのように一つの大きなブロックと見なします。
  2. 外部の順列 (External Permutation):このブロックと、残りの \(n-k\) 個の要素を合わせた全体を並べます。要素の総数は、ブロック（1個）+ 残り（\(n-k\) 個）= \((n-k+1)\) 個となります。これらの \((n-k+1)\) 個のものの順列を計算します。
  3. 内部の順列 (Internal Permutation):次に、ブロックの内部に注目します。ブロック化した \(k\) 個の要素は、そのブロックの中で自由に並び替わることができます。この内部での並び替えの総数（\(k!\) 通り）を計算します。
  4. 積の法則の適用:外部の並べ方の各々に対して、内部の並べ方が考えられるため、ステップ2とステップ3で得られた場合の数を積の法則によって掛け合わせます。

例題1：特定の男女が隣り合う

男子4人、女子3人の合計7人が一列に並ぶとき、特定の2人（A君とBさん）が必ず隣り合うような並び方は何通りあるか。

思考プロセス

  1. ブロック化: A君とBさんを一つのブロック (A, B) と見なします。
  2. 外部の順列: このブロック (A, B) と、残りの5人（男子3人、女子2人）の合計6つの要素を並べます。その並べ方は \(6!\) 通りです。例：[男1, 男2, (A, B), 女1, 男3, 女2]
  3. 内部の順列: ブロック (A, B) の内部では、「A君が左、Bさんが右」の場合と、「Bさんが左、A君が右」の場合の2通りの並び方があります。これは \(2! = 2\) 通りです。
  4. 積の法則: 外部の並べ方 \(6!\) 通りの各々に対して、内部の並べ方が \(2!\) 通りずつ存在します。したがって、求める場合の数は、\[6! \times 2! = 720 \times 2 = 1440\]答えは 1440通り となります。

例題2：女子全員が隣り合う

男子4人、女子3人の合計7人が一列に並ぶとき、女子3人が全員隣り合う（かたまって並ぶ）ような並び方は何通りあるか。

思考プロセス

  1. ブロック化: 女子3人を一つの大きなブロック (女1, 女2, 女3) と見なします。
  2. 外部の順列: この女子ブロックと、男子4人の合計5つの要素を並べます。その並べ方は \(5!\) 通りです。例：[男1, 男2, (女子ブロック), 男3, 男4]
  3. 内部の順列: 女子ブロックの内部では、女子3人が自由に並び替わることができます。その並べ方は \(3!\) 通りです。
  4. 積の法則:求める場合の数は、\[5! \times 3! = 120 \times 6 = 720\]答えは 720通り となります。

この「ブロック化」戦略は、「隣り合う」という条件を非常に明快に処理できるため、必ずマスターすべき必須のテクニックです。

8.2. 「隣り合わない」条件：後から挿入（隙間に入れる）戦略

条件：「特定の要素が隣り合わない」

この条件は、「隣り合う」条件よりも少し複雑です。特に、3つ以上の要素が互いに隣り合わない場合、単純に「全体の順列」から「隣り合う場合の数」を引くという余事象の考え方では、うまくいかないことが多いので注意が必要です。（例えば、「3人が隣り合う」の余事象は「3人がかたまってはいない」であり、「誰も隣り合わない」とは異なります。「2人だけが隣り合う」ケースが含まれてしまうからです。）

このような「隣り合わない」条件を処理するための、より安全で確実な戦略が、「条件の付いていない要素を先に並べ、その隙間に条件付きの要素を後から挿入する」という方法です。

思考プロセス

  1. 先行配置 (Priority Placement):隣り合ってはいけないという制約のない要素たちを、まず先に一列に並べてしまいます。
  2. 隙間の特定 (Gap Identification):先行配置した要素たちの間、および両端にできる「隙間」を特定します。\(m\) 個の要素を並べると、その両端と合わせて \((m+1)\) 個の隙間が生まれます。
  3. 挿入 (Insertion):特定した隙間に、隣り合ってはいけない要素たちを1つずつ入れていきます。1つの隙間には最大1つの要素しか入れないことで、「隣り合わない」という条件が自動的に満たされます。これは、\((m+1)\) 個の異なる隙間から、挿入する要素の数（\(k\) 個）だけ選んで並べる順列の問題となります。
  4. 積の法則の適用:ステップ1の並べ方の各々に対して、ステップ3の並べ方が考えられるため、両者の結果を掛け合わせます。

例題3：特定の男女が隣り合わない

男子4人、女子3人の合計7人が一列に並ぶとき、A君とBさんが隣り合わないような並び方は何通りあるか。

思考プロセス（挿入法）

  1. 先行配置: 条件の付いていない残り5人を先に並べます。その並べ方は \(5!\) 通りです。例：[ C, D, E, F, G ]
  2. 隙間の特定: この5人の間と両端に、A君とBさんが入ることのできる隙間ができます。_ C _ D _ E _ F _ G _隙間の数は \(5+1=6\) 箇所です。
  3. 挿入: この6箇所の隙間から、A君が入る場所とBさんが入る場所の2箇所を選んで配置します。場所も人も区別されるので、これは順列です。その方法は \(_6\mathrm{P}_2 = 6 \times 5 = 30\) 通りです。
  4. 積の法則:求める場合の数は、\[5! \times _6\mathrm{P}_2 = 120 \times 30 = 3600\]答えは 3600通り となります。

思考プロセス（余事象）

この問題は、隣り合わない要素が2つだけなので、余事象でも解くことができます。

  • 全体の並び方：\(7! = 5040\) 通り
  • A君とBさんが隣り合う並び方（例題1より）：\(1440\) 通り求める場合の数は、\(5040 – 1440 = 3600\) 通り。結果は一致します。しかし、次の例題を見ると挿入法の優位性が分かります。

例題4：女子全員が隣り合わない

男子4人、女子3人の合計7人が一列に並ぶとき、どの女子も隣り合わないような並び方は何通りあるか。

思考プロセス（挿入法）

  1. 先行配置: 隣り合っても良い男子4人を先に並べます。その並べ方は \(4! = 24\) 通りです。例：[ M1, M2, M3, M4 ]
  2. 隙間の特定: この4人の間と両端に、女子が入れる隙間ができます。_ M1 _ M2 _ M3 _ M4 _隙間の数は \(4+1=5\) 箇所です。
  3. 挿入: この5箇所の隙間に、女子3人を1人ずつ入れていきます。5箇所から3箇所を選んで、3人の女子を並べる順列です。その方法は \(_5\mathrm{P}_3 = 5 \times 4 \times 3 = 60\) 通りです。
  4. 積の法則:求める場合の数は、\[4! \times _5\mathrm{P}_3 = 24 \times 60 = 1440\]答えは 1440通り となります。

この問題を余事象で解こうとすると、「女子が3人隣り合う場合」と「女子が2人だけ隣り合う場合」を全体から引かねばならず、計算が非常に煩雑になります。このことからも、「隣り合わない」という条件に対しては、原則として「挿入法」を用いるのが最も明快かつ安全な戦略であると言えます。

まとめ

  • 「隣り合う」と言われたら → ブロック化して「外の順列 × 中の順列」
  • 「隣り合わない」と言われたら → 関係ないものを先に並べて「隙間に挿入」

この二大戦略を使い分けることで、条件付き順列の問題の多くを体系的に攻略することが可能になります。

9. 完全順列（攪乱順列）

順列の世界には、特定の美しい制約条件を持つ、興味深い特殊な順列が存在します。その代表格が完全順列 (Derangement)、または**攪乱順列（かくらんじゅんれつ）**と呼ばれるものです。これは、「すべての要素が、もともとあった位置（自分の番号の場所）とは異なる位置に配置される順列」を指します。この問題は、プレゼント交換で誰も自分のプレゼントを受け取らない場合や、宛名と違う手紙を全員が封筒に入れてしまう場合など、ユニークな設定で登場します。その解法は、これまでの順列問題とは少し異なり、漸化式を用いたり、包含と排除の原理に基づいたりと、より高度な数学的思考を要求します。

9.1. 完全順列とは何か

【定義】

1から \(n\) までの番号が付けられた \(n\) 個の要素を、\((p_1, p_2, \dots, p_n)\) という順列に並べ替えるとき、すべての \(i\) (\(1 \le i \le n\)) について \(p_i \neq i\) を満たすような順列を、完全順列または攪乱順列と呼びます。

簡単に言えば、「\(i\) 番目の位置に、要素 \(i\) が来てはいけない」という制約が、すべての要素に対して課せられた順列です。

\(n\) 個の要素の完全順列の総数を、\(D_n\) や \(M_n\) (フランスの数学者ピエール・モンモールにちなんでモンモール数と呼ばれる) と書くことがあります。

具体例で理解する

  • n=1 の場合:要素は {1} のみ。順列は (1) の1通り。1番目の位置に1が来てしまっているので、条件を満たしません。したがって、\(D_1 = 0\) 通り。
  • n=2 の場合:要素は {1, 2}。順列は (1, 2) と (2, 1) の2通り。
    • (1, 2): 1番目に1が、2番目に2が来ているのでダメ。
    • (2, 1): 1番目に2が、2番目に1が来ている。条件を満たす。したがって、\(D_2 = 1\) 通り。
  • n=3 の場合:要素は {1, 2, 3}。順列は \(3! = 6\) 通り。(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)このうち、条件を満たすものを探します。
    • (1, 2, 3): すべての位置がダメ。
    • (1, 3, 2): 1番目がダメ。
    • (2, 1, 3): 3番目がダメ。
    • (2, 3, 1): 1番目に2, 2番目に3, 3番目に1。OK。
    • (3, 1, 2): 1番目に3, 2番目に1, 3番目に2。OK。
    • (3, 2, 1): 2番目がダメ。したがって、\(D_3 = 2\) 通り。
  • n=4 の場合:同様にすべての順列を書き出して調べると、以下の9通りが見つかります。(2, 1, 4, 3), (2, 3, 4, 1), (2, 4, 1, 3)(3, 1, 4, 2), (3, 4, 1, 2), (3, 4, 2, 1)(4, 1, 2, 3), (4, 3, 1, 2), (4, 3, 2, 1)したがって、\(D_4 = 9\) 通り。

ここまでの結果をまとめると、\(D_1=0, D_2=1, D_3=2, D_4=9\) となります。この数列には、単純な階乗や累乗のような法則は見出しにくいですが、実は美しい漸化式が存在します。

9.2. 漸化式によるアプローチ

\(n\) が大きくなると、すべてを書き出すのは非現実的です。そこで、\(D_n\) を、それより小さい \(D_{n-1}\) や \(D_{n-2}\) を使って表現する漸化式を導出することを考えます。

思考プロセス：\(D_n\) の導出

\(n\) 個の要素 {1, 2, …, n} の完全順列を考えます。

まず、1番目の位置に注目します。この位置には、1以外の要素、つまり {2, 3, …, n} のいずれかが入ります。その選び方は \(n-1\) 通りです。

ここで、1番目の位置に要素 \(k\) (\(k \neq 1\)) が入ったと仮定します。

ここからが重要で、要素 \(k\) の行き先である、\(k\) 番目の位置に入る要素によって場合分けをします。

  • 場合分け1：\(k\) 番目の位置に、要素1が入る場合1番目 → kk番目 → 1このように、要素1と要素 \(k\) が互いの場所を交換する形になります。残りの要素は、{1, k} を除いた \(n-2\) 個です。これらの \(n-2\) 個の要素は、それぞれ自分たちの元の位置（2, 3, …, k-1, k+1, …, n番目）に入ってはいけない、という制約を受けます。これはまさに、\(n-2\) 個の要素の完全順列の問題そのものです。したがって、この場合の数は \(D_{n-2}\) 通りです。
  • 場合分け2：\(k\) 番目の位置に、要素1が入らない場合1番目 → kk番目 → 1 ではない何かこの状況を少し見方を変えてみましょう。残りの要素は {1, 2, …, k-1, k+1, …, n} の \(n-1\) 個です。これらの要素を、残りの \(n-1\) 個のポジション {2, 3, …, n} に配置します。このとき、各要素 \(j\) (\(j \neq 1, k\)) は、\(j\) 番目のポジションに入ってはいけません。そして、要素1は、\(k\) 番目のポジションに入ってはいけません。ここで、もし我々が「\(k\) 番目のポジション」を仮に「1番目のポジション」と名前を付け替えるとどうなるでしょうか。すると、この問題は、「\(n-1\) 個の要素 {1, 2, …, k-1, k+1, …, n} を、\(n-1\) 個のポジション {2, 3, …, “1”, …, n} に、どの要素も自分の番号のポジションに入らないように配置する」という問題と等価になります。これは、\(n-1\) 個の要素の完全順列の問題そのものです。したがって、この場合の数は \(D_{n-1}\) 通りです。

漸化式の完成

1番目に入れる要素 \(k\) の選び方は \(n-1\) 通りありました。

そして、その各々の \(k\) の選択に対して、上記の「場合分け1」または「場合分け2」が起こります。これらは排反な事象なので、和の法則を適用します。

したがって、\(k\) を1つ固定したときの場合の数は \((D_{n-2} + D_{n-1})\) 通りとなります。

最終的に、最初の \(k\) の選び方 \(n-1\) 通りを掛け合わせることで、漸化式が完成します。

【完全順列の漸化式】

\[

D_n = (n-1)(D_{n-1} + D_{n-2}) \quad (n \ge 3)

\]

ただし、\(D_1=0, D_2=1\)。

この漸化式を使って、\(D_n\) の値を順次計算してみましょう。

  • \(D_3 = (3-1)(D_2 + D_1) = 2(1 + 0) = 2\)
  • \(D_4 = (4-1)(D_3 + D_2) = 3(2 + 1) = 9\)
  • \(D_5 = (5-1)(D_4 + D_3) = 4(9 + 2) = 4 \times 11 = 44\)
  • \(D_6 = (6-1)(D_5 + D_4) = 5(44 + 9) = 5 \times 53 = 265\)

大学受験レベルでは、\(D_5\) あたりまでが問われる可能性があります。漸化式を導出するか、あるいは \(D_4=9\) あたりまでの値を覚えておくと有利な場合があります。

9.3. 公式（参考）

完全順列の総数 \(D_n\) は、漸化式だけでなく、直接計算できる公式も存在します。これは、高校数学の範囲を超える「包含と排除の原理」を用いて導出されますが、結果を知っておくことは興味深いでしょう。

【完全順列の公式】

\[

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} – \frac{1}{1!} + \frac{1}{2!} – \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!} \right)

\]

この式は、一見すると複雑ですが、展開してみると、

\(D_n = n! \times (\text{全員がOK}) – n! \times (\text{1人がOK}) + n! \times (\text{2人がOK}) – \cdots\)

という構造を修正した形になっています。（厳密には組合せの考え方が必要）

自然対数の底 \(e\) との関係

実は、\(n\) が大きくなると、\(D_n\) の値は \(\frac{n!}{e}\) に非常に近くなります。ここで \(e\) は自然対数の底（約2.718）です。

なぜなら、\(e^x\) のマクローリン展開は \(e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}\) であり、\(x=-1\) を代入すると \(e^{-1} = \frac{1}{e} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}\) となり、上記の公式の括弧の中身と一致するからです。

つまり、ランダムに \(n!\) 通りの順列を作ったとき、それが完全順列である確率は、\(n\) が大きいとき約 \(\frac{1}{e} \approx 0.368\) (36.8%) に収束します。これは非常に興味深い事実です。

完全順列は、その独特な制約条件と美しい数学的構造から、単なる順列の応用問題としてだけでなく、数学の奥深さや分野間の繋がりを感じさせてくれる魅力的なテーマであると言えるでしょう。

10. 塗り分け問題

これまでに学んだ順列の諸概念、特に積の法則を応用する実践的な問題として、「塗り分け問題」があります。これは、地図上の国や、図形の各領域を、指定された条件（例：「隣り合う領域は異なる色で塗る」）に従って、何色かの絵の具で塗り分ける方法が何通りあるかを数え上げる問題です。この種の問題を解く鍵は、どの領域から塗り始めるかという「戦略的な順序」と、各ステップで利用可能な色の数を正確に把握することにあります。

10.1. 塗り分けの基本戦略

塗り分け問題の多くは、以下の戦略的な思考プロセスによって解くことができます。

【基本戦略】

  1. 隣接関係の把握:まず、どの領域がどの領域と隣接しているかを正確に把握します。図に線で結ぶなどして、隣接関係を可視化すると間違いが減ります。
  2. 塗る順番の決定（最重要）:最も多くの他の領域と隣接している領域から塗り始めるのが、最も効率的で間違いの少ない定石です。なぜなら、制約が最も厳しい場所を最初に確定させることで、その後の選択肢の計算が楽になるからです。同じ数の隣接領域を持つものが複数ある場合は、どれから始めても構いませんが、一度決めたら系統的に進めることが大切です。
  3. 積の法則の適用:決定した順番に従って、各領域を塗っていきます。
    • 最初の領域：使える色の数だけ選択肢があります。
    • 2番目の領域：既に塗られた隣接領域の色を除いた色の数だけ選択肢があります。
    • 3番目の領域：同様に、それまでに塗られた隣-接領域の色を除いた数だけ選択肢があります。このプロセスは、まさに積の法則の世界です。各ステップでの選択肢の数を掛け合わせることで、総数を求めます。
  4. 場合分けの検討:塗る順番によっては、途中で「もし前の領域でこの色を塗っていたら、次の選択肢は…通り。もし別の色なら…通り」というように、選択肢の数が一定にならない場合があります。このような状況に陥った場合は、その分岐点で和の法則に基づいた場合分けが必要になります。

10.2. 基本的な塗り分け問題

例題1：5領域の塗り分け

下図のA, B, C, D, Eの5つの領域を、すべて異なる5色で塗り分ける方法は何通りあるか。

[図：中央にAがあり、その周りをB,C,D,Eが時計回りに囲んでいる。BはCと、CはDと、DはEと、EはBと隣接していないが、AはB,C,D,Eすべてと隣接している。]

思考プロセス

この問題は、「すべて異なる5色」という指定があります。

これは、5つの異なる領域に、5つの異なる色を割り当てる問題です。

したがって、5色の順列そのものと考えられます。

\(_5\mathrm{P}_5 = 5! = 120\) 通り。

例題2：隣接領域が異なる色

例題1の図を、5種類の色を使って、隣り合う領域が異なる色になるように塗り分ける方法は何通りあるか。同じ色を何回使ってもよい。

思考プロセス

  1. 隣接関係の把握:
    • Aは、B, C, D, E の4領域と隣接。
    • Bは、A, C, E の3領域と隣接。
    • Cは、A, B, D の3領域と隣接。
    • Dは、A, C, E の3領域と隣接。
    • Eは、A, B, D の3領域と隣接。
  2. 塗る順番の決定:最も多くの領域と隣接しているのは A (4領域) です。したがって、Aから塗り始めます。その後は、B→C→D→E のように時計回りに塗っていくのが系統的です。
  3. 積の法則の適用:
    • Aを塗る: 使える色は5色なので、5通り。
    • Bを塗る: Aと隣接しているので、Aで使った色以外。4通り。
    • Cを塗る: AとBに隣接しているので、AとBで使った2色以外。3通り。
    • Dを塗る: AとCに隣接しているので、AとCで使った2色以外。3通り。
    • Eを塗る: AとDとBに隣接しているので、AとDとBで使った3色以外。2通り。
    ん？ここで、DとEの選択肢を計算する際に、BとCの色が関係してきて、選択肢が一定にならない可能性が出てきました。例えば、BとDが同じ色か違う色かで、Eの選択肢が変わってしまいます。
    • もし BとDが違う色なら、EはA, D, Bの3色と違う色で塗る必要があり、選択肢は \(5-3=2\) 通り。
    • もし BとDが同じ色なら、EはA, D, B (DとBは同じ色)の2色と違う色で塗る必要があり、選択肢は \(5-2=3\) 通り。
    このように、単純な積の法則ではうまくいきません。ここで「場合分け」が必要になります。

10.3. 場合分けが必要な塗り分け問題

例題2のように、途中で選択肢の数が一定でなくなる問題は、塗り分け問題の典型的な難問です。この場合、選択肢の数を変動させる原因となる領域の関係に着目して場合分けを行います。

例題2では、Eの選択肢に影響を与えるBとDが「向かい合って」おり、直接隣接していないことが原因です。このBとDが同じ色か、異なる色かで場合分けをします。

例題2の解法（場合分け）

塗る順番は、A→B→C までは共通とします。

  • Aの塗り方: 5通り
  • Bの塗り方: (A以外) 4通り
  • Cの塗り方: (A, B以外) 3通り

ここから、Dの塗り方について、Bとの色の関係で場合分けします。

場合分け1：DがBと同じ色の場合

  • Dの塗り方: Bと同じ色に塗るので、選択肢は1通り。(このとき、DはCとも隣接しているので、BとCが同じ色でないことを確認する必要がありますが、A→B→Cの塗り方からBとCは必ず違う色なので問題ありません。)
  • Eの塗り方: EはAとD(Bと同じ色)に隣接しています。したがって、AとBの2色以外で塗ればよいので、選択肢は3通り。
  • この場合の総数：\(5 \times 4 \times 3 \times 1 \times 3 = 180\) 通り。

場合分け2：DがBと異なる色の場合

  • Dの塗り方: DはA, Cと隣接しており、さらにBとも違う色でなければなりません。A, C, Bはすべて異なる色なので、この3色以外の色で塗る必要があります。選択肢は \(5-3=2\) 通り。
  • Eの塗り方: EはA, B, Dと隣接しています。A, B, Dはすべて異なる色なので、この3色以外の色で塗る必要があります。選択肢は \(5-3=2\) 通り。
  • この場合の総数：\(5 \times 4 \times 3 \times 2 \times 2 = 240\) 通り。

結論

場合分け1と場合分け2は互いに排反なので、和の法則により、

総数は \(180 + 240 = 420\) 通りとなります。

なぜ場合分けが必要になったのか？

この問題の困難さは、円環状の隣接関係（B-C-D-E-B…）に起因します。一本道の塗り分けであれば、通常は単純な積の法則で解けます。しかし、ループ構造があると、始点と終点が繋がってしまい、最後の領域を塗る際に、最初の領域の色を考慮しなければならなくなるため、複雑性が増すのです。このようなループ構造を持つ問題では、ループを断ち切るような向かい合う領域（この場合はBとD）の関係性で場合分けする、というアプローチが非常に有効です。

ミニケーススタディ：立方体の塗り分け

立方体の6つの面を、異なる6色をすべて使って塗り分ける方法は何通りか。回転して同じになるものは同一と見なす。

思考プロセス

これは立体版の円順列のような問題です。

  1. 固定法を用いる:まず、1つの面（例えば底面）を特定の色（例えば赤色）で固定します。この固定は、回転による重複をなくすための基準を作る操作なので、1通りと考えます。
  2. 対面の決定:底面（赤）の向かい側にある面（上面）の色を決めます。残っている5色の中から選ぶので、5通りの選択肢があります。
  3. 側面の円順列:上面と底面の色が確定すると、残りの4つの側面は、立方体を上から見たときに円形に配置されていると見なせます。したがって、残りの4色を、この4つの側面に塗り分ける方法は、4色の円順列となります。その総数は \((4-1)! = 3! = 6\) 通りです。
  4. 積の法則:ステップ2とステップ3の結果を掛け合わせます。\(5 \times (4-1)! = 5 \times 6 = 30\) 通り。

答えは 30通り となります。この問題は、順列、固定法、円順列という、これまで学んだ複数の概念を立体的に組み合わせることで解ける、美しい応用問題です。

塗り分け問題は、単なる計算練習ではなく、問題の構造を的確に把握し、最適な解法戦略（積の法則、場合分け、固定法など）を選択する論理的判断力を養うための優れた演習となります。

Module 1：場合の数(1) 順列の総括：体系的計数の思考法

本モジュールを通じて、我々は「順列」という概念を、その根源的な原理から多角的な応用まで、体系的に探求してきました。出発点は、すべての計数の礎となる「和の法則」と「積の法則」でした。これら二つの法則は、単なる計算規則ではなく、複雑な事象を「排反なケースへの分割」と「連続するステップへの分解」という二つの基本的な視点から整理するための、強力な思考のフレームワークを提供してくれます。

\(nPr\) という順列の定義は、積の法則の直接的な帰結であり、それを簡潔に表現する「階乗 (\(n!\))」という概念は、\(n\) 個の要素が持つ内在的な多様性の数を象徴していました。そして、思考の舞台を直線から円環へと移した「円順列」では、「固定」という一つの操作が、いかにして回転という対称性を打ち破り、数え上げを可能にするかという、問題解決における視点変換の重要性を学びました。

さらに、現実世界の多様な状況をモデル化するために、「重複順列」では繰り返しを許し、「同じものを含む順列」では区別のない要素を扱い、それぞれのケースで生じる重複を、累乗や割り算といった操作でいかに合理的に処理するかを学びました。特に、「同じものを含む順列」における「区別を仮定し、後でその区別による重複を割る」という発想は、後に学ぶ「組合せ」の概念へと直接的に繋がる、極めて重要な橋渡しとなります。

「辞書式配列法」では、順列の構造そのものに深く分け入り、系統的なリストアップの論理を追体験しました。そして、「条件付き順列」では、「隣り合う」要素をブロック化する戦略や、「隣り合わない」要素を後から挿入する戦略といった、制約を乗り越えるための定石的なテクニックを習得しました。最後に、「完全順列」や「塗り分け問題」といった応用テーマは、これらの基本概念が有機的に結びつき、より複雑で挑戦的な問題解決へと昇華されていく様を見せてくれました。

このモジュールを通して、皆様が手に入れたものは、個々の公式や解法のリストではありません。それは、どのような計数問題に直面しても、その構造を見抜き、適切な法則やモデルを適用し、論理的なステップを積み重ねて答えにたどり着くための、「体系的計数の思考法」です。この思考法こそが、次なる「組合せ」、そして「確率」という広大な数学の世界を探求するための、最も信頼できる羅針盤となるのです。

基礎数学 基礎 数学A
目次