同じものを含む順列（重複順列）の２つの考え方・求め方

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

では，次の問題はどうでしょうか？

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

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

この記事では

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

を順に説明します．

「場合の数と確率」の一連の記事

重複順列
1. 考え方１（組み合わせ）
2. 考え方２（重複で割る）
具体例
1. 解答１（組み合わせを用いる）
2. 解答２（重複で割る）
重複順列の公式

重複順列

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

（再掲）カード$\fbox{A}$が３枚あり，カード$\fbox{B}$と$\fbox{C}$が１枚ずつある．この合計５枚のカードを一列に並べてできる文字列の総数は全部で何通りか．

考え方１（組み合わせ）

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

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

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

残る$\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}$は残りの１ヶ所から１ヶ所選ぶと考えれば，求める場合の数は$\Co{5}{3}\times\Co{2}{1}\times\Co{1}{1}$と書いても構いません．$\Co{1}{1}=1$なので，結果は変わりませんね．

考え方２（重複で割る）

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

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

こうすると，異なる５枚のカード$\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}$のみ２枚以上ありましたが，他のカードも２枚以上になっても考え方は同じです．

カード$\fbox{A}$が３枚あり，カード$\fbox{B}$が２枚あり，カード$\fbox{C}$が２枚ある．この合計５枚のカードを一列に並べてできる文字列の総数は全部で何通りか．

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

解答１（組み合わせを用いる）

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

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

残る$\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}$は残りの２ヶ所から２ヶ所選ぶと考えれば，求める場合の数は$\Co{7}{3}\times\Co{4}{2}\times\Co{2}{2}$と書いても構いません．$\Co{2}{2}=1$なので，結果は変わりませんね．

解答２（重複で割る）

まず３種類のカード$\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*}$

である．

重複順列の公式

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

公式１（組み合わせ）

［重複順列の総数］$\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*}$

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

公式２（重複で割る）

［重複順列の総数］$\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*}$

が並べ方の総数である．

２つの公式は同じ

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

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

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

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

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

$\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*}$