なかけんの数学ノート

【標準】重複順列

ここでは、「同じものを何度も登場させていい」という条件のもとで、1列に並べる方法の総数を考えます。

[広告]

重複順列

例題1
3個の数字 $1,2,3$ を使って4桁の整数を作るとき、数字は何個できるか。ただし、同じ数字を何度使ってもよく、使っていない数字があってもよい。

【標準】整数はいくつできるかのように、今までは「同じものを2回以上使えない」という条件が付いていました。ここでは、「同じものを2回以上使ってもいい」という条件に変わっています。これによって、数え方はどう変わるでしょうか。

基本的な数え方である、樹形図での書き出しについて考えてみましょう。まず、千の位が3通りあります。枝が3本できます。そのそれぞれの枝に対して、百の位が3通りあります。同じ数字を使っていいので、2通りではなく3通りです。なので、また3本の枝ができます。同様に、十の位も3通り、一の位も3通りです。以上から\[ 3^4=81 \]通りと求められます。

このように、重複を許して(「重複してもいい」という意味)1列に並べる順列を、重複順列(repeated permutation)といいます。この並べ方の総数は、例題1での考え方を一般化して、次のように書けます。

重複順列
n 個の異なるものから、重複を許して r 個を取り出して1列に並べる重複順列の総数は、 $n^r$ 通り。

重複が許されない場合に比べて、式は簡単になりますね。

重複順列っぽくない重複順列

一見、重複順列ではないように見えて、実は重複順列、という例をいくつか見てみましょう。

例題2
4人がじゃんけんをするとき、出し方は何通りあるか。

重複順列っぽくないですよね。というか、順列っぽくもないです。しかし、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ケタの整数を作る問題」と同じ構造をしていることがわかります。

例題3
4人を、松の間、竹の間、梅の間の3つの部屋に分ける場合、何通りの分け方があるか。ただし、誰もいない部屋があってもよいものとする。

この4人を A, B, C, D さんと名付けるとすると、Aさんは、松・竹・梅の3通り。Bさんも3通り、CさんもDさんも3通りずつあります。それぞれ3通りずつあるので\[ 3^4=81 \]通り、となります。

これも設定が違うだけで、例題1や例題2と同じ構造をしています。「3つの異なるものから、重複を許して4つを取り出して1列に並べる」という構造ですね。

部分集合の数

最後に、また少し変わった問題を考えてみます。

例題4
集合 $\{1,2,3\}$ の部分集合は、全部でいくつあるか。

部分集合というのは、それに含まれる集合ということです。忘れやすいですが、自分自身と空集合も、部分集合に含まれます。詳しくは、【基本】部分集合に載っています。

さて、まずは、実際にかきだしてみましょう。モレがないように、個数が少ない方から書いていきます。
\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}$ 個になる、というのも、同様に考えればすぐにわかるでしょう。

おわりに

ここでは、重複を許して並べる重複順列を見ました。また、重複順列っぽくないものの、重複順列と考えて解ける例をいくつか見ました。設定が違っても同じ構造であるケースや、視点を変えると考えやすくなるケースを見ました。

いろんな例を見て、柔軟に考えられるようになっていきましょう。

[広告]
対象者: 数学A
分野: 場合の数と確率
トピック: 場合の数
レベル: 標準
キーワード: 場合の数
更新日:2017/02/02