同じものを含む順列

方針

解答

⓪ 発想 — どう考え始めるか。 $6$ 文字を並べるだけなら $6!=720$ 通り。しかし $\mathrm{A}$ が $3$ つ、$\mathrm{B}$ が $2$ つ同じ文字だ。

$3$ つの $\mathrm{A}$ にこっそり番号をつけて ${\mathrm{A}}_1,{\mathrm{A}}_2,{\mathrm{A}}_3$ と区別すれば $720$ 通り。でも番号を消すと、$\mathrm{A}$ の並べ替え $3!=6$ 通りは全部同じ見た目になる。

つまり $720$ は、同じ並びを $3!\times 2!$ 回ずつ数えている。だから割る。

$$\frac{6!}{3!\times 2!}=\frac{720}{6\times 2}=60$$

分母は足し算ではなく掛け算($3!+2!=8$ で割るのは誤り)。$\mathrm{A}$ の重複と $\mathrm{B}$ の重複は独立に起きているので、重複の総数は積になるからだ。

6文字が全部違うなら $6!=720$ 通り。でも実際はAが3個、Bが2個ある。

同じAどうしや、同じBどうしを入れ替えても並びは変わらない。そのぶん、同じ並びを何回もダブって数えている。

Aの3個の並べ替え $3!$ 通り、Bの2個の並べ替え $2!$ 通りが、それぞれ同じ並びを表す。だからこれらで割る。

$$\frac{6!}{3!\times 2!}=\frac{720}{6\times 2}=\frac{720}{12}=60(\text{通り})$$

Cは1個なので $1!=1$ で割ることになり、影響しない(書かなくてよい)。分母は「同じ文字ごとに、その個数の階乗をかけ合わせたもの」だ。A用の $3!$、B用の $2!$ をかける。

まとめ:別の見方もできる。6か所のうちAを置く3か所を選び(${}_6{\mathrm{C}}_3$)、残り3か所からBを置く2か所を選ぶ(${}_3{\mathrm{C}}_2$)、最後の1か所にCを置く、と考えても ${}_6{\mathrm{C}}_3\times {}_3{\mathrm{C}}_2=20\times 3=60$ で同じになる。

発展 — 一歩先へ。 $\frac{n!}{p!q!r!}$ という数は多項係数と呼ばれ、二項係数 ${}_n{\mathrm{C}}_r=\frac{n!}{r!(n-r)!}$ の自然な拡張になっている(グループが $2$ つなら二項、$3$ つ以上なら多項)。

これは $(a+b+c{)}^6$ を展開したときの $a^3{b}^{2}c$ の係数でもある。$6$ 個の $(a+b+c)$ から、どの $3$ 個で $a$ を、どの $2$ 個で $b$ を選ぶか — 文字の並べ方と、展開の係数が同じ数なのだ。実際、その係数はぴったり $60$ になる。

日常の言葉で言えば、この数は「$6$ 個のものを、$3$ 個・$2$ 個・$1$ 個の名前つきグループに分ける方法の数」である。トランプを配る、チームを分ける、荷物を仕分ける — 現実の分配問題は、たいていこの形をしている。

なお「$6$ 人を $3$ 人・$2$ 人・$1$ 人の名前のない組に分ける」なら話が変わる。組に区別がないと、さらに割る必要が出てくる場合があるからだ(同じ人数の組が複数あるとき)。「区別があるか、ないか」— 場合の数は、最後までこの問いに尽きる。

別解

割り算を使わず、「どの場所に置くか」を選んでいくやり方がある。こちらのほうが、じつは直感的かもしれない。

発想の転換。 「文字を並べる」のではなく、「$6$ つの席のうち、どの席に $\mathrm{A}$ を座らせるか」を選ぶと考える。

$$\underline{1}\underline{2}\underline{3}\underline{4}\underline{5}\underline{6}$$

手順1: $6$ 席から、$\mathrm{A}$ の $3$ 席を選ぶ。

$\mathrm{A}$ は $3$ つとも同じ文字だから、どの $\mathrm{A}$ がどこか、は気にしなくてよい。ただ「$3$ 席を選ぶ」だけ。

$${}_6{\mathrm{C}}_3=\frac{6\times 5\times 4}{3\times 2\times 1}=20(\text{通り})$$

手順2: 残り $3$ 席から、$\mathrm{B}$ の $2$ 席を選ぶ。

$${}_3{\mathrm{C}}_2=3(\text{通り})$$

手順3: $\mathrm{C}$ は、残った $1$ 席に入るしかない。

$${}_1{\mathrm{C}}_1=1(\text{通り})$$

掛け合わせる。

$$20\times 3\times 1=60(\text{通り})$$

割り算を $1$ 度も使わずに、同じ $60$ にたどり着いた ✓。

この方法の何がいいか。 「同じものだから割る」という引け目のある操作が消える。同じ文字はもともと区別しないまま、席だけを選んでいるからだ。「$720$ 通りを一度作ってから、重複を割って消す」より、「最初から重複を作らない」ほうが気持ちがいい。

そして、この見方は次の問題(最短経路)に直結する。 「右へ $4$ 回・上へ $3$ 回、合わせて $7$ 回の移動のうち、どの $3$ 回を『上』にするか」— まさに席選びそのものだ。

同じものを含む順列は、じつは組合せだった。 一般に

$$\frac{n!}{p!q!r!}={}_n{\mathrm{C}}_p\times {}_{n-p}{\mathrm{C}}_q\times \cdots$$

「割り算の式」と「選び方の積」は同じものである。どちらで計算してもよいが、意味が見えるのは後者だ。