【応用】条件のついた並び方(部分的に順序指定)

ここでは、部分的に順序が指定された状況で並び方を数える問題を見ていきます。例えば、「AさんがBさんより左にくる並び方は何通りあるか」のような問題を見ていきます。順列ですが、使うのは組合せです。その点では、【標準】同じものを含む順列に通じるものがあります。

【広告】
※ お知らせ: nCr の性質に関する動画を公開しました。

AさんがBより左に並ぶ場合

例題
A, B, C, D, E の5人を左から右へ一列に並べる。
(1) A が B よりも左に並ぶような並べ方は何通りあるか。
(2) A が B よりも左に並び、B が C よりも左に並ぶような並べ方は何通りあるか。
(3) A が B よりも左に並び、C が D よりも左に並ぶような並べ方は何通りあるか。

5人を一列に並べる方法は $5!=120$ 通りですね。この中から、A が B より左に並ぶ場合を考えましょう。

例えば、
 「AB・C・D・E」
という並びはOKで、
 「BA・C・D・E」
はダメです。同様に考えると、120通りの並び方の中には、「A と B の並び順が同じ」「C, D, E の並んでいる場所が同じ」である、対応する2つの並び方があることがわかります。もう一つ例を挙げると
 「C・A・D・B・E」
 「C・B・D・A・E」
といった並び方のペアがある、ということです。このうち、「A が B より左」にあるのは片方だけなので、全体の半分が(1)の並び方に該当することがわかります。つまり、\[ 120\div 2=60 \]通り、ということです。

もっとざっくりいうと、
 「A が B より左」
 「A が B より右」
この2つの並び方は、それぞれ対応付けができる(A と B を入れ替えればいい)ので、同じ数だけあるから、2で割れば求められるというわけです。

(2)も、(1)と同じように「対応付けができるから、あとで割る」という考え方でも解けます。

5人を並べたときに、A と B と C だけを抜き出したとき、この3人を入れ替えたものはそれぞれ対応します。例えば
 「D・AB・E・C
という並び方であれば、A と B と C だけを入れ替えた次の並び方
 「D・AC・E・B
 「D・BA・E・C
 「D・BC・E・A
 「D・CA・E・B
 「D・CB・E・A
が対応し、これらのうち1つだけが条件に該当します。上のような入れ替えは、3人を一列に並べる方法 $3!=6$ 通りあるので、\[ 120\div 3!=20 \]通り、となります。

また、次のような考え方でもいいでしょう。まず、順番が指定されている3人を〇で表し、「〇・〇・〇・D・E」を一列に並べます。そのあと、条件を満たすため、3つの〇に、左から「A・B・C」を並べていく、という方法です。後から条件を満たすように並べるという方法です。こうすれば確実に、条件を満たします。また、モレやダブりも発生しませんね。

【標準】同じものを含む順列で見たように、この並び順を数える方法は、まず1番目から5番目の中から3つ選びます。選んだ3か所には、左から順番に「A・B・C」を並べます。選ばなかった2か所は、2人が並ぶので\[ {}_5 \mathrm{ C }_3 \times 2!=20 \]通り、となります。

(3)も、まずは「対応する数だけ割る」方針で解いてみます。

5人を並べたとき、A と B の位置関係、C と D の位置関係だけを抜き出すと
 「A は B の左、C は D の左」
 「A は B の左、C は D の右」
 「A は B の右、C は D の左」
 「A は B の右、C は D の右」
の4パターンあり、それぞれ対応しています。この対応のうち、1つしか条件を満たさないので、 $5!$ 通りの並び方を4で割ったものが、求める答えになります。よって、\[ 5!\div 4=30 \]通り、となります。

次に、(2)の後半で見た、「条件が指定されている人がどこに並ぶかを選ぶ方法」で考えてみます。

「〇・〇・△・△・E」を並べます。次に、〇に「A・B」を左から並べ、△に「C・D」を左から並べます。こうすれば、確実に条件を満たす並び方になります。〇の入る場所を5つから2つ選び、△の入る場所を3つから2つ選ぶと、後はどこにだれが入るかはすべて決まるので\[ {}_5 \mathrm{ C }_2 \times {}_3 \mathrm{ C }_2=30 \]通り、と求められます。

個人的には、「条件が指定されている人がどこに並ぶか」の観点から考えたほうが解きやすいように思います。条件が指定された人を〇などと置いて並べ、あとで条件に合うように並べる、という方法。どちらが解きやすいかは個人の趣味ですが、こちらの解き方のほうが、使える場面が多いように感じます。

おわりに

ここでは、部分的に順序が指定された並び方を数える問題を見てきました。対応する並び方を考えて後で割るか、条件が指定されている人が並ぶ場所を選ぶ方法か。考え方を理解して使えるようにしていきましょう。