Processing math: 24%

同じものを含む順列

同じものを含む順列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=654321×3221×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,1,2,2,3,3 の7つの数字を一列に並び替えるとき,何通りの並べ方があるか.
  2. SUUGAKUAを並び替えるとき,何通りの並べ方があるか.

  1. 1を3つ,2を2つ,3を2つ含むから
  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}

    ∴210通り

    《別解》

    \text{C}(3,~2,~2)=\dfrac{7!}{3! 2! 2!}=\boldsymbol{210} 通り

  3. Uを3つ,Aを2つ,S,G,Kをそれぞれ1つ含むから
  4. \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}

    ∴3360通り

    《別解》

    \begin{align} \text{C}(3,~2,~1,~1,~1)=&\ \frac{8!}{3! 2! 1! 1! 1!}\\ =&\ \boldsymbol{3360}通り \end{align}