同じものを含む順列(重複順列)の2つの考え方・求め方

場合の数と確率
場合の数と確率

5枚のカード$\fbox{A}\fbox{B}\fbox{C}\fbox{D}\fbox{E}$を一列に並べてできる文字列の総数は単純な順列なので$5!$通りありますね.

では,次の問題はどうでしょうか?

カード$\fbox{A}$が3枚あり,カード$\fbox{B}$と$\fbox{C}$が1枚ずつある.この合計5枚のカードを一列に並べてできる文字列の総数は全部で何通りか.

この問題のように,同じものを含む順列を重複順列といい,普通の順列よりも場合の数は少なくなります.

この記事では

  • 重複順列の組み合わせを用いる考え方
  • 重複順列の重複で割る考え方

を順に説明します.

重複順列

冒頭の問題を2つの考え方から解きましょう.

(再掲)カード$\fbox{A}$が3枚あり,カード$\fbox{B}$と$\fbox{C}$が1枚ずつある.この合計5枚のカードを一列に並べてできる文字列の総数は全部で何通りか.

考え方1(組み合わせ)

次に組み合わせを用いて解きましょう.

カードを並べる場所は全部で5ヶ所あるから,カード$\fbox{A}$を並べる場所を選ぶ場合の数は$\Co{5}{3}$である.

Rendered by QuickLaTeX.com

カード$\fbox{A}$を並べる場所を決めれば,残りの2ヶ所から1ヶ所選んでカード$\fbox{B}$を並べれば良く,この場合の数は$\Co{2}{1}$である.

Rendered by QuickLaTeX.com

残る$\fbox{C}$の並べる場所は自動的に決まるから,求める場合の数は

    \begin{align*}\Co{5}{3}\times\Co{2}{1}=\frac{5\cdot4\cdot3}{3\cdot2\cdot1}\times\frac{2}{1}=20\end{align*}

である.

$\fbox{C}$は残りの1ヶ所から1ヶ所選ぶと考えれば,求める場合の数は$\Co{5}{3}\times\Co{2}{1}\times\Co{1}{1}$と書いても構いません.$\Co{1}{1}=1$なので,結果は変わりませんね.

考え方2(重複で割る)

まずは「普通の順列で考えてから重複で割る」という考え方で解きましょう.

まず3枚のカード$\fbox{A}$を全て区別し,$\fbox{A1},\fbox{A2},\fbox{A3}$とする.

こうすると,異なる5枚のカード$\fbox{A1},\fbox{A2},\fbox{A3},\fbox{B},\fbox{C}$ができあがるから,これらの順列は$5!$通りある.

この$5!$通りの順列それぞれでカード$\fbox{A}$の区別をなくすと,例えば

  • $\fbox{A1}\fbox{A2}\fbox{A3}\fbox{B}\fbox{C}$
  • $\fbox{A1}\fbox{A3}\fbox{A2}\fbox{B}\fbox{C}$
  • $\fbox{A2}\fbox{A1}\fbox{A3}\fbox{B}\fbox{C}$
  • $\fbox{A2}\fbox{A3}\fbox{A1}\fbox{B}\fbox{C}$
  • $\fbox{A3}\fbox{A1}\fbox{A2}\fbox{B}\fbox{C}$
  • $\fbox{A3}\fbox{A2}\fbox{A1}\fbox{B}\fbox{C}$

はいずれも$\fbox{A}\fbox{A}\fbox{A}\fbox{B}\fbox{C}$となる.

同様に,他の場合でもカード$\fbox{A}$の区別をなくすと,最初の$5!$通りの順列において$3!(=6)$個ずつ同じものができあがる.

よって,求める場合の数は

    \begin{align*}\frac{5!}{3!}=\frac{5\cdot4\cdot3\cdot2\cdot1}{6}=20\end{align*}

である.

一度同じものを全て異なるとみなせば普通の順列の考え方ができ,そのあとに区別をなくせば同じものが同じ個数ずつできるので,その重複分で割れば良いというわけですね.

具体例

いまの問題ではカード$\fbox{A}$のみ2枚以上ありましたが,他のカードも2枚以上になっても考え方は同じです.

カード$\fbox{A}$が3枚あり,カード$\fbox{B}$が2枚あり,カード$\fbox{C}$が2枚ある.この合計5枚のカードを一列に並べてできる文字列の総数は全部で何通りか.

この問題も2つの考え方から解きましょう.

解答1(組み合わせを用いる)

カードを並べる場所は全部で7ヶ所あるから,カード$\fbox{A}$を並べる場所を選ぶ場合の数は$\Co{7}{3}$である.

Rendered by QuickLaTeX.com

残る4ヶ所からカード$\fbox{B}$を並べる場所を選ぶ場合の数は$\Co{4}{2}$である.

Rendered by QuickLaTeX.com

残る$\fbox{C}$の並べる場所は自動的に決まるから,求める場合の数は

    \begin{align*}\Co{7}{3}\times\Co{4}{2}=\frac{7\cdot6\cdot5}{3\cdot2\cdot1}\times\frac{4\cdot3}{2\cdot1}=20\end{align*}

である.

$\fbox{C}$は残りの2ヶ所から2ヶ所選ぶと考えれば,求める場合の数は$\Co{7}{3}\times\Co{4}{2}\times\Co{2}{2}$と書いても構いません.$\Co{2}{2}=1$なので,結果は変わりませんね.

解答2(重複で割る)

まず3種類のカード$\fbox{A}$それぞれで全て区別し,$\fbox{A1},\fbox{A2},\fbox{A3},\fbox{B1},\fbox{B2},\fbox{C1},\fbox{C2}$の順列を考えると,場合の数は$7!$通りある.

ここで,カード$\fbox{A}$の区別をなくすと$3!$通り同じものができ,カード$\fbox{B}$の区別をなくすと$2!$通り同じものができ,カード$\fbox{C}$の区別をなくすと$2!$通り同じものができる.

よって,求める場合の数は

    \begin{align*}\frac{7!}{3!2!2!}=\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{3\cdot2\cdot1\cdot2\cdot1\cdot2\cdot1}=210\end{align*}

である.

重複順列の公式

いまの考え方から以下の公式が得られます.

公式1(組み合わせ)

[重複順列の総数]$\mrm{A}_1,\mrm{A}_2,\dots,\mrm{A}_n$がそれぞれ$r_1$個, $r_2$個, ……, $r_n$個あるとき,これらの並べ方の総数は

    \begin{align*}\Co{r_1+r_2+\dots+r_n}{r_1}\times\Co{r_2+\dots+r_n}{r_2}\times\dots\times\Co{r_{n-1}+r_n}{r_{n-1}}\end{align*}

である.

カードを並べる場所は$(r_1+r_2+\dots+r_n)$ヶ所あるので,最初に$\mrm{A}_1$を並べる場所を選ぶ場合の数は$\Co{r_1+r_2+\dots+r_n}{r_1}$である.

さらに,残る$(r_2+\dots+r_n)$ヶ所に$\mrm{A}_2$を並べる場合の数は$\Co{r_2+\dots+r_n}{r_2}$である.

これを$\mrm{A}_{n-1}$まで同様に繰り返せば,$\mrm{A}_n$を並べる位置が決まり,

    \begin{align*}\Co{r_1+r_2+\dots+r_n}{r_1}\times\Co{r_2+\dots+r_n}{r_2}\times\dots\times\Co{r_{n-1}+r_n}{r_{n-1}}\end{align*}

が求める並べ方の総数である.

公式2(重複で割る)

[重複順列の総数]$\mrm{A}_1,\mrm{A}_2,\dots,\mrm{A}_n$がそれぞれ$r_1$個, $r_2$個, ……, $r_n$個あるとき,これらの並べ方の総数は

    \begin{align*}\frac{(r_1+r_2+\dots+r_n)!}{r_1!r_2!\dots r_n!}\end{align*}

である.

$\mrm{A}_1$, $\mrm{A}_2$, ……, $\mrm{A}_n$を全て区別すると,$(r_1+r_2+\dots+r_n)!$通りの並べ方がある.

$\mrm{A}_k$ ($k=1,\dots,n$)の区別をなくしたときの重複は$n_k$通りあるから,重複で割って

    \begin{align*}\frac{(r_1+r_2+\dots+r_n)!}{r_1!r_2!\dots r_n!}\end{align*}

が並べ方の総数である.

2つの公式は同じ

いまの2つの公式の見た目は違いますが,同じものを数えているので2つの公式は等しくなっているはずですね.

このことは,組み合わせの場合の数$\Co{n}{r}$が

    \begin{align*}\Co{n}{r}=\frac{n!}{r!(n-r)!}\end{align*}

と表されることを思い出すと証明できます.

実際,組み合わせによる公式1から出発すると

    \begin{align*} &\Co{r_1+r_2+\dots+r_n}{r_1}\times\Co{r_2+\dots+r_n}{r_2}\times\dots\times\Co{r_{n-1}+r_n}{r_{n-1}} \\&=\frac{(r_1+r_2+r_3\dots+r_n)!}{r_1!(r_2+r_3\dots+r_n)!}\times\frac{(r_2+r_3\dots+r_n)!}{r_2!(r_3+\dots+r_n)!}\times\dots\times\frac{(r_{n-1}+r_n)!}{r_{n-1}!r_n!} \\&=\frac{(r_1+r_2+\dots+r_n)!}{r_1!r_2!\dots r_n!} \end{align*}

と綺麗に約分されて,重複で割る考え方の公式2と等しいことが分かりますね.

コメント