順列と組み合わせ（nPr と nCr）

Q: 順列と組み合わせ（nPr と nCr）とは何ですか？

異なる n 個のものから異なる r 個を選んで並べる順列の数を _n\mathrm{P}_r、並べる順序を考慮せず単に r 個の組を選ぶ組み合わせの数を _n\mathrm{C}_r と書く。 - 順列: _n\mathrm{P}_r = n(n-1)(n-2)\cdots(n-r+1) = \dfrac{n!}{(n-r)!} - 組み合わせ: _n\mathrm{C}_r = \dfrac{_n\mathrm{P}_r}{r!} = \dfrac{n!}{r!(n-r)!} - 重複順列: 異なる n 種類から重複を許して r 個並べる総数は n^r

Q: 順列と組み合わせ（nPr と nCr）は社会やプログラミングでどのように使われていますか？

パスワードのエントロピー計算とブルートフォース攻撃耐性評価: サイバーセキュリティにおいて、パスワードの強度は総当たり（ブルートフォース）攻撃に必要な試行回数（組み合わせ数 N^L）と、それを毎秒何億回試行できるかで評価される。桁数による組み合わせ数の爆発が防御の最大の武器となる。

「並べる順番」を区別するかどうか。パスワードセキュリティとガチャ確率の数理

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 順列（nPr）は「並べる順番を考慮する」選び方、組み合わせ（nCr）は「グループとして誰がいるかだけ」を見る選び方
2: パスワードの安全性は文字種数^桁数の「重複順列」で決まり、桁数が1つ増えるだけで攻撃者の解析時間は数十〜数百倍に跳ね上がる
3: ソシャゲのガチャで「確率 1% を 100 回引いても約 36.6% の人は当たらない」という直感との乖離は余事象の確率計算で解明される

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

サイコロ賭博の公平な配分問題（パスカルとフェルマーの往復書簡）から、あらゆる「選び方・並べ方」の総数を数え漏れ・重複なく算出するために体系化された。

身につく武器・思考力

「並び順が関係あるか否か」を瞬時に見分け、天文学的な組み合わせ爆発を見積もってリスクや計算量を判断できるようになる。

実社会・ITでの活躍現場

•サイバーセキュリティにおけるパスワード強度（総当たり耐性）評価
•ソーシャルゲームのガチャ排出確率・天井設定のシミュレーション
•ハッシュ衝突耐性（誕生日攻撃）の暗号学的安全性の証明
•ネットワークの通信経路数やトーナメント戦の組み合わせ設計

Layer 1 — 直感・シミュレーター

2つのタブ（パスワード解析時間シミュレータ / ガチャ確率シミュレータ）を操作してみよう。パスワードの文字種（英小文字・英数字・記号）や桁数を増やすと総組み合わせ数が天文学的に跳ね上がり、スーパーコンピュータでも解読に何万年もかかる理由が一目で理解できる。

パスワード桁数:8 桁

4桁（危険）8桁（最低基準）12桁（推奨）16桁（極めて強固）

使用する文字種（総プール数: 36 種類）:

数字 (0-9: 10種)英小文字 (a-z: 26種)英大文字 (A-Z: 26種)記号 (!@#等: 32種)

組み合わせ総数（N^L）

2,821,109,907,456 通り

文字種 36 通りの文字が 8 桁並ぶ重複順列： ${36}^{8}$

解読にかかる推定時間（秒間100億回試行）

約 2.4 分

⚡ 短期間で突破されるリスクがあります。桁数を増やしましょう。

直感チェック！ミニクイズ

排出率 1%（0.01）のガチャを 100 連引いたとき、少なくとも 1 回以上当たる確率は約何％か？

Layer 2 — 定義・受験・証明

定義

異なる $n$ 個のものから異なる $r$ 個を選んで並べる順列の数を $_n\mathrm{P}_r$ 、並べる順序を考慮せず単に $r$ 個の組を選ぶ組み合わせの数を $_n\mathrm{C}_r$ と書く。 - 順列: $_n\mathrm{P}_r = n(n-1)(n-2)\cdots(n-r+1) = \dfrac{n!}{(n-r)!}$ - 組み合わせ: $_n\mathrm{C}_r = \dfrac{_n\mathrm{P}_r}{r!} = \dfrac{n!}{r!(n-r)!}$ - 重複順列: 異なる $n$ 種類から重複を許して $r$ 個並べる総数は $n^r$

公式・数理モデル

_n\mathrm{P}_r = \frac{n!}{(n-r)!}, \quad _n\mathrm{C}_r = \frac{n!}{r!(n-r)!}, \quad n^r

証明・導出

組み合わせの公式の導出： $n$ 個から $r$ 個を選んで並べる手順を2段階で考える。 1. まず $n$ 個から $r$ 個を選ぶ（選び方は $_n\mathrm{C}_r$ 通り） 2. 選んだ $r$ 個を一列に並べる（並べ方は $r!$ 通り）

積の法則より、この連続操作の総数は $_n\mathrm{C}_r \times r!$ となる。これは初めから $n$ 個から $r$ 個を選んで並べる順列 $_n\mathrm{P}_r$ に他ならない。

_n\mathrm{C}_r \times r! = _n\mathrm{P}_r

両辺を $r!$ で割ることで、

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

という公式が導かれる。順序の区別を無くすために、並び順の総数 $r!$ で割るという考え方が本質である。

押さえておきたいポイント

「順番が関係ある」なら順列（P）、「チーム分けのように順序不問」なら組み合わせ（C）
性質: $_n\mathrm{C}_r = _n\mathrm{C}_{n-r}$ （「選ぶ」ことと「選ばないものを決める」ことは同義）
二項定理 $(a+b)^n = \sum_{k=0}^n {_n\mathrm{C}_k} a^{n-k} b^k$ の係数（パスカルの三角形）として現れる
パスワードの安全性（エントロピー）は、文字種数 $N$ と桁数 $L$ による $N^L$ で指数関数的に増大する

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

パスワードのエントロピー計算とブルートフォース攻撃耐性評価

サイバーセキュリティにおいて、パスワードの強度は総当たり（ブルートフォース）攻撃に必要な試行回数（組み合わせ数 $N^L$ ）と、それを毎秒何億回試行できるかで評価される。桁数による組み合わせ数の爆発が防御の最大の武器となる。

1// パスワードの組み合わせ総数と解読時間の試算
2interface SecurityReport {
3  totalCombinations: bigint;
4  secondsToCrack: number;
5  readableTime: string;
6}
7
8function evaluatePasswordStrength(
9  length: number,
10  options: { lowercase: boolean; uppercase: boolean; numbers: boolean; symbols: boolean }
11): SecurityReport {
12  let charPoolSize = 0;
13  if (options.lowercase) charPoolSize += 26;
14  if (options.uppercase) charPoolSize += 26;
15  if (options.numbers) charPoolSize += 10;
16  if (options.symbols) charPoolSize += 32;
17
18  // 総組み合わせ数 = (文字種数)^桁数 (重複順列)
19  const poolBig = BigInt(charPoolSize);
20  const total = poolBig ** BigInt(length);
21
22  // 攻撃者の試行速度: 秒間 100億回 (10^10 / sec) のGPUクラスタを想定
23  const guessesPerSecond = 10_000_000_000n;
24  const secondsBig = total / (guessesPerSecond * 2n); // 平均して半分の探索でヒット
25  const seconds = Number(secondsBig > BigInt(Number.MAX_SAFE_INTEGER) ? Number.MAX_SAFE_INTEGER : secondsBig);
26
27  let readableTime = "1秒未満";
28  if (seconds > 31536000 * 1000) {
29    readableTime = `約 ${(seconds / 31536000).toExponential(1)} 年（解読不可能）`;
30  } else if (seconds > 31536000) {
31    readableTime = `約 ${(seconds / 31536000).toFixed(1)} 年`;
32  } else if (seconds > 86400) {
33    readableTime = `約 ${(seconds / 86400).toFixed(1)} 日`;
34  } else if (seconds > 60) {
35    readableTime = `約 ${(seconds / 60).toFixed(1)} 分`;
36  }
37
38  return { totalCombinations: total, secondsToCrack: seconds, readableTime };
39}
40
41// 例: 数字のみ8桁 vs 英数記号12桁
42const weak = evaluatePasswordStrength(8, { lowercase: false, uppercase: false, numbers: true, symbols: false });
43const strong = evaluatePasswordStrength(12, { lowercase: true, uppercase: true, numbers: true, symbols: true });
44
45console.log(`数字8桁: ${weak.readableTime}`); // 1秒未満
46console.log(`英数記号12桁: ${strong.readableTime}`); // 何万年以上