例えば,A, B, C, D, E, Fの6文字を一列に並べてできる文字列の数は$6!$通りあります.このことは以前の順列の記事で説明しましたね.
それではA, A, A, A, B, Bの6文字を一列に並べてできる文字列の数はどれくらいあるでしょうか?
この場合の数は単純に$6!$通りではなく,もっと少なくなります.このように,同じ文字を含む順列では単純に考えるだけでは場合の数は得られません.
「同じものを含む順列」は
- 重複で割る考え方
- 組み合わせの考え方
の2つの考え方があります.
「重複で割る考え方」の方が計算は楽ですが,考え方を理解しやすいのは「組み合わせの考え方」でしょう.
「同じものを含む順列」は実際の問題でも頻繁に出題されるので,しっかり理解しておいてください.
一連の記事はこちら
【場合の数1|[和の法則]と[積の法則]は超アタリマエ!】
【場合の数2|[順列]のnPrの考え方と公式は超カンタン!】
【場合の数3|実はカンタンな円順列と数珠順列の考え方】
【場合の数4|[組み合わせ]のnCrの求め方から性質まで攻略】
【場合の数5|同じものを含むと順列の場合の数はどう変わる?】←今の記事
【場合の数6|[重複組み合わせ]は2パターンでOK!】
【場合の数7|二項定理を理解しよう!場合の数を使って導出!】
【場合の数8|展開が楽にできる「パスカルの三角形」の考え方】
【場合の数9|多項定理とは?実は二項定理と同じ考え方!】
考え方1
まずは「重複で割る」という考え方で「同じものを含む順列」をみてみましょう
例題
- 2枚のカード$\fbox{A}$,3枚のカード$\fbox{B}$の合計5枚のカードを一列に並べてできる並びは全部で何通りか.
- 3枚のカード$\fbox{A}$,2枚のカード$\fbox{B}$,4枚のカード$\fbox{C}$,3枚のカード$\fbox{D}$の合計12枚のカードを一列に並べてできる並びは全部で何通りか.
(1) まず全てのカードを区別し,
- カード$\fbox{A}$を$\fbox{A1}$, $\fbox{A2}$
- カード$\fbox{B}$を$\fbox{B1}$, $\fbox{B2}$, $\fbox{B3}$
とすると,普通の順列の考え方ができるのでカードの並びは全部で$5!$通りありますね.
ここでカード$\fbox{A}$の区別をなくすことを考えます.たとえば,
- $\fbox{A1}\fbox{A2}\fbox{B1}\fbox{B2}\fbox{B3}$→$\fbox{A}\fbox{A}\fbox{B1}\fbox{B2}\fbox{B3}$
- $\fbox{A1}\fbox{B2}\fbox{A2}\fbox{B3}\fbox{B1}$→$\fbox{A}\fbox{B2}\fbox{A}\fbox{B3}\fbox{B1}$
- $\fbox{B3}\fbox{B2}\fbox{A2}\fbox{B1}\fbox{A1}$→$\fbox{B3}\fbox{B2}\fbox{A}\fbox{B1}\fbox{A}$
ですね.
さて,カード$\fbox{A}$に区別があるときは,
- $\fbox{A1}\fbox{A2}\fbox{B1}\fbox{B2}\fbox{B3}$
- $\fbox{A2}\fbox{A1}\fbox{B1}\fbox{B2}\fbox{B3}$
は違うものですが,カード$\fbox{A}$の区別をなくせばどちらも$\fbox{A}\fbox{A}\fbox{B1}\fbox{B2}\fbox{B3}$になりますね.
カード$\fbox{A1}$と$\fbox{A2}$の並べ替えは$2!$通りあるので,カード$\fbox{A}$の区別をなくすことで同じ並びになるものは$5!$通りの中に$2!$通りずつあることになります.
同様にカード$\fbox{B}$の重複をなくして同じ並びになるものは,$8!$通りの中に$3!$通りずつあります.
よって,求める場合の数は
となります.
(2) 全てのカードを区別して考えると,カードの並びは全部で$12!$通りあります.
カード$\fbox{A}$,カード$\fbox{B}$,カード$\fbox{C}$,カード$\fbox{D}$の区別をなくすことで同じ並びになるものはそれぞれ$3!$, $2!$, $4!$, $3!$通りあるから,求める場合の数は
となります.
(1)は考え方を見るために丁寧に解きましたが,実際には(2)のようにパッと解くことができます.
公式
同じ考え方で以下の公式が得られます.
$\mrm{A}_1$, $\mrm{A}_2$,……,$\mrm{A}_n$がそれぞれ$r_1$個,$r_2$個,……,$r_n$個あるとき,これらの並べ方の総数は
である.
$\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$通りあるから,重複で割って
が求める並べ方の総数となります.
同じものが含まれるときの順列は,一度全て区別して順列を考え,そのあと区別をなくして重複の個数で割ればよい.
考え方2
さて,先ほどと同じ問題を別の考え方で解いてみましょう.
例題
- 2枚のカード$\fbox{A}$,3枚のカード$\fbox{B}$の合計5枚のカードを一列に並べてできる並びは全部で何通りか.
- 3枚のカード$\fbox{A}$,2枚のカード$\fbox{B}$,4枚のカード$\fbox{C}$,3枚のカード$\fbox{D}$の合計12枚のカードを一列に並べてできる並びは全部で何通りか.
(1) カードを並べる場所は全部で5ヶ所あるので,カード$\fbox{A}$を並べる場所を選ぶ場合の数は$\Co{5}{2}$です.
カード$\fbox{A}$を並べる場所を決めれば,カード$\fbox{B}$を並べる場所は決まりますから,求める場合の数は
となります.
(2) カードを並べる場所は全部で12ヶ所あるので,最初にカード$\fbox{A}$を並べる場所を選ぶ場合の数は$\Co{12}{3}$です.
次に残った9ヶ所にカード$\fbox{B}$を並べることになるので,カード$\fbox{B}$を並べる場所を選ぶ場合の数は$\Co{9}{2}$です.
同様に,次にカード$\fbox{C}$を並べる場所の場合の数は$\Co{7}{4}$で,ここまで決めればカード$\fbox{D}$を並べる場所は決まります.
よって,求める場合の数は
となります.
理解するが簡単なのは,おそらくこちらでしょう.
しかし,(結局は「考え方1」の式と等しくなりますが,)種類が多くなればなるほど$\Co{n}{r}$が増えるので計算は面倒になります.
公式
今の考え方と同じようにして,以下の公式が得られます.
$\mrm{A}_1$, $\mrm{A}_2$,……,$\mrm{A}_n$がそれぞれ$r_1$個,$r_2$個,……,$r_n$個あるとき,これらの並べ方の総数は
である.
カードを並べる場所は$(r_1+r_2+\dots+r_n)$ヶ所あるので,最初に$\mrm{A}_1$を並べる場所を選ぶ場合の数は$\Co{r_1+r_2+\dots+r_n}{r_1}$です.
ここで,$\mrm{A}_1$を並べて残った$(r_2+\dots+r_n)$ヶ所に$\mrm{A}_2$を並べることになるので,カード$\mrm{A}_2$を並べる場所を選ぶ場合の数は$\Co{r_2+\dots+r_n}{r_2}$です.
これを$\mrm{A}_{n-1}$まで繰り返せば,$\mrm{A}_n$を並べる位置は決まります.
よって,
が求める並べ方の総数となります.
2つの考え方の関係
2つの考え方で得られた公式の見た目は違いますが,計算すると等しいことが証明できます.
まず,$\Co{n}{r}$は
と表されるのでした.これについては以下の記事を参照してください.
【前回の記事:場合の数4|[組み合わせ]のnCrの求め方から性質まで攻略】
$n$個のものから$r$個選ぶ場合の数を$\Co{n}{r}$と表します.これを「組み合わせ」といいますが,$\Co{n}{r}$の表し方は「並べて表す方法」と「階乗を使う方法」の2通りあります.どちらも非常に重要なので,しっかりフォローしてください.
このことから,
と計算でき,2つの公式が等しいことが証明できました.最後の等号でバサバサと約分されていますね.
次の記事で説明する「重複組み合わせ」はこの「同じものを含む順列」を使うので,「同じものを含む順列」はしっかり理解しておいてください.
[同じものを含む順列]の考え方は,「重複で割る方法」と「組み合わせを使う方法」の2通りある.当然,どちらも同じ答えが得られる.
【次の記事:場合の数6|[重複組み合わせ]は2パターンでOK!】
「A,B,Cの3種類で7文字の列を作る場合の数」などは「重複組み合わせ」を使って考える典型的な問題です.「重複組み合わせ」の問題では,
- 使わない種類のものがあってもよいパターン
- 使わない種類のものがあってはならないパターン
の2つのパターンがあります.これらで考え方が異なりますが,どのような違いか理解しておけば間違えることはありません.