大学入試数学 上限付きの配分—同じものを分ける条件を整数の範囲と除外する場合へ直す｜武蔵野個別指導塾

箱の容量を超える配分が重なるときの引き過ぎを、個数の組と仕切りの対応からたどる上限付きの配分。

よくあるのは、高校生が箱ごとの容量を無視して仕切りだけを並べる場面です。区別のつかない品物を名前の異なる箱に分けるとき、仕切りの並べ方は便利ですが、その中には入りきらない箱を含むものもあります。

問いの形には、各箱の上限がある配分を数えるもの、最低個数を先に入れるもの、複数の上限違反が同時に起きるものがあります。まず配分を個数の組に直し、仕切りで数えた集合から何を除いたかを明らかにしましょう。

個数の組と仕切りの対応

箱を A、B、C と区別し、同じ品物をそれぞれ x、y、z 個入れるとします。全部で n 個なら x + y + z = n です。空箱を許すとき、x、y、z は 0 を含む整数であり、箱の容量が順に a、b、c なら 0 ≤ x ≤ a、0 ≤ y ≤ b、0 ≤ z ≤ c も必要です。

図1のように、品物を丸、箱の区切りを縦線で表すと、左から各箱の個数が決まります。逆に個数の組が決まれば丸と仕切りの列は1通りに決まります。箱は名前で区別しますが、品物同士を入れ替えても新しい配分にはなりません。

図1の列では、左から 2、0、1 個です。仕切りが隣り合うことは空箱に対応します。端に仕切りを置く場合も、端の箱が空になる正しい列です。

一般に n 個を区別のある k 個の箱に空箱も許して配ると、丸 n 個と仕切り k − 1 本の並びに対応します。n は 0 以上、k は 1 以上の整数です。合わせて n + k − 1 個の位置から仕切りの位置を選びます。C(p,q) を p 個から q 個を選ぶ組合せの数とすると、上限を無視した個数は C(n + k − 1,k − 1) です。

ただし、この式が数えるのは非負整数の組であり、容量を満たす組とは限りません。合計が容量の合計を超えれば配分は 0 通りです。また下限の合計が品物の数を超える場合や、ある箱の下限がその上限を超える場合も 0 通りです。こうした成立しない条件を先に調べると、負の数に組合せの式を無理に適用せずに済みます。

下限があるときは、各箱に最低限を先に入れて残りを数えます。例えば x ≥ 2 なら X = x − 2 と置きます。上限が x ≤ 5 なら移動後は 0 ≤ X ≤ 3 です。下限を引いた後に上限も同じだけ引くことが、元の条件と新しい条件を対応させる鍵です。

基本例題：1箱の容量を超える場合を除く

【基本・標準】同じ玉 5 個を区別のある箱 A、B、C に全部入れます。空箱を許し、A には高々 2 個入れます。他の箱には 5 個まで入ります。配分の数を整数で求めてください。

A、B、C の個数を x、y、z とします。上限を無視すると非負整数解の数は C(7,2) = 21 です。A の上限違反は x ≥ 3 ですから、そこに 3 個を先に置き、残り 2 個を配ります。

全体 = C(7,2) = 21
A が違反 = C(4,2) = 6
条件を満たす数 = 21 - 6 = 15

図2のように、違反する組から A の 3 個を取り除けば、残り 2 個の任意の配分に対応します。逆に A に 3 個を戻せば違反する元の組へ戻るので、引いた 6 通りに過不足はありません。

図2で取り除いた 3 個は、捨てた品物ではなく違反集合を数えるための目印です。元に戻したとき合計は 5 個に戻り、A は必ず 3 個以上になります。

別の確かめ方は A の個数で分ける方法です。A が 0、1、2 個のとき、残りを B と C に配る数はそれぞれ 6、5、4 通りです。合計は 15 通りとなり、各場合は A の個数が異なるので重なりません。

下限と複数の上限を扱う

【標準例題・やや難】同じ飴 7 個を区別のある袋 P、Q、R に全部配ります。P には 1 個以上 3 個以下、Q には 2 個以上 4 個以下、R には 0 個以上入れます。配分の数を整数で求めてください。

P、Q、R の個数を p、q、r として、P に 1 個、Q に 2 個を先に入れます。残りを P、Q、R に X、Y、Z 個入れると、X + Y + Z = 4、0 ≤ X ≤ 2、0 ≤ Y ≤ 2、Z ≥ 0 です。

上限を無視した数 = C(6,2) = 15
X ≥ 3 の数 = C(3,2) = 3
Y ≥ 3 の数 = C(3,2) = 3
両方の違反 = 0
条件を満たす数 = 15 - 3 - 3 = 9

両方が違反するには残り 4 個のうち少なくとも 6 個が必要なので、共通部分は空です。負の残数を得たときに、そのまま組合せを計算するのではなく、違反が同時には成立しないと判断します。

別解では X を 0、1、2 と固定します。Y はそれぞれ 0 から 2 まで選べ、Z は残りで決まるので 3 + 3 + 3 = 9 通りです。各組に先取りした 1 個と 2 個を戻せば合計 7 個で、P と Q の下限にも上限にも戻ります。

【発展例題・難】同じ札 8 枚を区別のある容器 D、E、F に全部入れます。空容器を許し、どの容器にも高々 3 枚入れます。配分の数を整数で求めてください。

上限を一度無視すると C(10,2) = 45 通りです。D の違反は 4 枚を先に D に入れた残りの配分なので C(6,2) = 15 通りで、E、F も同数です。ところが D と E が両方違反する組は、8 枚を先に使い切る (4,4,0) の 1 通りがあります。同様の共通部分が 3 組あります。

上限を無視した数 = C(10,2) = 45
1容器の違反の合計 = 3・C(6,2) = 45
2容器の違反の共通部分の合計 = 3・1 = 3
3容器同時の違反 = 0
条件を満たす数 = 45 - 45 + 3 = 3

3 容器同時の違反には少なくとも 12 枚が必要なので存在しません。答えを元に戻して確かめるには、各容器の空き容量を見ると早いです。容量の合計は 9 枚なので、空きは合計 1 枚です。空きのある容器の選び方が 3 通りで、元の配分は (2,3,3) とその位置を変えた組です。これが別解にもなります。

上限違反の共通部分を足し戻す理由は、公式を暗記するよりも各配分が何回数えられるかで見ると明確です。違反がない組は最初の全体で 1 回残り、1箇所違反の組は 1 − 1 = 0 回、2箇所違反の組は 1 − 2 + 1 = 0 回です。3箇所違反があり得る問題では 1 − 3 + 3 = 1 回残ってしまうため、その共通部分をさらに 1 回引きます。

引き過ぎを組で発見する

先ほどの 8 枚の問題で、全体 45 から 3 容器それぞれの違反 15 を引き、0 通りとするのは誤りです。例えば図3の (4,4,0) は D 違反と E 違反の両方に属します。全体で 1 回数えた後に 2 回引かれるため、差し引き -1 回となります。

図3の組を 1 回足し戻すと、その組の寄与は 0 回になります。他の 2 つの共通部分も同様です。条件に合わない組を数えたまま残すためではなく、余分に引いた分を戻すための操作です。

一方、違反条件を x ≥ 3 とすべきところを x ≥ 2 とすると、上限が 2 の箱にちょうど 2 個入る正しい配分まで除いてしまいます。「高々 2」の違反は「3 以上」です。等号の位置を、上限ちょうどの具体的な組で点検してください。

また、仕切りの式を用いる前に対象を確かめます。品物に名前が付いていれば、同じ個数の組でもどの品物が入るかで配分が変わります。ここでは同じ品物の個数の組と仕切りが一対一になることを利用しており、品物の順列を数える問題とは対象が違います。

練習問題

各問で品物は互いに区別せず、容器は名前で区別します。指定されたものを全部配り、答えは整数で求めてください。

1. 【標準】同じ石 4 個を箱 U、V、W に入れます。空箱を許し、U は高々 1 個、V と W はそれぞれ 4 個まで入ります。何通りですか。
2. 【標準】同じ花 6 本を花瓶 A、B、C に入れます。A と B には各 1 本以上、C は空でもよく、各花瓶の上限は 6 本です。何通りですか。
3. 【やや難】同じ棒 7 本を筒 A、B、C に入れます。空の筒を許し、A と B は各高々 3 本、C は高々 7 本です。何通りですか。
4. 【難】同じ片 6 個を箱 A、B、C に入れます。空箱を許し、各箱は高々 2 個です。何通りですか。
5. 【やや難】同じ球 5 個を袋 A、B、C に入れます。A は 2 個以上 3 個以下、B は 1 個以上 2 個以下、C は 0 個以上 1 個以下です。何通りですか。

練習問題の答えと考え方

1. 全体は C(6,2) = 15 通りです。U に 2 個以上入る違反は、U に 2 個を先取りして C(4,2) = 6 通りです。したがって 15 − 6 = 9 通りです。U が 0 個なら V、W は 5 通り、1 個なら 4 通りで、元の合計 4 個に戻しても 9 通りです。

2. A と B に 1 本ずつ入れ、残り 4 本を配ります。C(6,2) = 15 通りです。先取りを戻すと合計は 6 本で、各花瓶の個数は 6 本以下です。A に戻した後の本数を 1 から 5 まで固定すると、残りの選択肢は順に 5、4、3、2、1 通りで、合計も 15 通りです。

3. 上限なしでは C(9,2) = 36 通りです。A または B の違反は、それぞれ 4 本を先取りし C(5,2) = 10 通りです。両方の違反には 8 本必要で、7 本では不可能です。よって 36 − 10 − 10 = 16 通りです。元の A、B の個数はそれぞれ 0 から 3 までの 4 通りで、そのどの組でも C に残りを入れられるため 4・4 = 16 通りとも確かめられます。

4. 容量の合計は 2 + 2 + 2 = 6 個で、品物も 6 個です。どこかに空きがあれば他の箱が容量を超えるため、配分は (2,2,2) の 1 通りです。上限を無視すると C(8,2) = 28、1箱の違反は C(5,2) = 10 通り、2箱の違反は各 1 通り、3箱の違反は不可能なので、28 − 3・10 + 3 = 1 とも求まります。

5. A に 2 個、B に 1 個を先に置きます。残り 2 個を X、Y、Z として配ると、いずれも 0 以上 1 以下です。2 個を異なる 2 袋へ入れるので C(3,2) = 3 通りです。元の配分は (3,2,0)、(3,1,1)、(2,2,1) であり、いずれも合計 5 個かつ各袋の範囲内です。

条件が成立しない場合と境界の確認

配分の式を立てる前に、最小限必要な個数と、容器に入る最大の合計を比べます。例えば箱が 3 個あり、各箱に 2 個以上必要なのに品物が 5 個なら、最低でも 6 個必要なので 0 通りです。反対に各箱の上限が 2 個で品物が 7 個なら、容量の合計は 6 個なので 0 通りです。最低個数の合計と容量の合計の間に品物の数があれば、各箱の下限が上限以下であることも確認したうえで、残りを空き容量に順に入れて配分を作れます。

下限と上限が同じ箱では、その箱の個数は固定です。たとえば 2 個以上 2 個以下なら 2 個を先取りした後の空き容量は 0 です。違反を調べる際は移動後に 1 個以上入った組が違反となります。上限が 0 の箱も同様に必ず空であり、仕切りが隣接するか端にある列を許して扱います。

違反の数え上げで残りがちょうど 0 の場合は、成立しない場合と区別します。先取りした分で品物を使い切ったら、残りをどの箱にも入れない組が 1 通りあります。残りが負なら先取り自体が不可能なので 0 通りです。発展例題で 2 箱が違反する場合は残り 0 で 1 通り、3 箱が違反する場合は残りが負で 0 通りでした。この境界を取り違えると、足し戻しの数が変わります。

上限が複数あるとき、直接列挙と除外のどちらが短いかは残数によって変わります。残りが少ない場合は空き容量を配る方法が短く、上限が大きく違反が少ない場合は全体から除く方法が見通しを与えます。どちらを選んでも、先に何を1通りとするかを定め、分類した場合が重ならず全体を尽くすことを確かめます。

手元に残す要点

• 個数の組と仕切りの列の対応を作り、空箱を許すかを決めます。
• 下限を先に入れたら、残りの上限も同じ数だけ減らします。
• 上限違反は上限より 1 個多く先取りして数えます。
• 違反が重なるときは引いた回数を調べ、共通部分を調整します。
• 残数が負ならその場合は成立せず、元の条件へ戻して答えを確かめます。

どこで考えが止まるか

仕切りの式は書けても容量を反映できない場合は、まず上限ちょうどの組と、1 個超えた組を並べて区別します。両方を除いているなら不等号の境界に原因があります。共通部分の扱いに迷う場合は、1つの組が全体、各違反、共通部分で何回数えられるかを追います。

個別指導で確認するなら、答えの数だけでなく、先取りした個数を戻す操作を口頭で説明できるかが手がかりです。下限の移動後に残数や容量が負になるとき、式を続けず配分不能と判断できるかも確かめます。箱ごとの範囲を保った個数の組が、配分を正確に表します。