読者です 読者をやめる 読者になる 読者になる

猫尾製作所

あまりアテにしないでね

順列と階乗

数学 代数学

異なる  n 個の対象の、重複しないいろいろな並び方を  n 個の順列(じゅんれつ)といいます。

まず、辞書的な定義から入りました。しかし、これだけではわかりにくいので、次に順列の具体例について書きます。並び方、とありますが、一般的にいわれる並べるものではなくてもいいのです。

時期的な例を挙げるといいかも。というわけで、あなたは今年、お盆休みを3日間もらったとしましょう。たった3日だけのお盆休みですが、したいことは決まっています。お盆なので当然ある日には墓参りに行きたいのですが、別の日には海水浴に行きたい、また別の日には勉強のため図書館に行きたい。というふうに3日分の予定は決まっているのです。ですので、あとはどの日にどれを行うか、が問題となります。1日に複数の予定は行わないものとします(墓参りの帰りに図書館に寄るなどは×)、また同じ予定を複数回してもなりませんが(毎日墓参りに行くなどは×)、3つの予定は全て行うものとします(墓参りに行かないとかも×)。

この条件下でのお盆休みの予定の候補リストは次のようになります。

1日目 2日目 3日目
墓参り 海水浴 図書館
墓参り 図書館 海水浴
海水浴 墓参り 図書館
海水浴 図書館 墓参り
図書館 墓参り 海水浴
図書館 海水浴 墓参り

お盆休みの過ごし方の候補は全部で6通りとなります。

さて、今入ってきた情報によりますと、さらにもう一日休めるとのことです。つまり、お盆休みは計4日間となります。そこで、もうひとつ予定を増やすことが出来ます。のこりの一日は自宅でゲームでもしようかな。しかし、4日間の予定の候補は何通りになるのだろう。

では。{ 墓参り, 海水浴, 図書館, ゲーム } という4つの予定リストの中から、1日目にすることを決めるときには4つ選択肢があります。しかし、1日目の予定は埋まったので予定リストからも一つ消します。2日目の行動の選択肢は残りの3つのうちから。3日目の行動の選択肢はさらに残りの2つのうちから。すると、4日目の行動の選択肢は残った1つしかありません。つまり、行動の選択肢は 4×3×2×1 で 24通りとなります。4 から 1 までの整数の掛け合わせです。

例示に固執して、かえって解りにくくなったかもしれません。ともかく、4個のものを並び替える順列の総数は 4×3×2×1 で 24 ということになります。一般に  n 個のものを並び替える順列の総数は  n から  1 までの整数の掛け合わせである  n \times (n-1) \times \cdots \times 3 \times 2 \times 1 となります。

この整数の掛け合わせ  n \times (n-1) \times \cdots \times 3 \times 2 \times 1 には  n階乗という名前がついていて、びっくりマーク「!」を用いて  n! と表現されます。

階乗についてはCDに入っている  n 曲を重複させることなく、全て再生したいときの再生順は  n! 通りあるとか、 n 枚のトランプのカードをシャッフルさせるとき、カードの並び方は  n! 通りある、というふうに簡潔な具体例も挙げることができます。

この階乗の再帰的な定義(漸化式での表現)は  0! = 1 という規約のもと、 n \ge 1 に対して  n! = n \times (n-1)! というものになります。

この  n! の具体的な数値は次のようになります。

 0! =                                         1
 1! =                                         1
 2! =                                         2
 3! =                                         6
 4! =                                        24
 5! =                                       120
 6! =                                       720
 7! =                                      5040
 8! =                                    4 0320
 9! =                                   36 2880
10! =                                  362 8800
11! =                                 3991 6800
12! =                               4 7900 1600
13! =                              62 2702 0800
14! =                             871 7829 1200
15! =                          1 3076 7436 8000
16! =                         20 9227 8988 8000
17! =                        355 6874 2809 6000
18! =                       6402 3737 0572 8000
19! =                    12 1645 1004 0883 2000
20! =                   243 2902 0081 7664 0000
21! =                  5109 0942 1717 0944 0000
22! =               11 2400 0727 7776 0768 0000
23! =              258 5201 6738 8849 7664 0000
24! =             6204 4840 1733 2394 3936 0000
25! =          15 5112 1004 3330 9859 8400 0000
26! =         403 2914 6112 6605 6355 8400 0000
27! =      1 0888 8694 5041 8352 1607 6800 0000
28! =     30 4888 3446 1171 3860 5015 0400 0000
29! =    884 1761 9937 3970 1954 5436 1600 0000
30! = 2 6525 2859 8121 9105 8636 3084 8000 0000

といった感じになります。 n の増え方に対し、急激に大きくなるのです。20の階乗は19桁で約243京、30の階乗だと33桁で2溝を超えます(現代日本語の数詞では 一万倍になるごとに、一、万(10^4)、億(10^8)、兆(10^12)、京(10^16)、垓(10^20)、𥝱(10^24)*1、穣(10^28)、溝(10^32)、… となります)。この先は 70! で 10の100乗(1グーゴル)を超えます。

今回は階乗の話題で終わってしまいましたが、次回からはもうすこし抽象化して順列についてのおはなしを進めていきます。

*1:この文字は「じょ」と読むのですが、取り扱いに関しましての参考URLとして http://ja.wikipedia.org/wiki/%E3%81%98%E3%82%87 を挙げておきます。