隣り合う・隣り合わない順列

方針

解答

⓪ 発想 — どう考え始めるか。 「隣り合う」と言われたら、$2$ 人を $1$ つのかたまりにする。これがこの型の第一手だ。

女子 $2$ 人をひもで縛って $1$ 人ぶんの荷物にすれば、並べるのは「男子 $3$ 人 $+$ 女子のかたまり」の $4$ 個になる。その並べ方は $4!$ 通り。

そして、かたまりの中でも $2$ 人が入れかわれる($\mathrm{女}1\mathrm{女}2$ と $\mathrm{女}2\mathrm{女}1$)。この $2!$ を掛け忘れるのが最頻ミスだ。

$$4!\times 2!=24\times 2=48$$

(2)の「隣り合わない」は、直接数えると場合が散らばって数えにくい。そこで全体から「隣り合う」を引く。

$$5!-48=120-48=72$$

数えにくいほうは、反対を数えて引く。

(1) 女子2人をひもで結んで、1つのかたまりだと思う。すると並べるものは「男子3人 + 女子のかたまり」の4つになる。この4つの並べ方は $4!=24$ 通り。

さらに、かたまりの中で女子2人の並ぶ順が $2!=2$ 通りある。両方かけて

$$4!\times 2!=24\times 2=48(\text{通り})$$

かたまりの中の $2!$ をかけ忘れるのが、いちばん多いミスだ。「かたまりにしたら、中の並びも数える」とセットで覚えよう。

(2) 「隣り合わない」を最初から数えようとすると、場合が多くて大変だ。そこで、全部の並べ方から「隣り合う」場合を引く。

全部の並べ方は $5!=120$ 通り、隣り合うのは(1)の48通りだから

$$120-48=72(\text{通り})$$

まとめ:「隣り合わない = 全部 − 隣り合う」と裏返して数えるのがコツだ。正面から数えるのが大変なときは、反対側から数えられないか考えてみよう。

発展 — 一歩先へ。 すきま法は「$n$ 人並べたら、すきまは $n+1$ か所」という単純な事実の上に立っている。この $+1$(両端のぶん)を落とすかどうかが勝負の分かれ目だ。

一般化してみよう。男子 $m$ 人、女子 $f$ 人が誰も隣り合わないように並べるには

$$m!\times {}_{m+1}{\mathrm{P}}_f$$

そしてこの式は $f>m+1$ のとき $0$ になる(すきまの数より女子が多ければ、どうやっても隣り合ってしまう)。${}_4{\mathrm{P}}_5$ のような記号は定義されない — 式が「不可能」を自動的に教えてくれるわけだ。

たとえば男子 $2$ 人・女子 $4$ 人では、すきまは $3$ か所しかないので、女子 $4$ 人を別々に入れることはできない。鳩の巣原理(巣より鳩が多ければ、どこかに $2$ 羽入る)そのものである。

数え上げの式は、単に数を出すだけでなく「そもそも可能か」まで語る。 答えが $0$ になったり、記号が定義できなくなったりしたときこそ、問題の構造が見えている瞬間だ。

別解

(2)は引き算に頼らず、直接数えることもできる。「隣り合わない」を積極的に作りにいく方法で、すきま法と呼ばれる。人数が増えたときはこちらのほうが強い。

手順1: まず、じゃまにならない男子だけを並べる。

男子 $3$ 人を $1$ 列に並べる。

$$3!=6(\text{通り})$$

手順2: 男子の「すきま」を数える。

男子が $3$ 人並ぶと、女子が入れる場所は男子と男子のあいだ、および両端である。

$$\underline{}\text{男}\underline{}\text{男}\underline{}\text{男}\underline{}$$

下線の場所は $4$ か所ある($3$ 人の両側で $3+1=4$)。

手順3: すきまに女子を入れる。

女子は別々のすきまに入れる。 そうすれば、女子どうしのあいだに必ず男子が $1$ 人以上いるので、絶対に隣り合わない。

$4$ か所のすきまから $2$ か所を選び、そこに女子 $2$ 人を並べる(どちらの女子がどちらのすきまか、で区別がつく)。

$${}_4{\mathrm{P}}_2=4\times 3=12(\text{通り})$$

手順4: 掛ける。

$$6\times 12=72(\text{通り})$$

引き算のルートと同じ答えだ ✓。

すきま法の何が強いのか。 「隣り合わない」人が $3$ 人以上になると、引き算のルートは急に難しくなる。「少なくとも $2$ 人が隣り合う」を引こうとすると、$2$ 人だけ隣り合う場合と $3$ 人固まる場合が重なって、包除原理が必要になるからだ。

一方すきま法なら、人数が増えても手順は同じ。男子 $5$ 人・女子 $3$ 人が隣り合わないなら、$5!\times {}_6{\mathrm{P}}_3$ — すきまが $6$ か所になるだけである。

「隣り合う」ならかたまり、「隣り合わない」ならすきま。 $2$ つの型をセットで覚えておくと、この手の問題はすべて片づく。そして引き算のルートと突き合わせて検算する — $2$ つの道が同じ数に着けば、まず間違いない。