【標準】重複順列
ここでは、「同じものを何度も登場させていい」という条件のもとで、1列に並べる方法の総数を考えます。
重複順列
【標準】整数はいくつできるかのように、今までは「同じものを2回以上使えない」という条件が付いていました。ここでは、「同じものを2回以上使ってもいい」という条件に変わっています。これによって、数え方はどう変わるでしょうか。
基本的な数え方である、樹形図での書き出しについて考えてみましょう。まず、千の位が3通りあります。枝が3本できます。そのそれぞれの枝に対して、百の位が3通りあります。同じ数字を使っていいので、2通りではなく3通りです。なので、また3本の枝ができます。同様に、十の位も3通り、一の位も3通りです。以上から\[ 3^4=81 \]通りと求められます。
このように、重複を許して（「重複してもいい」という意味）1列に並べる順列を、重複順列(repeated permutation)といいます。この並べ方の総数は、例題1での考え方を一般化して、次のように書けます。
重複が許されない場合に比べて、式は簡単になりますね。
重複順列っぽくない重複順列
一見、重複順列ではないように見えて、実は重複順列、という例をいくつか見てみましょう。
重複順列っぽくないですよね。というか、順列っぽくもないです。しかし、4人が何を出すかを順番に考えていけば、順列そのものです。また、もちろん「あいこ」になってもいいので、重複順列でもあります。
この4人を A, B, C, D さんと名付けるとすると、Aさんの手の出し方は、グー・チョキ・パーの3通り。Bさんも3通り、CさんもDさんも3通りずつあります。それぞれ3通りずつあるので\[ 3^4=81 \]通り、となります。
ちなみに、このグー・チョキ・パーを $1,2,3$ とみなし、 A, B, C, D の出した手をこの順に並べると、さきほどの「4ケタの整数を作る問題」と同じ構造をしていることがわかります。
この4人を A, B, C, D さんと名付けるとすると、Aさんは、松・竹・梅の3通り。Bさんも3通り、CさんもDさんも3通りずつあります。それぞれ3通りずつあるので\[ 3^4=81 \]通り、となります。
これも設定が違うだけで、例題1や例題2と同じ構造をしています。「3つの異なるものから、重複を許して4つを取り出して1列に並べる」という構造ですね。
部分集合の数
最後に、また少し変わった問題を考えてみます。
部分集合というのは、それに含まれる集合ということです。忘れやすいですが、自分自身と空集合も、部分集合に含まれます。詳しくは、【基本】部分集合に載っています。
さて、まずは、実際にかきだしてみましょう。モレがないように、個数が少ない方から書いていきます。
\begin{eqnarray}
\varnothing , \\
\{ 1 \}, \{ 2 \}, \{ 3 \}, \\
\{ 1, 2 \}, \{ 2, 3 \}, \{ 3, 1 \}, \\
\{ 1, 2, 3 \}
\end{eqnarray}数えてみると、8個です。これが答えです。
これでおしまいでもいいのですが、重複順列とからめて考えてみましょう。この答えは $8=2^3$ と変形できます。この式から、何か思いつくことはありませんか。
式から逆に考えると、 $2^3$ は「2つの異なるものから、重複を許して3つを取り出して1列に並べる」ときの並べ方の総数と同じですね。元が3つあるから「3つを取り出して」はわかりますが、「2つの異なるもの」の「2つ」とは何でしょうか。部分集合を作ることと、この「2つ」はどうつながるでしょうか。
実は、部分集合を作るときに、その元が「入るか入らないか」の2つなんですね。例えば、 $\{1,2\}$ という部分集合であれば、「1入る、2入る、3入らない」となるし、 $\{3\}$ なら「1入らない、2入らない、3入る」となります。 $\varnothing$ なら全部「入らない」で、 $\{ 1, 2, 3 \}$ なら全部「入る」です。
「部分集合を作る」というように集合を中心に考えるのではなく、「その元が入るか入らないか」というように元を中心に考えると、 $2^3$ 個だとすぐにわかりますね。もしある集合の元の数が10個なら、その部分集合の数は全部で $2^{10}$ 個になる、というのも、同様に考えればすぐにわかるでしょう。
おわりに
ここでは、重複を許して並べる重複順列を見ました。また、重複順列っぽくないものの、重複順列と考えて解ける例をいくつか見ました。設定が違っても同じ構造であるケースや、視点を変えると考えやすくなるケースを見ました。
いろんな例を見て、柔軟に考えられるようになっていきましょう。
