大学入試数学 禁止位置のある順列—重なる禁止条件を包除で整理して数え漏れを防ぐ｜武蔵野個別指導塾

返却先の札を手がかりに、違反の共通部分を数え直し、引きすぎを修正する包除をたどります。

よくあるのは、高校生が返却先の違う札を並べるとき、違反を1件ずつ引いて引きすぎる場面です。札Aが禁止位置にある並びと、札Bが禁止位置にある並びには、両方が同時に起こるものが含まれます。その並びを2回引くと、もとの全体からは1回しか取り除く必要がないのに、余分に1回消してしまいます。

問いには、指定された複数の札がそれぞれの禁止位置を避ける並びを求める型、どの札も自分の番号の位置に置かない型、禁止位置が互いに衝突する型があります。いずれも全体から違反を除きますが、同時に起きる違反が何通りあるかは配置を見て決めます。ここでは区別できる札を区別できる位置に1枚ずつ置き、完成した並びを数えます。

違反の集合を作る

全体の集合をU、札Aが禁止位置にある並びの集合をA、札Bが禁止位置にある並びの集合をBとします。AとBの共通部分は、両方の違反が同時に起きる並びです。以下、集合の要素の個数を、例えばn(A)と表します。求めたいのはAにもBにも入らない並びです。

図1のように、2つの違反をそれぞれ引くと共通部分は2回引かれます。そこで共通部分を1回足し戻します。式は n(U) − n(A) − n(B) + n(AとBの共通部分) です。これは図形の面積を測る公式として覚えるより、1つの並びが何回数えられるかを確かめると使いやすくなります。

図1で、Aだけに入る並びは全体で1回数えられ、Aを引くと0回になります。両方に入る並びは1 − 1 − 1 + 1 = 0回です。どちらにも入らない並びは最初の1回が残ります。したがって、欲しい並びだけが1回ずつ残ります。

違反が3つなら、まず各違反を引き、次に2つずつの共通部分を足し、最後に3つの共通部分を引きます。3つとも違反する並びは、全体で1回、単独の違反で3回引かれ、2つずつの共通部分で3回足されます。この時点では1回残っているので、最後に1回引いて0回にします。ちょうど2つに違反する並びは1 − 2 + 1 = 0回、ちょうど1つなら1 − 1 = 0回です。違反がない並びは1回残ります。

共通部分の個数は、札と位置を固定してから残りを並べて求めます。ただし固定が両立するときに限ります。異なる2枚を同じ1位置に置く条件や、1枚を異なる2位置に置く条件は同時に成立しないため、その共通部分は0通りです。0を含めて表に書くと、機械的に残りの札を並べる誤りを防げます。

基本例題：2つの返却先

【基本・標準】区別できる札A、B、C、Dを、区別できる位置1、2、3、4に1枚ずつ置きます。Aを位置1に、Bを位置2に置くことをそれぞれ禁止します。禁止をどちらも破らない並びは何通りですか。整数で答えてください。

全体は4・3・2・1 = 24通りです。Aを位置1に固定すると、残り3枚を3位置に並べるので6通りです。Bを位置2に固定した場合も6通りあります。両方を固定すると残り2枚の順序が2通りです。

図2のように、両方の違反を固定できることを先に確かめます。2つの位置が異なるので矛盾はありません。

求める個数 = 24 - 6 - 6 + 2
= 14

答えは14通りです。足し戻した2通りは、違反を含む並びを答えに入れるためではありません。2回引いてしまった分を調整するためです。各並びについて最終的に違反があれば0回、なければ1回となる点を確認してください。

別の数え方では、Aの置き場を2、3、4に分けます。位置2に置くとBは位置2を使えないので残り3位置のどこでもよく、残りを含めて6通りです。Aが位置3または4なら、Bには残る3位置のうち位置2以外の2つがあり、それぞれ残り2枚を2通りに並べます。したがって6 + 4 + 4 = 14通りとなり、包除と一致します。場合分けは排反で、Aの許される位置をすべて含んでいます。

標準例題：3つの違反を重ねる

【標準・やや難】区別できる5枚の札A、B、C、D、Eを位置1から5へ1枚ずつ置きます。Aは位置1、Bは位置2、Cは位置3に置けません。条件を満たす並びを整数で求めてください。

全体は5・4・3・2・1 = 120通りです。A、B、Cのいずれか1つの違反を指定すれば、残り4枚を並べるので各24通りです。2つの違反を指定する組は3組あり、どの組も異なる札を異なる位置に固定するので各6通りです。3つの違反を指定すると残り2枚の並べ方は2通りです。

求める個数 = 120 - 3・24 + 3・6 - 2
= 64

答えは64通りです。3つの違反の共通部分を引く段階を落とすと66通りになります。2つずつの共通部分を足す操作は、3つとも違反する並びにも3回作用するため、最後の調整が必要です。

別の見方として、A、B、Cの違反数で並びを分けます。違反が3つの並びは2通り、ちょうど2つの並びは各組について6 − 2 = 4通りで計12通りです。ちょうど1つの並びは、指定した1違反の24通りから他の2違反を含むものを除き、24 − 6 − 6 + 2 = 14通りずつ、計42通りです。違反のある並びは2 + 12 + 42 = 56通りなので、120 − 56 = 64通りです。違反数による分類は互いに重ならず、全体を尽くしています。

発展例題：同じ位置を禁止するとき

【発展・難】区別できる札P、Q、R、Sを位置1から4へ1枚ずつ置きます。PとQはそれぞれ位置1に置けず、Rは位置2に置けません。条件を満たす並びを整数で求めてください。

Pの違反をX、Qの違反をY、Rの違反をZとします。各違反は札1枚を固定するので、それぞれ6通りです。しかしXとYは異なる2枚を位置1に同時に置けないので、共通部分は0通りです。XとZ、YとZはそれぞれ両立し、残り2枚を並べて各2通りです。3つの共通部分もXとYを含むため0通りです。

求める個数 = 24 - 6 - 6 - 6 + 0 + 2 + 2 - 0
= 10

答えは10通りです。禁止が3件あるという数だけを見て、2件の共通部分をすべて2通りとすることはできません。固定した札と位置が衝突するかを組ごとに確認します。

別解では位置1に入る札を決めます。PとQは入れないため、RまたはSです。RならRの禁止する位置2も自動的に避け、残りは3・2・1 = 6通りです。Sなら位置2にRを置く2通りを残りの6通りから引き、4通りです。位置1の札による2つの場合は重ならず、6 + 4 = 10通りとなります。禁止位置が重なるとき、こちらの分類の方が短くなることもあります。

引きすぎた並びを追跡する

基本例題で24 − 6 − 6 = 12通りとする解答を考えます。図3の2行は、Aが位置1、Bが位置2にある実際の並びです。どちらもAの違反として一度、Bの違反としてもう一度引かれます。

図3の各行は全体では1回現れたので、2回引いた直後は数え上げの係数が -1です。この係数を0に戻すため、2行を1回ずつ足し戻します。12という値には、条件を満たす14通りからこの2通り分をさらに引いた状態が表れています。

反対に、共通部分を足したままで「両方違反しても許される」と解釈するのも誤りです。足し戻しまで含む係数が0であることを、1行について追ってください。また共通部分が空の場合に足すのは0です。図で領域が重なって見えるとしても、実際の配置条件が衝突するなら共通する並びは存在しません。

全禁止位置を避ける問題でも、全体から各違反を引く手順は変わりません。例えば異なるn枚を異なるn位置に置き、札ごとに異なる1位置を禁止するとします。nは正の整数で、指定したk個の違反が同時に成立するとき、残りのn − k枚を並べられます。どのk個を選んでも固定する位置が異なるので、共通部分の個数は同じです。ただし最初から式を暗記する必要はありません。単独、2つ、3つと固定し、選び方と残りの並べ方を分けて数えることで、符号と係数を作れます。

禁止位置が互いに異ならない場合は、同じk個の違反でも両立する組としない組が混ざります。共通部分を一律に扱う前に、その条件があるかを調べます。固定後に残る札と位置が同数か、同じ札を2回使っていないかも点検してください。

配置を紙に書くときは、位置を左から順に並べ、固定する札だけを先に記入します。その後に空欄と残った札を対応させれば、固定した条件に反する並びが混ざっても、それは指定した共通部分に属するので数えてよいとわかります。たとえば2つの違反の共通部分には、3つ目の違反も起こる並びが含まれます。3つ目を避けるという条件を勝手に加えると、足し戻す個数が不足します。共通部分は「指定した違反が起きる」ことを表し、指定しない違反の有無は問いません。

練習問題

各問の札と位置は区別でき、各位置に札を1枚ずつ置きます。いずれも答えは整数の通り数で求めてください。

1. 【標準】札a、b、cを位置1から3に置きます。aを位置1に置かない並びは何通りですか。
2. 【標準】札d、e、f、gを位置1から4に置きます。dを位置1に、eを位置3に置かない並びは何通りですか。
3. 【やや難】札h、i、j、kを位置1から4に置きます。hを位置1、iを位置2、jを位置4に置かない並びは何通りですか。
4. 【やや難】札L、M、N、O、Tを位置1から5に置きます。LとMをそれぞれ位置4に置かない並びは何通りですか。
5. 【難】札U、V、W、Xを位置1から4に置きます。Uを位置1にも位置2にも置かず、Vを位置3に置かない並びは何通りですか。

練習の解答と確かめ

1

全体は3・2・1 = 6通りです。aを位置1に固定した違反は2・1 = 2通りなので、6 − 2 = 4通りです。aの置き場を位置2と3に分けても、各2通りで計4通りです。位置1にaがないことを、それぞれの分類で直接確かめられます。

2

全体は24通りです。各違反は6通り、両方の違反はdとeを異なる位置に固定し、残り2通りです。したがって24 − 6 − 6 + 2 = 14通りです。直接数えると、dが位置3なら6通り、位置2か4なら各4通りで、条件を満たす14通りに戻ります。

3

全体は24通りです。各違反は6通り、2つの違反の各共通部分は2通り、3つの共通部分は残りの札の位置も決まり1通りです。よって24 − 3・6 + 3・2 − 1 = 11通りです。違反が3つの並びは1通り、ちょうど2つは3通り、ちょうど1つは各違反について6 − 2 − 2 + 1 = 3通りで計9通りです。違反ありは13通りなので、24から引いても11通りです。

4

全体は120通りです。Lの違反とMの違反は各24通りで、異なる2枚を位置4に置くことはできず、共通部分は0通りです。120 − 24 − 24 + 0 = 72通りとなります。位置4に入る札をN、O、Tの3枚から選び、残りを4・3・2・1通りに並べても3・24 = 72通りです。

5

Uが位置1にある違反をA、位置2にある違反をB、Vが位置3にある違反をCとします。各違反は6通り、AとBの共通部分は0通り、AとCおよびBとCの共通部分は各2通りです。3つの共通部分も0通りです。

求める個数 = 24 - 3・6 + 0 + 2 + 2 - 0
= 10

Uは位置3または4です。位置3ならVは残りのどの位置でもよく6通り、位置4ならVを位置3に置く2通りを除いて4通りです。元の条件に戻しても6 + 4 = 10通りです。

覚えておくこと

• 全体を決め、違反を集合として名前を付けます。
• 2つの違反は各々を引き、共通部分を足し戻します。
• 3つの違反は2つずつの共通部分を足した後、3つの共通部分を引きます。
• 固定する札と位置が衝突する共通部分は0通りです。
• 最後に、1つの並びの数えられる回数を追います。

どこで止まったかを見分ける

式の符号で迷う場合は、3つとも違反する1つの並びに注目し、全体からの係数を順に書きます。固定後の個数で迷う場合は、実際に札と位置を書き込んで空いた場所を数えます。共通部分を足す理由と、その中身を数える作業は別の段階です。

個別に学ぶ場面では、まず1つの並びが違反のどの集合に入るかを説明し、次に共通部分の固定が可能かを確認します。最後に、位置を先に選ぶ別の分類と答えを照合すれば、引きすぎも固定の衝突も見つけられます。禁止位置の重なりを確かめれば、包除の各項に意味が戻ります。