【階乗とは】順列と置換の基礎、計算方法をやさしく解説！【樹形図】

こんにちは。iQeda [@iQeeeda] です。

物やデータを並べるとき「何パターンの並べ方が考えられるか？」を検討するのは重要です。
また、全部を並べるのか・一部だけ選んで並べるのか…で話は違います。

置換とは

3 枚のカード A, B, C の順序を並べかえるとします。
※ 例えば、ABC, ACB, BCA … といったように

並べ方は全部で何通りあるでしょうか？

実際に並べてみると、答えは 6 通りです。
順序を考えて n 個のものを全て並べることを「置換」といいます。

置換の総数

では、計算結果をもとに置換の総数 (順序を考えて並べた総数) を求め方を説明します。

「 1 枚目の選び方 * 2 枚目の選び方 * 3 枚目の選び方」で何通りあるか計算できます。
置換の総数は 3 * 2 * 1 で 6 通りと求めることができます。

階乗とは

次はカードを 5 枚に増やしてみましょう。
5 枚のカード A, B, C, D, E の置換の総数はいくつでしょう？

答えは 5 * 4 * 3 * 2 * 1 で 120 通りです。

読み方は「5 の階乗」です。

置換の総数の一般化

置換の総数を一般化してみましょう。 n 枚のカードの置換の総数はいくつになるでしょうか？

答えは n! です。
つまり n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 のことです。

【問題】トランプの並べかた

ジョーカーを除くとトランプは 52 枚ありますが、一列に並べる方法は何通りでしょうか？

答え

答えは 52! で、計算すると 80658175170943878571660636856403766975289505440883277824000000000000 通りです。階乗は非常に数が大きくなるのが特徴です。

階乗の値

階乗の値について、いくつか例を示します。

ゼロの階乗について

これは深く考えるより「そういうルールだから」と思っておいてください。

そういうルールだからと言われても…

一応解説しました！
…が今はそんなに気にしなくていい、とだけ言っておきます。

順列とは

5 枚のカード A, B, C, D, E から 3 枚選び出し、
順序を考えて並べる場合の並べ方は何通りでしょうか？

「 1 枚目の選び方 * 2 枚目の選び方 * 3 枚目の選び方」で何通りあるか計算できるので、
並べ方は 5 * 4 * 3 で 60 通りとなります。

順列の総数

順序を考える、ということ

置換・順序の「順序を考えて並べる」という考え方は大事なポイントです。

これは順序を考えているからです。

順列の総数の一般化

n 枚のカードから k 枚のカードを選び出すとして、順列を一般化してみしょう。

順列の総数は (n - 0) * (n - 1) * (n - 2) * ... * (n - k + 1) 通りとなります。
n から引いている数は「 0 から k – 1 まで」変化していきます。

この「 0 から k – 1 まで」って一体何個あるんだ？…を考えるとき、
前回のブログ記事で紹介した「植木算」が使えます。

植木算は 0 番目の存在を忘れずちゃんと数えようという概念でしたが、
そこから「 0 から k – 1 まで」を数えると「 k 個」あることがわかります。
なので (n - 0) * (n - 1) * (n - 2) * ... * (n - k + 1) は k 個の項の掛け算です。

※ P は permutation の略です

5 枚のカードから 3 枚選ぶ順列の総数

5 枚のカードから 3 枚選ぶ順列の総数は 5P3 と表記できます。
5P3 は (5 - 0) * (5 - 1) * (5 - 2) なので、答えは 60 通りとなります。

置換の総数

順列の総数の値

順列の総数について、いくつか例を示します。

項がゼロの順列の総数について

これもそういうルールだから仕方がないと思ってください。

階乗を使った順列の総数の表現

順列の総数は「階乗の表記方法」を使って nPk = n! / (n - k)! と表現することもできます。

たとえば 5P3 は 5! / (5 - 3)! になります。

これは要するに (5 * 4 * 3 * 2 * 1) / (2 * 1) のことで、
分母で分子を約分すると 5 * 4 * 3 になるので、5P3 の意味と一致することが分かります。

樹形図

重複なしの順列

A, B, C 3 枚のカードから 3 枚を選ぶ順列の場合、
同じカードを 2 回選ぶことはできません。

なので、2 枚目・ 3 枚目に選べる枚数は減っていきます。

これを「樹形図」というもので表現してみます。

root
├── A
│   ├── B
│   │   └── C
│   └── C
│       └── B
├── B
│   ├── A
│   │   └── C
│   └── C
│       └── A
└── C
    ├── A
    │   └── B
    └── B
        └── A

根 (root) から 3 本の枝 (branch) が伸びていくように捉えてください。

それぞれの枝からは、枝が 2 本ずつ伸びています。
これは 2 枚目のカードの置き方が 2 通りあることを示しています。

最後の枝からは、枝が 1 本だけ伸びています。
この樹形図から、枝分かれの数は「3 → 2 → 1」と減っていくことが分かります。

重複ありで並べる場合

3 種類のカードから「重複を許して」3 枚並べる場合の樹形図はどうなるでしょうか？
あるカードを選んでも、そのカードは減らない場合のことです。

root
├── A
│   ├── A
│   │   ├── A
│   │   ├── B
│   │   └── C
│   ├── B
│   │   ├── A
│   │   ├── B
│   │   └── C
│   └── C
│       ├── A
│       ├── B
│       └── C
├── B
│   ├── A
│   │   ├── A
│   │   ├── B
│   │   └── C
│   ├── B
│   │   ├── A
│   │   ├── B
│   │   └── C
│   └── C
│       ├── A
│       ├── B
│       └── C
└── C
    ├── A
    │   ├── A
    │   ├── B
    │   └── C
    ├── B
    │   ├── A
    │   ├── B
    │   └── C
    └── C
        ├── A
        ├── B
        └── C

その場合の樹形図は根・すべての枝から 3 本の枝が伸びるようになります。
数える物の性質によってはこのように変化することを知っておきましょう。

CS シリーズ

次回

前回