\({}_n\mathrm{P}_r\) では、異なる\(n\)個のものから異なる\(r\)個を取り出して並べる順列を考えましたが、異なる\(n\)個のものから重複を許して\(r\)個を取り出して並べる順列の総数はどうなるでしょうか。
重複を許すので、同じものを何回選んでもよいことになります。
・重複順列
\(A,B,C\)の1文字が書かれたカードがたくさんあるとします。
これらを同じものを選んでもよいとして5個選んで1列に並べるときその総数は、
\(A,B,C\)の1文字が書かれたカードがたくさんあるとします。
これらを同じものを選んでもよいとして5個選んで1列に並べるときその総数は、
1番目は\(A,B,C\)の3通り
2番目も\(A,B,C\)の3通り
3番目も\(A,B,C\)の3通り
4番目も\(A,B,C\)の3通り
5番目も\(A,B,C\)の3通り
2番目も\(A,B,C\)の3通り
3番目も\(A,B,C\)の3通り
4番目も\(A,B,C\)の3通り
5番目も\(A,B,C\)の3通り
選び方があるので、\(3^5\)(通り)となります。
これを一般化すると、異なる\(n\)個のものから重複を許して\(r\)個を取り出して並べる順列の総数は、1番目も2番目も・・・\(r\)番目も\(n\)通り選び方があるので、
\(n×n×n・・・×n=n^r\)(通り) (左辺は\(n\)が\(r\)個ある)
となります。またこのような順列を、\(n\)個から\(r\)個とる重複順列といいます。
また、\({}_n\mathrm{P}_r\) では、\(n≧r\)という制限がありますが、重複順列では同じものを何回選んでもよいので、\(n<r\)(選ぶ個数が選ばれるものの個数より大きい)であってもよいです。
例のように3個のカードから5個選ぶような場合も可能ということです。
例題を何題かやってみます。
(例題1)
同じ数字を繰り返し用いてもよいとして
(1)\(1,2,3,4\)の4個の数字を用いて3桁の正の整数はいくつできるか。
(2)\(0,1,2,3\)の4個の数字を用いて3桁の正の整数はいくつできるか。
同じ数字を繰り返し用いてもよいとして
(1)\(1,2,3,4\)の4個の数字を用いて3桁の正の整数はいくつできるか。
(2)\(0,1,2,3\)の4個の数字を用いて3桁の正の整数はいくつできるか。
(解答)
(1)
百、十、一の位それぞれ4通りの場合があるので
\(4^3=\)\(64\)(通り)
(1)
百、十、一の位それぞれ4通りの場合があるので
\(4^3=\)\(64\)(通り)
(2)
百の位は\(0\)を除いた3通り、十と一の位は4通りの場合があるので
\(3×4^2=\)\(48\)(通り)
百の位は\(0\)を除いた3通り、十と一の位は4通りの場合があるので
\(3×4^2=\)\(48\)(通り)
(例題2)
集合 \(A=\{a,b,c,d,e\}\) の空集合でない部分集合の個数を求めよ。
集合 \(A=\{a,b,c,d,e\}\) の空集合でない部分集合の個数を求めよ。
(解答)
要素\(a\)が部分集合に属しているかしていないかを考えると2通り
要素\(b,c,d,e\)も同様に属しているか属していないかが2通りずつあるから
すべての要素が選ばれない場合、つまり部分集合が空集合となる場合の1通りを除くと
\(2^5-1=\)\(31\)(個)
要素\(a\)が部分集合に属しているかしていないかを考えると2通り
要素\(b,c,d,e\)も同様に属しているか属していないかが2通りずつあるから
すべての要素が選ばれない場合、つまり部分集合が空集合となる場合の1通りを除くと
\(2^5-1=\)\(31\)(個)
集合\(A\)自身も、\(A\)の部分集合です。
(例題3)
1から5までの番号がついた箱がある。次のような入れ方は何通りあるか。
(1)それぞれの箱に、赤か白の球のうちいずれか1個を入れて、赤球も白球もどれかの箱にはいるように入れる。
(2)それぞれの箱に、赤、白、青の球のうちどれか1個を入れて、どの色の球も必ずどれかの箱にはいるように入れる。
(解答)
(1)
1から5までの箱にそれぞれ赤、白の2通りの場合があると考えます。
そして1種類の球しかはいらない場合、(赤のみ、白のみの2通り)を除きます。
そして1種類の球しかはいらない場合、(赤のみ、白のみの2通り)を除きます。
それぞれの箱に赤か白の球どちらかを1個入れる入れ方は
\(2^5=32\)(通り)
あり、このうち赤球のみ、白球のみしか入らない場合、合計2通りを除くと
\(32-2=\)\(30\)(通り)
\(2^5=32\)(通り)
あり、このうち赤球のみ、白球のみしか入らない場合、合計2通りを除くと
\(32-2=\)\(30\)(通り)
(2)
同様に3個の球のどれかをそれぞれの箱に入れる場合を考えます。(\(3^5\)通り) このうち全種類の球が入らない場合は、①1色の球だけ ②2色の球だけ の場合が考えられれます。②については2色の選び方が 赤白・白青・青赤の3パターンあり、それぞれの場合の数は同じでその数は(1)で求めた値となります。
それぞれの箱に3色の球いずれかを入れる入れ方は
\(3^5\)(通り)
\(3^5\)(通り)
このうち
①1色の球だけが入る場合
赤のみ、白のみ、青のみの \(3\)(通り)
②2色の球だけが入る場合
2色の選び方は、赤白・白青・青赤 の3通りあり、それぞれの入れ方は(1)より30通りなので、全部で \(3×30\)(通り)
赤のみ、白のみ、青のみの \(3\)(通り)
②2色の球だけが入る場合
2色の選び方は、赤白・白青・青赤 の3通りあり、それぞれの入れ方は(1)より30通りなので、全部で \(3×30\)(通り)
以上より求める入れ方は
\(3^5-(3+3×30)=243-93=\)\(150\)(通り)
\(3^5-(3+3×30)=243-93=\)\(150\)(通り)
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。