同じものを含む順列
同じものを含む順列C(n1,n2,⋯,nm)の定義
例えば,6枚のカード A,A,A,B,B,C を1列に 並べる順列の総数は次のように求めることができる.ただし,ここでは A の3枚や, B の2枚の並べ方の違いは区別しないものとする.
まず,カードを並べるための“部屋”を先に6つ用意しておく.
3枚の A の入れる部屋の選び方は 6C3 通りあり, その選んだ部屋に A を入れる.
そのそれぞれに対し,残りの部屋は3部屋であるから,2枚の B の入れる部屋の選び方は 3C2 通りあり,その選んだ部屋に B を入れる.
そのそれぞれに対し,残りの部屋は1つであるから,最後に C を入れる.
以上から,6枚のカード A,A,A,B,B,C を1列に 並べる順列の総数は積の法則より
6C3× 3C2× 1C1=6⋅5⋅43⋅2⋅1×3⋅22⋅1×11=60∴60通り
となる.
ここで,数個の区別しないものを含む n 個の順列を定義しておこう.
同じものを含む順列 C(n1,n2,⋯,nm) の定義
第 i 種 (1≦ のものが n_i 個ずつ全部で n_1+n_2+\cdots+n_m=n 個あり,同種のものは区別しないものとするとき, これら n 個を1列に並べた順列のことを,
同じものを含む順列
または,
一般順列(generalized permutation)
といい,その総数を FTEXT では \text{C}(n_1,~n_2,~\cdots,~n_m) と表す.
例えば, a が3個, b が2個, c が1個の計6個の同じものを含む順列の総数は, \text{C}(3,~2,~1) である.
この例より, \text{C}(3,~2,~1)=60 である.
同じものを含む順列\text{C}(n_1,n_2,\cdots,n_m)の計算
今みた例と同じように,一般の \text{C}(n_1,~n_2,~\cdots,~n_m) も,以下のように考えることができる.
まず,カードを並べるための場所を先にn個用意しておく.
n_1 個の同種のものの入れる場所の選び方は _{n}\mathrm{C}_{n_1} 通りあり,またそのそれぞれに対して n_2 個の同種のものの入れる場所の選び方は _{n-n_1}\mathrm{C}_{n_2} 通りあり,またそのそれぞれに対して n_3 個の同種のものの入れる場所の選び方は _{n-n_1-n_2}\mathrm{C}_{n_3} 通りあり, \cdots ,またそのそれぞれに対して n_m 個の同種のものの入れる場所の選び方は _{n-n_1-n_2-…-n_{m-1}}\mathrm{C}_{n_m} 通りある.
以上から,同じものを含む n 個の順列は,積の法則から
\begin{align} &\ \text{C}(n_1,~n_2,~\cdots,~n_m)\\ =&\ _{n}\mathrm{C}_{n_1}\times\ _{n-n_1}\mathrm{C}_{n_2}\times\ _{n-n_1-n_2}\mathrm{C}_{n_3}\\ &\qquad\qquad\times\cdots\times\ _{n-n_1-n_2-\cdots-n_{m-1}}\mathrm{C}_{n_m} \end{align}となる.
まとめると
同じものを含む順列 \text{C}(n_1,n_2,…,n_m) の計算
第 i 種 (1\leqq{i}\leqq{m}) のものが n_i 個ずつ全部で n_1+n_2+\cdots+n_m=n 個あり,同種のものは区別しないときの 同じものを含む順列の総数 \text{C}(n_1,n_2,\cdots,n_m) は
\begin{align} &\ \text{C}(n_1,~n_2,~\cdots,~n_m)\\ =&\ _{n}\mathrm{C}_{n_1}\times\ _{n-n_1}\mathrm{C}_{n_2}\times\\ &\qquad\cdots\times\ _{n-n_1-\cdots{n}_{m-1}}\mathrm{C}_{n_m}\tag{1}\label{Cnokeisan1}\\ =&\ \frac{n!}{(n-n_1)!n_1!}\\ &\times\frac{(n-n_1)!}{(n-n_1-n_2)!n_2!}\times\\ &\cdots\times\frac{(n-n_1-\cdots-n_{m-1})!}{0!n_m!}\\ =&\ \frac{n!}{n_1!n_2!n_3!\cdots n_m!}\tag{2}\label{Cnokeisan2} \end{align}と計算できる.
例えば, a が3個, b が2個, c が1個の計6個の順列の総数は \eqref{Cnokeisan1} を用いて
\begin{align} \text{C}(3,2,1)=&\ _{6}\mathrm{C}\ _{3}\times\ _{6-3}\mathrm{C}_{2}\times\ _{6-3-2}\mathrm{C}_{1}\\ =&\ _{6}\mathrm{C}_{3}\times\ _{3}\mathrm{C}_{2}\times\ _{1}\mathrm{C}_{1}=60 \end{align}または, \eqref{Cnokeisan2} を用いて
\begin{align} \text{C}(3,~2,~1) =&\frac{6!}{3!2!1!}=60 \end{align}と計算できる.
上の \eqref{Cnokeisan2} , \text{C}(n_1,~n_2,~\cdots,~n_m)=\dfrac{n!}{n_1!n_2!n_3!\cdots n_m!} は,ただ計算の上でいえるだけでなく
「 n 個のものすべてを区別した n! 通りの順列のうち,同種の n_1,n_2,\cdots,n_m 個 の並び替えについては同一視するため, n_1!n_2!\cdots n_m! 通りで一まとめにして数えたもの」
と考えることもできる.
同じものを含む順列
- 1,1,1,2,2,3,3 の7つの数字を一列に並び替えるとき,何通りの並べ方があるか.
- SUUGAKUAを並び替えるとき,何通りの並べ方があるか.
- 1を3つ,2を2つ,3を2つ含むから \begin{align} \text{C}(3,~2,~2)=&\ _{7}\mathrm{C}_{3}\times\ _{7-3}\mathrm{C}_{2}\cdot\ _{7-3-2}\mathrm{C}_{2}\\ =&\ _{7}\mathrm{C}_{3}\times\ _{4}\mathrm{C}_{2}\times\ _{2}\mathrm{C}_{2}=\boldsymbol{210} \end{align}
- Uを3つ,Aを2つ,S,G,Kをそれぞれ1つ含むから \begin{align} &\ \text{C}(3,~2,~1,~1,~1)\\ =&\ _{8}\mathrm{C}_{3}\cdot\ _{8-3}\mathrm{C}_{2}\cdot\ _{8-3-2}\mathrm{C}_{1}\\ &\qquad\cdot\ _{8-3-2-1}\mathrm{C}_{1}\cdot\ _{8-3-2-1-1}\mathrm{C}_{1}\\ =&\ _{8}\mathrm{C}_{3}\times\ _{5}\mathrm{C}_{2}\times\ _{3}\mathrm{C}_{1}\times\ _{2}\mathrm{C}_{1}\times\ _{1}\mathrm{C}_{1}\\ =&\ \boldsymbol{3360} \end{align}
∴210通り
《別解》
\text{C}(3,~2,~2)=\dfrac{7!}{3! 2! 2!}=\boldsymbol{210} 通り
∴3360通り
《別解》
\begin{align} \text{C}(3,~2,~1,~1,~1)=&\ \frac{8!}{3! 2! 1! 1! 1!}\\ =&\ \boldsymbol{3360}通り \end{align}