隣り合わないように並べる - すき間に入れるという発想

「隣り合う」と指定されたら、その 2 人を 1 つの塊とみなして並べます。逆に「隣り合わない」と言われたら、塊を作る手が使えない。

そこで発想を裏返します。関係のないものを先に並べてしまい、できたすき間へあとから入れる。これがすき間法です。

隣り合う場合はまとめる

比較のために、まず隣り合う側を確かめます。5 人が一列に並び、A と B が隣り合う並び方を数える。

A と B を 1 つの塊と見ると、塊 1 つと残り 3 人で 4 つのものを並べることになります。$4!=24$ 通り。

塊の中で A と B が入れ替わるので、さらに $2!=2$ 倍。$24\times 2=48$ 通りになります。

2 人だけなら引き算で足りる

隣り合わない並び方は、全体から隣り合う場合を引けば出ます。

$5!=120$ から 48 を引いて 72 通り。離れてほしいものが 2 つだけなら、この引き算がいちばん速い。

3 つ以上になると引き算が重い

離してほしいものが 3 つ以上あると、事情が変わります。「どれも隣り合わない」の反対は「少なくとも 1 組が隣り合う」で、そこには 2 組が隣り合う場合も含まれる。

そのまま引くと、二重に引いてしまいます。場合分けが枝分かれして、式が長くなる。

こういうときにすき間法が効きます。引き算をせず、最初から条件を満たす並びだけを作る方法です。

すき間法の手順

離す必要のないものを先に並べます。並べたものが $m$ 個あれば、両端を含めて $m+1$ か所のすき間ができる。

そのすき間に、離したいものを 1 つずつ入れていきます。同じすき間へ 2 つ入れなければ、入れたものは決して隣り合わない。

すき間は $m+1$ か所なので、入れるものが $m+1$ 個を超えると並べようがありません。ここが唯一の制限になる。

例：男子 4 人と女子 3 人

男子 4 人と女子 3 人が一列に並びます。女子がどの 2 人も隣り合わない並び方を数える。

まず男子 4 人を並べて $4!=24$ 通り。男子の並びができると、両端を含めて 5 か所のすき間ができます。

5 か所のすき間から 3 か所を選び、そこへ女子 3 人を並べます。女子は区別するので、選ぶだけでなく順序も付く。

$${}_5{\mathrm{P}}_3=5\times 4\times 3=60$$

男子の並び 24 通りのどれについても女子の入れ方が 60 通りなので、掛けて $24\times 60=1440$ 通り。

例：男子 3 人と女子 2 人で答え合わせ

離すものが 2 つの場合は、引き算とすき間法の両方が使えます。値が一致するか確かめる。

引き算で数えます。全体は $5!=120$、女子が隣り合うのは $4!\times 2!=48$ で、差は 72 通り。

すき間法では、男子 3 人で $3!=6$ 通り、すき間 4 か所に女子 2 人で ${}_4{\mathrm{P}}_2=12$ 通り。

$6\times 12=72$ 通りです。両方の道筋が同じ値になった。

例：すき間に入りきらない

男子 2 人と女子 4 人では、女子を全員離せません。

男子 2 人が作るすき間は 3 か所。そこへ女子 4 人を入れると、どこかのすき間に 2 人が入って隣り合います。

答えは 0 通りです。$k\le m+1$ を満たすかどうかを、計算の前に見ておく。

選ぶだけの場合

並べる順序を考えず、番号や席を選ぶだけの問題もあります。こちらは公式の形がすっきりします。

$1$ から $n$ までの番号から $k$ 個を、どの 2 つも連続しないように選ぶ。この選び方の総数は次の式になる^[1]。

$${}_{n-k+1}{\mathrm{C}}_k$$

理由はすき間法と同じです。選ばない $n-k$ 個を先に並べると、すき間が $n-k+1$ か所できる。

そこから $k$ か所を選べば、選んだものはどれも連続しません。番号には順序がすでに付いているので、並べ替えは掛けない。

例：詰めて考える

$1$ から $10$ までから 3 個を、連続しないように選びます。

選んだ数を小さい順に $a_1<a_2<a_3$ とし、$a_1$、$a_2-1$、$a_3-2$ に置きかえる。連続していた分の 1 と 2 を詰める操作です。

置きかえた 3 数は $1$ から $8$ までの中で、ただ大小の順に並ぶだけです。連続してはいけないという条件が消える。

逆向きの操作もできるので、両者はぴったり対応します。したがって答えは ${}_8{\mathrm{C}}_3=56$ 通り。

公式の $n-k+1$ は、この $10-3+1=8$ にあたります。

例：1 から 15 まで 4 個

同じ式に当てはめます。$n=15$、$k=4$ なので $15-4+1=12$。

$${}_{12}{\mathrm{C}}_4=495$$

495 通りです。制限なしの ${}_{15}{\mathrm{C}}_4=1365$ と比べると、3 分の 1 ほどに減っている。

例：同じ色の玉

赤玉 5 個と白玉 3 個を一列に並べます。同じ色どうしは区別せず、白玉が隣り合わない並べ方を数える。

赤玉を先に置くと、すき間が 6 か所。そこから 3 か所を選ぶだけで並びが決まります。

$${}_6{\mathrm{C}}_3=20$$

白玉に区別がないので、順列ではなく組み合わせになる。人を並べる問題との違いはここだけです。

例：円形の席

円卓の 8 席から 3 席を、どの 2 席も隣り合わないように選びます。円では両端がつながるので、直線の公式はそのまま使えない。

特定の 1 席、たとえば 1 番の席を選ぶかどうかで分けます。

1 番を選ぶ場合、両隣の 2 番と 8 番は使えません。残るのは 3 番から 7 番までの 5 席が一列に並んだ形で、そこから 2 席を連続しないように選ぶ。${}_4{\mathrm{C}}_2=6$ 通り。

1 番を選ばない場合、2 番から 8 番までの 7 席が一列に並びます。そこから 3 席を連続しないように選んで ${}_5{\mathrm{C}}_3=10$ 通り。

足して 16 通りです。円は 1 か所で切って直線に直すと扱えます。

例：塊と離す条件が混ざる

数学の本 3 冊、英語の本 2 冊、国語の本 2 冊を並べます。数学の 3 冊は続けて置き、英語の 2 冊は隣り合わないようにする。

まず数学の 3 冊を 1 つの塊とみなします。塊 1 つと国語 2 冊で、3 つのものを並べて $3!=6$ 通り。

この 3 つが作るすき間は 4 か所です。そこへ英語 2 冊を入れて ${}_4{\mathrm{P}}_2=12$ 通り。

最後に塊の中で数学 3 冊を並べ替えて $3!=6$ 通り。全部を掛けて $6\times 12\times 6=432$ 通りになります。

塊を作る操作と、すき間へ入れる操作は同時に使えます。順番としては、塊を作ってから並べ、そのあとすき間を数える。

例：少なくとも 2 つが隣り合う

「どれも隣り合わない」を数えられれば、その反対も出ます。

$1$ から $10$ までから 3 個を選ぶのは ${}_{10}{\mathrm{C}}_3=120$ 通り。うち連続しないものが 56 通りでした。

少なくとも 1 組が連続するのは $120-56=64$ 通りです。難しく見える側を、易しい側から引く。

小さい場合で確かめる

公式を覚えたら、手で書ける大きさで検算します。$n=4$、$k=2$ で試す。

式は ${}_{4-2+1}{\mathrm{C}}_2={}_3{\mathrm{C}}_2=3$ 通り。

書き出すと $\{1,3\}$、$\{1,4\}$、$\{2,4\}$ の 3 つ。$\{1,2\}$ や $\{3,4\}$ は連続するので外れます。値が合った。

よくある誤り

迷ったら、まず「先に並べるのはどれか」を決めます。そこさえ決まれば、あとは選ぶか並べるかの判断だけ。

参考文献

^[1] が連続しない選び方の公式、^[2] と ^[3] がすき間を使う数え方の一般形、^[4] と ^[5] は各国語での基本公式のまとめです。