メインコンテンツへスキップ

数学|初見の一手 §2 場合の数|対応づけによる数え上げ:数えたいものが直接見えないとき、何に移して数えればよい?

    §2 場合の数|細目:対応づけによる数え上げ
    関係する一手の型:型4 数え方を変える
    想定する読み手のレベル感:【実戦】。5題とも、数えたい対象を別の構造へ移す一手が決まってから計算に入る実戦寄りの内容です。元の第44回・第158回・第164回・第184回・第185回を統合した記事です。


    導入:数えたいものを、数えやすい構造へ移してから数える

    直接数えようとすると条件が絡み合って手が止まる場面では、数えたい対象そのものではなく、それと対応する別の対象を数えます。この記事で扱うのは、席順の置換、順列の下降箇所、包含関係のない集合の集まり、整数の和の表し方、二組の共通要素という、見た目の違う5つの場面です。共通しているのは、移し先の方が数えやすく、しかも移し方が一対一か、あるいは「同じものが何回ずつ数えられるか(多重度)」が正確に分かる、という点です。

    初手の対応表は次のとおりです。例題ごとに「何と何を対応させたか」を先に固定します。

    • 席順を置換の巡回に移す:人の移動を置換とみて巡回に分解すると、「自分の席に座らない」「二人で交換しない」という禁止条件は、巡回の長さが1でない・2でない、という長さの条件に移ります。(例題1)

    • 順列を三つの箱への振り分けに移す:下降箇所で区切ると各部分は増加列になるので、順列は「数字を三つの箱へ分け、箱の中を小さい順に並べてつなぐ」作り方と対応します。ただし同じ順列が何回作られるかは、その順列の下降箇所の数で変わります。(例題2)

    • 集合の集まりを、順列と集合の組に移して二通りに数える:一つの順列からは包含でつながる集合の列が作れます。条件を満たす集まりは、その列から高々一つしか取れません。「順列と、その列に現れる選ばれた集合」の組を、順列の側と集合の側の二通りで数えると、重み付きの上限が出ます。(例題3)

    • 数の選び方を、奇数ごとの係数に移す:各数を「奇数×2の累乗」に分け、同じ奇数を持つ仲間ごとにまとめると、選び方は係数の組と一対一に対応します。二進法が、係数から元の選び方へ一意に戻れることの根拠です。(例題4)

    • 二集合の組を、共通要素の側から数える:各数の登場回数を置くと、二集合の組の総数は、共通要素ごとにちょうど一度ずつ数え直せます。その結果が登場回数の二乗の和を決め、二乗の非負性から個数の上限が出ます。(例題5)

    読み方のコツは、対応を作ったところで止まらないことです。一対一なら個数はそのまま移りますが、多重度がある場合は「何回ずつ数えたか」を対象の特徴ごとに調べ直すこと(例題2)、上限を出す問題では構成例で等号が取れるかまで確かめること(例題3・例題5)が、答案を閉じる条件になります。


    例題1(元の第44回):席順を巡回に分解し、禁止条件を長さの条件に移す

    番号1から8の人を、同じ番号の八つの席へ一人ずつ座らせる。誰も自分の番号の席に座らず、どの二人も互いの元の席を交換しない座り方は何通りか。

    人と席を一対一に対応させる問題でも、条件が「元の席に残らない」「二人だけで交換しない」となると、全体の 8!8! 通りから一度に引くのは難しくなります。一人の移動先を順に追うと、最後に出発点へ戻る巡回が見えます。そこで、席順を置換の巡回へ移します。

    禁止条件を、巡回の長さに言い換える

    人 jj の座る席を σ(j)\sigma(j) とします。全員の席が異なるため、σ\sigma は1から8の置換です。j→σ(j)→σ2(j)→⋯j\to\sigma(j)\to\sigma^2(j)\to\cdots と追うと、有限個の番号を進んで、元の番号に戻ります。このひと続きが巡回です。

    自分の席に残る人は長さ1の巡回、互いに席を交換する二人は長さ2の巡回です。したがって条件は、すべての巡回の長さが3以上であること、と言い換えられます。対応の定義はここまでで、数える対象は「巡回長がすべて3以上の置換」に移りました。

    八を、三以上の整数に分ける

    巡回の長さの合計は8です。3以上の長さを使う構成は、

    8,5+3,4+48,\qquad5+3,\qquad4+4

    の三種類だけです。三つ以上の巡回なら合計は9以上になるので不可能です。先に可能な構成を尽くすことで、後の計算に漏れがないことを保証できます。

    一つの巡回に使う kk 人が決まっているとき、その巡回は (k−1)!(k-1)! 通りです。一人を始点に固定し、残りの人を巡回の順に並べればよいからです。逆向きの巡回は一般に別の置換なので、さらに2では割りません。

    長さが違う巡回と、同じ巡回を区別する

    全員が一つの巡回(長さ8)なら 7!=50407!=5040 通りです。

    長さ5と3なら、長さ3の巡回の三人を選び、その三人を巡回させ、残る五人を巡回させます。したがって、

    (83)2!4!=56⋅2⋅24=2688\binom{8}{3}2!4!=56\cdot2\cdot24=2688

    通りです。二つの巡回は長さが違うので、どちらが三人組かは一意に決まり、2で割る必要はありません。

    長さ4と4なら、先に四人を選ぶと、二つの組を選ぶ順序の分だけ各構成を二回数えます。よって、

    (84)(3!)22=70⋅362=1260\dfrac{\binom{8}{4}(3!)^2}{2}=\dfrac{70\cdot36}{2}=1260

    通りです。同じ長さの巡回が複数あるときの重複は、ここで割り落とします。

    禁止した構成がないことを確かめる

    三種類は巡回の長さの組み合わせが違うので互いに重なりません。合計は、

    5040+2688+1260=8988通り\boxed{5040+2688+1260=8988\text{通り}}

    です。数えた置換には長さ1と2の巡回がないため、元の二つの禁止条件を満たします。逆に条件を満たす置換は三種類のいずれかなので、数え漏れもありません。なお、全 8!8! 通りから無作為に選ぶなら、その確率は 898840320=107480\dfrac{8988}{40320}=\dfrac{107}{480} です。


    例題2(元の第158回):順列を三つの箱への振り分けに移し、多重度を調べ直す

    n≥3n\ge3 とする。1,2,…,n1,2,\ldots,n の順列で、隣り合う数について左の数が右の数より大きくなる箇所が、ちょうど二つある並び方の数を求めよ。

    例えば 1,4,2,5,31,4,2,5,3 では、44 から 22 と、55 から 33 の二か所が、左の数が右の数より大きくなる箇所(下降箇所)です。下降する二つの場所を先に選んでも、それ以外の場所の大小をそろえる条件が残ります。

    逆に、下降箇所で区切ると、それぞれの部分は増加列です。そこで、数字を三つの箱へ分け、箱の中を小さい順にして左からつなぐ方法を考えます。箱は区別し、空でも構いません。数字ごとに箱を選ぶので、この作り方は全部で 3n3^n 通りです。これが対応の定義です。ただし、境目で必ず数が小さくなるとは限らないため、下降箇所が二か所ある並びだけを一回ずつ作るわけではありません。同じ並びが何回作られるか(多重度)を、並びの下降箇所の数ごとに調べ直すのがこの例題の中心です。

    まず二箱で、一か所の場合を求める

    下降箇所がちょうど一つある並びの数を A1A_1 とします。二箱へ数字を分け、それぞれ増加列にしてつなぐ作り方は 2n2^n 通りです。

    下降箇所が一か所の並びでは、その箇所に境目を置く必要があり、分け方は一通りです。一方、全体が増加する並びは 1,2,…,n1,2,\ldots,n の一つだけですが、境目は両端を含む n+1n+1 か所のどこにも置けます。したがって、

    A1=2n−(n+1)A_1=2^n-(n+1)

    です。空の箱を認めたのは、境目を両端にも置けるようにし、数え方を一つにそろえるためです。

    三箱では、境目が二本ある

    三箱の作り方を、できた並びの下降箇所の数で分けます。三つの増加列をつないだ並びなので、その数は0、1、2のどれかです。

    0か所の並びは一つだけです。二本の境目を、両端を含む n+1n+1 か所へ重複を認めて置きます。同じ場所に二本置けば、間の箱が空になります。よって分け方は

    (n+22)\binom{n+2}{2}

    通りです。これが0か所の並びの多重度です。

    1か所の並びでは、その一か所に境目が少なくとも一本必要です。もう一本を n+1n+1 か所のどこへ置いてもよいので、一つの並びにつき n+1n+1 通りです。二本ともその箇所に置く場合も一通りとして含みます。これが1か所の並びの多重度です。

    2か所の並びでは、二本の境目をその二か所へ置くしかなく、分け方は一通りです。求める数を A2A_2 とすると、三箱の作り方の総数 3n3^n を多重度つきで数え直して、

    3n=(n+22)+(n+1)A1+A23^n=\binom{n+2}{2}+(n+1)A_1+A_2

    となります。箱の中身から並びと境目が一意に決まり、逆に並びと境目から箱の中身が戻るため、この数え直し自体に余分な重複はありません。A1=2n−(n+1)A_1=2^n-(n+1) と (n+22)=(n+1)(n+2)2\binom{n+2}{2}=\dfrac{(n+1)(n+2)}2 を代入して整理すると、

    A2=3n−(n+1)2n+n(n+1)2\boxed{A_2=3^n-(n+1)2^n+\dfrac{n(n+1)}2}

    です。多重度は並びによって (n+22) \binom{n+2}{2} 回、n+1n+1 回、1回と異なるので、単純に 3!3! などで割る問題ではありません。

    演習:「ちょうど二つ」を「二つ以下」へ変える

    小さくなる箇所が二つ以下である並び方の数を求めよ。

    0か所の一通り、1か所の A1A_1 通り、2か所の A2A_2 通りは互いに重ならないので、足し合わせて、

    3n−n2n+n(n−1)2\boxed{3^n-n2^n+\dfrac{n(n-1)}2}

    です。例えば n=3n=3 では答えは6で、全順列に一致します。三つの数字では小さくなる場所が最大で二つだからです。


    例題3(元の第164回):順列と集合の組を二通りに数え、重み付きの上限を出す

    {1,2,…,8}\lbrace 1,2,\ldots,8\rbrace の部分集合をいくつか選ぶ。選んだ異なる二集合の間で、一方が他方に含まれることはないものとする。選べる集合の個数の最大値を求めよ。空集合や全体集合も、条件を満たせば選んでよい。

    要素の数が同じで異なる二集合なら、一方が他方に含まれることはありません。したがって、四要素の集合をすべて選べば 8C4=70{}_8\mathrm{C}_4=70 個を選べます。ただし、三要素や五要素の集合を混ぜるともっと増やせるかもしれません。四要素だけの例では「少なくとも70個」までしか示せていないため、どんな混ぜ方でも70個を超えないこと(上限)の証明が必要です。上限と構成の両面を示すのがこの例題です。

    一つの順列から、順番に大きくなる集合を作る

    8個の数字の順列 a1,…,a8a_1,\ldots,a_8 を一つ取り、空集合から始めて、先頭の数字を一つずつ加えます。

    ∅, {a1}, {a1,a2}, …, {a1,…,a8}\varnothing,\ \lbrace a_1\rbrace,\ \lbrace a_1,a_2\rbrace,\ \ldots,\ \lbrace a_1,\ldots,a_8\rbrace

    この九つは、先の集合が後の集合に必ず含まれます。したがって、問題の条件を満たす集まりから、この九つの中へ入る集合は多くても一つです。

    そこで、「順列と、その先頭部分に現れる選ばれた集合」の組を数えます。これが対応の定義です。順列ごとに組は多くても一組なので、組の総数は 8!8! 以下です。

    集合の大きさによって、現れる順列の数が違う

    選ばれた集合 AA の要素数を kk とします。AA が先頭 kk 個の集合になるには、先頭へ AA の数字を任意の順に並べ、残りへそれ以外の数字を並べればよいので、そのような順列は k!(8−k)!k!(8-k)! 通りです。空集合なら k=0k=0、全体集合なら k=8k=8 としても同じ式が使えます(0!=10!=1)。

    選んだ集まりを F\mathcal F と書き、二通りの数え方を合わせると、

    ∑A∈F∣A∣!(8−∣A∣)!≤8!\sum_{A\in\mathcal F}|A|!(8-|A|)!\le8!

    となります。両辺を 8!8! で割って、

    ∑A∈F18C∣A∣≤1\sum_{A\in\mathcal F}\dfrac1{{}8\mathrm{C}{|A|}}\le1

    です。どの大きさの集合も同じ回数現れるわけではないため、まずこの重みを付けて数えたことが要点です。

    重みをそろえれば、個数の上限になる

    二項係数 8Ck{}_8\mathrm{C}_k は k=4k=4 で最大の70となります。したがって、上の和の各項は 170\dfrac1{70} 以上です。選んだ個数を MM とすれば、

    M70≤1\dfrac M{70}\le1

    となり、M≤70M\le70 が出ます。初めに挙げた四要素の集合すべてを選ぶ構成で等号が取れるため、最大値は

    70\boxed{70}

    です。

    演習:各集合の要素数を二つ以下にする

    選ぶ各集合の要素数が2以下という条件も加えたとき、最大個数を求めよ。

    同じ二重の数え方で、重み付きの和は1以下です。今度使える大きさは0、1、2だけで、対応する二項係数は1、8、28です。したがって各項は 128\dfrac1{28} 以上になり、個数は28以下です。二要素の集合をすべて選べば28個で条件を満たすため、答えは

    28\boxed{28}

    です。最初から同じ大きさの集合に限定して数えたのではなく、違う大きさを混ぜる可能性まで含めて上限を示しました。


    例題4(元の第184回):数の選び方を、奇数ごとの係数に移す

    15を、1以上8以下の相異なる正整数の和として表す方法は何通りあるか。足す順序は区別しない。

    1から8までの各数を使うかどうかで候補は 28=2562^8=256 通りありますが、合計15だけを拾うには、合計以外の構造も使いたいところです。ここでは、どの数も「奇数×2の累乗」に一意に分けられることに注目します。

    同じ奇数を持つ数をまとめる

    1、2、4、8は、同じ奇数1を持つ仲間です。3と6は奇数3の仲間、5と7はそれぞれ一つだけです。選んだ数をこの四組に分けると、組ごとの合計は

    m1,3m3,5m5,7m7m_1,\quad3m_3,\quad5m_5,\quad7m_7

    と書けます。許される係数の範囲は、

    0≤m1≤15,0≤m3≤3,m5,m7∈{0,1}0\le m_1\le15,\quad0\le m_3\le3,\qquad m_5,m_7\in\lbrace 0,1\rbrace

    です。例えば、1、2、4、8の一部を選んだ和は、0から15までをちょうど一度ずつ表します。これは二進法の表示そのものです。3と6の場合は、係数が0、1、2、3となります。

    係数から元の選び方へ、一意に戻れるか

    合計が等しくなるだけでは、数え直しには使えません。同じ合計の異なる選び方が一つに潰れないかを確かめます。m1m_1 を二進法で書けば、1、2、4、8のどれを使ったかが決まります。m3m_3 の二進法表示は、3と6の使い方を決めます。5と7については係数は0か1だけです。したがって、四つの係数の組と元の整数の集合は一対一に対応します。これが対応の定義と、その逆向きの確認です。例えば m1=6, m3=3, m5=m7=0m_1=6,\ m_3=3,\ m_5=m_7=0 なら、選んだ数は2、4、3、6で、合計は15です。

    残りを1の仲間で埋める

    求める式は、

    m1+3m3+5m5+7m7=15m_1+3m_3+5m_5+7m_7=15

    です。m5,m7m_5,m_7 を先に決めると、m3m_3 の候補は次のとおりです。

    • (m5,m7)=(0,0)(m_5,m_7)=(0,0):m3=0,1,2,3m_3=0,1,2,3 の4通り

    • (m5,m7)=(1,0)(m_5,m_7)=(1,0):m3=0,1,2,3m_3=0,1,2,3 の4通り

    • (m5,m7)=(0,1)(m_5,m_7)=(0,1):m3=0,1,2m_3=0,1,2 の3通り

    • (m5,m7)=(1,1)(m_5,m_7)=(1,1):m3=0,1m_3=0,1 の2通り

    どの場合も残りは m1m_1 で一つに決まり、0以上15以下に収まります。よって答えは

    4+4+3+2=13通り\boxed{4+4+3+2=13\text{通り}}

    です。大きい数から選んでいく代わりに、同じ奇数を持つ仲間をまとめたことで、場合分けが短くなりました。

    演習:使える数の上限を外す

    任意の正整数 NN について、「相異なる正整数の和で NN を表す方法」と「奇数だけの和で NN を表す方法」は同じ数だけあることを示せ。後者では同じ奇数を何回使ってもよく、順序はどちらも区別しない。

    相異なる整数をそれぞれ j2rj2^r(jj は奇数)に分けます。同じ jj の仲間を、jj を 2r2^r 個足す形に直せば、奇数だけの和になります。逆に、奇数 jj の使用個数 mjm_j を二進法で表し、1が立つ桁 rr ごとに整数 j2rj2^r を一つ選びます。同じ jj なら桁が違い、異なる jj なら奇数部分が違うので、選ぶ整数はすべて異なります。二つの操作は互いに逆なので、表し方の個数は等しくなります。

    主問題では上限8があるため、二進法で使える桁にも上限がありました。対応を使うときは、元の上限が対応の中でどこへ移るかまで確認しておくと安心です。


    例題5(元の第185回):二集合の組を共通要素の側から数え直し、二乗の和に移す

    集合 {1,2,3,4,5,6}\lbrace 1,2,3,4,5,6\rbrace から、要素が三つの部分集合をいくつか選びます。選んだどの二集合も、共通する要素がちょうど一つであるようにします。選べる集合の最大個数を求めてください。

    三要素の集合は全部で 6C3=20{}_6\mathrm{C}_3=20 個あります。ただ、一組ずつ点検するより、各数が選んだ集合のうち何個に入っているかを数えたほうが、「共通要素がちょうど一つ」という条件をまとめて使えます。

    集合の組を数えるため、各数の登場回数を置く

    選んだ集合の個数を MM、数 ii の登場回数を rir_i とします。どの集合も三つの数を含むので、延べ個数を数えて、

    r1+r2+⋯+r6=3Mr_1+r_2+\cdots+r_6=3M

    です。ここまでは延べ個数を数えただけです。次に、二集合の組を数えます。

    同じ二集合を、共通する数から一度だけ数える

    数 ii を含む集合は rir_i 個あります。その中から二集合を選ぶ方法は (ri2)\binom{r_i}{2} 通りです(ri=0,1r_i=0,1 ならこの個数は0とします)。

    どの二集合も共通要素がちょうど一つなので、その二集合は共通要素のところで一度だけ数えられます。これが対応の要です。二集合の組の総数を共通要素の側から数え直すと、

    ∑i=16ri(ri−1)2=M(M−1)2\sum_{i=1}^6\dfrac{r_i(r_i-1)}2=\dfrac{M(M-1)}2

    となります。先ほどの和 ∑ri=3M\sum r_i=3M を使って整理すると、

    ∑i=16ri2=M2+2M\sum_{i=1}^6r_i^2=M^2+2M

    です。「共通要素がちょうど一つ」という条件が、登場回数の二乗の和に移りました。

    二乗は負にならないことから、上限を出す

    六つの実数について展開すると、

    6∑i=16ri2−(∑i=16ri)2=∑1≤i<j≤6(ri−rj)2≥06\sum_{i=1}^6r_i^2-\left(\sum_{i=1}^6r_i\right)^2=\sum_{1\le i<j\le6}(r_i-r_j)^2\ge0

    となります。右辺は二乗の和です。二つの数え上げの結果を左辺に入れると、

    9M2≤6(M2+2M),M(M−4)≤09M^2\le6(M^2+2M),\qquad M(M-4)\le0

    となり、M≤4M\le4 が出ます。これが上限です。

    上限を取る構成を示す

    上限4が出たことと、四集合を作れることは別の話です。実際に、

    A1={1,2,3},A2={1,4,5},A3={2,4,6},A4={3,5,6}A_1=\lbrace 1,2,3\rbrace,A_2=\lbrace 1,4,5\rbrace,A_3=\lbrace 2,4,6\rbrace,A_4=\lbrace 3,5,6\rbrace

    と選べます。六組の共通要素は順に1、2、3、4、5、6で、どの組もちょうど一つだけです。したがって最大値は

    4\boxed{4}

    です。このとき各数の登場回数は2でそろい、上の二乗の和も0になります。

    演習:「ちょうど一つ」を「一つ以上」に変える

    共通要素が一つ以上でよいなら、最大個数はいくつか。

    三要素の集合20個は、互いに補集合になる二集合の組が10組に分かれます。一組の両方を選ぶと共通要素がないので、各組から選べるのは高々一個、合計で高々10個です。逆に、数1を含む三要素の集合を全部選べば、どの二集合も1を共有します。その個数は 5C2=10{}_5\mathrm{C}_2=10 個です。よって最大値は10です。

    主問題では、二集合を一度だけ数えられたので二乗の和が決まりました。演習では共通要素の数が変わるため、その等式は使えません。同じ集合の問題でも、条件に合わせて「何を一組として数えるか」を選び直します。


    まとめ:手が止まったときの初手の選び方

    直接数えにくい場面で手が止まったら、まず「何と何を対応させるか」を言葉で固定します。

    • 移動や並べ替えの禁止条件なら、置換の巡回へ移し、条件を巡回の長さの条件に直す。構成は長さの分割で尽くし、同じ長さの巡回どうしの重複は割って落とす。(例題1)

    • 順列の局所的な条件(下降箇所の数)なら、箱への振り分けと増加列の連結へ移す。ただし多重度は対象ごとに違うので、下降箇所の数ごとに「何回作られるか」を調べ直してから総数とつなぐ。(例題2)

    • 包含を避ける集まりの最大個数なら、順列から作る包含の列と組み合わせて二通りに数え、大きさごとの重みをそろえて上限を出す。上限には必ず構成で答える。(例題3)

    • 和の表し方なら、各数を「奇数×2の累乗」に分けて仲間ごとに係数化する。係数から元の選び方へ二進法で一意に戻れることを確かめてから、係数を数える。(例題4)

    • 二集合の関係の条件なら、二集合の組を共通要素の側から数え直し、登場回数の二乗の和へ移す。二乗の非負性で上限を出し、構成で等号を確認する。(例題5)

    共通しているのは、「数える」作業を「数えやすい構造へ移す」作業に置き換えることです。移し方を決めたら、残りは一対一か多重度つきかの確認と、上限問題では構成による裏付けに分解できます。

    ―――

    無料ツール公開中

    Claudeで作った『大学別数学模試ジェネレータ』を無料で公開しています。共通テスト含む42校・90形式対応、答案の写真からのAI採点(部分点・講評つき)もできます。

    仕様と使い方(無料記事):https://note.com/opus3333/n/n6feebee8832a

    ツールはこちら:https://claude.ai/artifact/Dh3TZXcoe8CU4RzNhwVm98

    有料記事(各¥100)

    ・大学入試数学、解けない問題に何分使う?『撤退する力』を鍛える5題:https://note.com/opus3333/n/n0caf1ada7687

    ・ChatGPTに答えを教えさせるな。難関大数学を自力で解くためのAI活用プロンプト12選:https://note.com/opus3333/n/n0c4eae0f24ab

    この記事が役に立ったら、スキで応援してもらえると嬉しいです。

    ―――

    あなたへのおすすめ