重複順列

重複順列はふつうの順列に似ていますが、もとの集合 M の要素をくり返して使ってもよいところがちがいます。

定義と公式

典型的な例から始めましょう。英語のアルファベット（abc … xyz の26文字）を使って、長さ6の単語はいくつつくれるでしょうか。6文字はそれほど多くありませんが、それでも単語の数はかなり多くなります。単語の意味は考えないので、「weqrww」のようなものも長さ6の単語として数えます。

計算には積の法則だけを知っていれば十分です。使える文字は全部で 26 種類です。1文字目には 26 文字のどれかを置けます。2文字目にも、やはり 26 文字のどれかを置けます。同じ文字をくり返してはいけない、という条件はつけていないからです。つまり、どの位置でも 26 文字から選ぶことになり、積の法則により、重複順列の総数は 26⁶ = 308,915,776 です。たった26文字しか使っていないのに、かなりの数です。

要素が n 個の集合 M から k 個をとる重複順列とは、集合 M の要素から重複を許して k 個を取り出し、1列に並べたものです。どの要素も、その k 個の並びの中に k 回まで現れてかまいません。たとえば集合 M = {1, 2, 3} なら、(1, 1, 1, 1)、(1, 2, 3, 1)、(2, 2, 3, 3) はどれも、4個をとる重複順列の例です。このような重複順列の総数は、次のようになります。

$$n^k.$$

例題

1. 数字 {2, 4, 6, 8} から、同じ数字をくり返して使ってもよいとき、6けたの数はいくつつくれるでしょうか。公式に代入するだけです。集合の要素は4個で、6個を並べます。

   $$4^6=4096.$$

2. コンピュータでは、ふつう2進法、つまり数字0と1だけを使う記数法が使われます。そこでは新しい単位が使われます。たとえば1ビットは、0か1のどちらかを入れる1つのマスのようなものです。もっと大きな単位がバイトで、8ビットからなります。つまり、1は1ビット、01110001は1バイトです。1バイトを8ビットでうめる方法は何通りあるでしょうか。

   集合 {0, 1}、つまり2つの要素から選びます。並べる個数は k = 8 なので、k 個の並びの総数は次のとおりです。

   $$2^8=256.$$

3. 前の例から、1バイトで256通りの値を区別できることがわかりました。4バイトをうめる方法は何通りあるでしょうか。

   4バイトには 4 · 8 = 32 ビットがあり、選ぶのはやはり2個の要素からなる集合からです。したがって、答えは次のとおりです。

   $$2^{32}=\mathrm{4,294,967,296.}$$

   わずか4バイトで、40億をこえる値を区別できることがわかります。参考までに、いまのコンピュータのディスクの大きさは数百ギガバイト、あるいは数テラバイトです。1テラバイトは 1,000,000,000,000 バイト、つまり 8,000,000,000,000 ビットです。そのため、1テラバイトのディスクには、2^{8,000,000,000,000} 通りもの異なる値を保存できます。

   注：現在、キロバイト（メガバイトなど）という言葉の意味には少し混乱があります。技術的な理由から、1キロバイトは、ほかの単位のように（1キログラムは1000グラムです）1000バイトではなく、2¹⁰ バイト、つまり 1024 バイトとされていました。1メガバイトは 2²⁰ バイト、つまり 2¹⁰ キロバイトでした。

   そこで現在は、2つの書き方を区別しています。1 kB（キロバイト）は1000バイト、1 KiB（キビバイト）は 2¹⁰ = 1024 バイトです。

4. ほかの例は、パスワードの安全性の記事にあります。