重複順列について

重複順列$_{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\]

と計算できる.

重複順列の計算練習

次の値を求めよ.

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

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

重複順列~その1~

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

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

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

    \[_{7}\mathrm{P}_{3}=\boldsymbol{210}通り\]
  3. 3つの場所それぞれ,7通りの色が選べる. つまり,7つのものから繰り返しを許して3つ並べる重複順列となり
  4. \[_{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の両方を含むものは何通りあるか.

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$ 包含と排除の原理

通り