重複順列

カード引きでは、1回目に引く場合と2回目に引く場合では状況が異なるが、さいころ投げでは1回目に出る目と2回目に出る目に全体として変化が無い。さいころ投げで順序を考慮する場合には、下でみるように重複順列を考えることになる。

ボール・箱	単射	写像全て	全射
あり・あり	順列	重複順列	部屋割り
なし・あり	組合せ	重複組合せ	資源配分
あり・なし		（右枠の和）	部屋割り（区別なし）
なし・なし		（右枠の和）	資源配分（区別なし）

重複順列について

重複順列 $_{n}\Pi_{r}$ の定義

無題

例えば，の目が描いてある正四面体のさいころを2回振って，出た目を順に 1列に並べる場合の数は次のように求めることができる．

まず，1回目のさいころの目の出方は4通りある．

そして，2回目のさいころの目の出方も4通りある．

つまり，1回目の目の出方4通りに対して，2回目の目の出方も4通りに定まるから，さいころを2回振ったときの目の出方は積の法則より

$4\times4=16通り$

となる．

右の図は，さいころを2回振ったときの目の出方16通りを樹形図を用いて表したものである．

ここで， $n$ 個のものから，繰り返し用いることを許して， $r$ 個とって並べる場合の順列を定義しておこう．

重複順列 $_{n}\Pi_{r}$ の定義

（無題）

「区別する $n$ 個のものから，繰り返し用いることを許して， $r$ 個取り出して1列に並べた列」のことをn-r重複ちょうふく順列(permutation with repetitions)といい，その並べ方の総数を $\boldsymbol{_{n}\Pi_{r}}$ と表す

この例では， $_{4}\Pi_{2}=4\times4=16$ である．

重複順列 $_{n}\Pi_{r}$ の計算

区別する $n$ 個のものから，繰り返し用いることを許して， $r$ 個取り出して1列に並べる順列の数 $_{n}\Pi_{r}$ も，先程の例と同じように考えることができる．

まず，1番目のものの取り方は $n$ 通りあり，2番目のものの取り方もそのそれぞれに対して $n$ 通りあり， 3番目のものの取り方もそのそれぞれに対して $n$ 通りあり， $\cdots$ ， $r$ 番目のものの取り方もそのそれぞれに対して $n$ 通りある．

したがって，積の法則より

$\begin{align} _{n}\Pi_{r}&=\underbrace{n\times{n}\times\cdots\times{n}}_{r個の積}=n^r \end{align}$

と計算できることがわかる．

重複順列 $_{n}\Pi_{r}$ の計算

重複順列 $_{n}\Pi_{r}$ は

$_{n}\Pi_{r}=n^r$

と計算できる．

重複順列の計算練習

次の値を求めよ.

$_{4}\Pi_{2}$
$_{5}\Pi_{2}$
$_{6}\Pi_{3}$
$_{8}\Pi_{4}$

重複順列の計算練習の解答

$_{4}\Pi_{2}=4^2=\boldsymbol{16}$
$_{5}\Pi_{2}=5^2=\boldsymbol{25}$
$_{6}\Pi_{3}=6^3=\boldsymbol{216}$
$_{8}\Pi_{4}=8^4=\boldsymbol{4096}$

重複順列～その1～

7色の絵の具で3つの場所を塗る場合について次の問に答えよ．

同じ色を使わないで塗る方法は何通りあるか．
同じ色を使って塗る方法は何通りあるか．

重複順列～その1～の解答

最初の場所を塗るには7通りの色が選べ，そのそれぞれに対して，

次の場所を塗るには最初に使った絵の具以外の6通りの色が選べ，さらにそのそれぞれに対して，最後の場所を塗るには5通りの色が選べる．つまり，7つのものから3つを選んで並べる順列となり

$_{7}\mathrm{P}_{3}=\boldsymbol{210}通り$

3つの場所それぞれ，7通りの色が選べる．つまり，7つのものから繰り返しを許して3つ並べる重複順列となり

$_{7}\Pi_{3}=7^3=\boldsymbol{343}通り$

ボールと箱のモデル2

無題

例えば， $_{5}\Pi_{3}$ の定義は

「区別する5個のものから，繰り返し用いることを許して，3個とりだして1列に並べるときの並べ方の総数」

であったが，これはボールと箱のモデルを使って

「区別する3個のボールを，区別する5個の箱に配る（何個でもよい）場合の総数」

といいかえることができる．それには，次のように考えるとよい．

準備として，ボールは区別するので番号をつけ，それを①，②，③とし，箱も区別するので番号をつけ，それをとしておく．

まず，ボール①を箱に配ることを考えると，箱は5つあるので5通りの場合がある．

次に，ボール②を箱に配ることを考えると，箱には何個でもボールを入れてよいので，このときも5通りの場合がある．

さらに，ボール③を箱に配ることを考えると，同じように5通りの場合がある．

以上から，ボールの箱への配り方は $5\times5\times5$ 通りあり，これは $_{5}\Pi_{3}$ と一致する．

一般に，次のようにまとめることができる．

重複順列 $_{n}\Pi_{r}$ のボールと箱のモデル

重複順列 $_{n}\Pi_{r}$ はボールと箱のモデルを用いて

「区別する $r$ 個のボールを，区別する $n$ 個の箱に配る（何個でもよい）場合の総数」

と考えることができる．

重複順列～その2～

4桁の電話番号は0000から9999まで10000通りある．このうち，0007や3556のように同じ数字が連続しているものは何通りあるか．また，数字の1と6の両方を含むものは何通りあるか．

重複順列～その2～の解答

10000通りの電話番号を全体集合 $U$ として， $X$ を

$X：同じ数字が連続しているもの$

とおく．まず $\overline{X}$ ，すなわち同じ数字が連続していないものについて考える．

左から順に数字を並べたとき，はじめの数字はなんでもよいので10通りあり，左から2番目の数字は今並べた数字とは同じにならないようにするため9通りある．左から3番目，4番目も同様に9通りあるので

$n(\overline{X})=10\times9^3=7290$

よって

$\begin{align} n(X)=&\ n(U)-n(\overline{X})\\ =&\ 10000-7290\\ =&\ \boldsymbol{2710} \end{align}$

$\blacktriangleleft$ 補集合の要素の個数

通り

また

$A：数字の1を含む$

$B：数字の6を含む$

とおくと， $\overline{A}$ ，すなわち数字の1を含まないものは $9^4$ 通りあり， $\overline{B}$ ，すなわち数字の6を含まないものも同様に $9^4$ 通りあり， $\overline{A}\cap\overline{B}$ ，すなわち数字の1と6を含まないものは $8^4$ 通りあるので

$\begin{align} n(A\cap{B}) =&\ n(U)-n(\overline{A\cap{B}})\\ =&\ n(U)-n(\overline{A}\cup\overline{B}) \\ =&\ n(U)-\\ &\left\{n(\overline{A})+n(\overline{B})-n(\overline{A}\cap{\overline{B}})\right\}\\ =&\ 10000-(9^4+9^4-8^4)\\ =&\ \boldsymbol{974} \end{align}$

$\blacktriangleleft$ 補集合の要素の個数

$\blacktriangleleft$ ド・モルガンの法則

$\blacktriangleleft$ 包含と排除の原理

通り

重複順列

重複順列について

重複順列nΠr_{n}\Pi_{r}の定義

無題

重複順列 nΠr_{n}\Pi_{r} の定義

重複順列nΠr_{n}\Pi_{r}の計算

重複順列 nΠr_{n}\Pi_{r} の計算

重複順列の計算練習

重複順列の計算練習の解答

重複順列～その1～

重複順列～その1～の解答

ボールと箱のモデル2

無題

重複順列 nΠr_{n}\Pi_{r} のボールと箱のモデル

重複順列～その2～

重複順列～その2～の解答

重複順列 $_{n}\Pi_{r}$ の定義

重複順列 $_{n}\Pi_{r}$ の定義

重複順列 $_{n}\Pi_{r}$ の計算

重複順列 $_{n}\Pi_{r}$ の計算

重複順列 $_{n}\Pi_{r}$ のボールと箱のモデル