【第13章】数え上げの技術──重複・仕切り・対応づけ

数強塾オリジナル無料講座『数学の原理』第13章
前章の「数えるとは対応をつけること」を、技術のレベルまで引き上げます。○と仕切り棒という、たった1つの絵を覚えるだけで、重複組合せも、方程式の整数解も、「同じものを配る」問題も、全部同じ問題になります。そして、多くの人が混乱する「区別するのはどっちだっけ」問題に、表1枚で決着をつけます。

まず「重複を許す」とはどういうことか

藤原です。第13章です。

前章では「\(n\) 個から \(r\) 個を選ぶ」を扱いました。今回は同じものを何度選んでもいい場合です。

いちばん簡単なのは重複順列。たとえば「3種類のジュースから、5回買う（同じものを何度買ってもよい、買った順番も区別する）」なら、毎回3通りずつなので

\[3^5 = 243\]

積の法則そのものです。一般に \(n\) 種類から \(r\) 回選ぶ（順序あり・重複あり）なら \(n^r\)。ここは問題ないでしょう。

難しいのは、順序を区別しないほうです。

例題　りんご・みかん・ぶどうの3種類の果物が、それぞれたくさんある。この中から合計5個を買う方法は何通りか。（同じ種類を何個買ってもよい。買う順番は区別しない。）

「りんご2個、みかん0個、ぶどう3個」のような買い方を数えます。どう数えればいいでしょうか。

○と仕切り棒──この絵がすべてを解決する

ここで、前章の「翻訳」を使います。買い方を、記号の列に翻訳するのです。

買う果物を○で表し、種類の切れ目を仕切り棒「|」で表します。3種類なので、仕切りは2本です。

「りんご2個・みかん0個・ぶどう3個」は、○○||○○○。「りんご1個・みかん3個・ぶどう1個」は、○|○○○|○。

逆に、○5個と|2本を並べた列を作れば、それに対応する買い方がちょうど1つ決まります（仕切りの前が1種類目、間が2種類目、後ろが3種類目）。

買い方　⟷　○5個と|2本を並べた列
この対応は1対1。だから個数は等しい。

あとは「同じものを含む順列」です。全部で7個の記号のうち、どの2か所を仕切りにするかを選べばよいので

\[{}_7 \mathrm{C}_2 = 21\]

答え：21通り

一般化しておきましょう。

\(n\) 種類から重複を許して \(r\) 個選ぶ方法の数
＝　○ \(r\) 個と仕切り \(n-1\) 本の並べ方
\[{}_{r+n-1} \mathrm{C}_{n-1} = {}_{r+n-1} \mathrm{C}_{r}\]

この公式を覚える必要はありません。「○が \(r\) 個、仕切りが \(n-1\) 本」という絵さえ描ければ、その場で作れます。むしろ絵だけを覚えてください。公式を覚えると、\(n\) と \(r\) のどっちがどっちだったか必ず混乱します。

同じ絵が、方程式の整数解も数える

次の問題を考えてください。

\(x + y + z = 5\) を満たす0以上の整数の組 \((x,\ y,\ z)\) は何個か。

……気づきましたか。これはさっきの果物の問題とまったく同じです。\(x\) がりんごの個数、\(y\) がみかんの個数、\(z\) がぶどうの個数。

\[{}_{7} \mathrm{C}_{2} = 21\]

見た目がまったく違う2つの問題が、同じ問題だった。これが対応づけの威力です。

では、条件が「正の整数」（つまり全員1個以上）だったら？

ここで第12章の問題8と同じ手を使います。ずらして翻訳する。

\[x’ = x – 1, \quad y’ = y – 1, \quad z’ = z – 1\]

とおくと、\(x,y,z \ge 1\) は \(x’,y’,z’ \ge 0\) と同値になり、方程式は

\[x’ + y’ + z’ = 2\]

これは○2個と仕切り2本なので \({}_4 \mathrm{C}_2 = 6\) 個。

「1個以上」は、先に1個ずつ配ってしまえ。
配ってしまえば、残りは「0個以上」の問題になり、いつもの○と仕切りに戻ります。この一手はとてもよく使います。

最大の混乱ポイント：何を区別するのか

「配る」問題で、多くの人が混乱します。「玉は区別する？　箱は区別する？」。ここを表1枚で整理します。

大事なポイントを整理します。

• 玉を区別するなら、玉のほうから考える（各玉がどの箱に行くかを選ぶ）
• 玉を区別しないなら、箱のほうから考える（各箱に何個入るかを決める＝○と仕切り）
• 箱を区別しない場合は、高校では「書き出す」のが正解。公式はありません（玉も箱も区別しないケースは、大学で「分割数」として扱いますが、簡単な式はありません）

「箱を区別しない」を \(k!\) で割って処理していいのは、どの箱も空でないときだけです。空箱があると、同じ配り方が \(k!\) 通り未満しか現れないことがあり、\(k\) 対1対応が崩れます。均等でない重複は割れないという第12章の原則です。

「空箱なし」は包除原理で

「玉を区別する・箱を区別する・どの箱も空でない」という条件は、入試の定番です。

例題　区別できる5個の玉を、区別できる3つの箱に、どの箱も空にならないように入れる方法は何通りか。

直接数えるのは大変です。全体から「空箱がある場合」を引きます（余事象）。

全体：\(3^5 = 243\) 通り。

ここで「箱Aが空」「箱Bが空」「箱Cが空」という3つの集合を考えます。求めたいのは、この3つのどれにも入らないものの個数です。

• 「箱Aが空」＝残り2箱に入れる＝\(2^5 = 32\)。B, C も同じで、合計 \(3 \times 32 = 96\)
• 「AもBも空」＝Cだけに入れる＝\(1^5 = 1\)。3組あるので \(3 \times 1 = 3\)
• 「A も B も C も空」＝どこにも入れられない＝\(0\)

包除原理（足しすぎたら引き、引きすぎたら足す）で、「少なくとも1箱が空」の個数は

\[96 – 3 + 0 = 93\]

したがって求める個数は

\[243 – 93 = 150\]

答え：150通り

包除原理を式で書くとこうです。

\[|A \cup B \cup C| = |A|+|B|+|C| – |A \cap B| – |B \cap C| – |C \cap A| + |A \cap B \cap C|\]

2個のときの \(|A|+|B|-|A \cap B|\) の延長です。ベン図を描けば、なぜ足したり引いたりするのかが目で見えます。3つの円が重なった真ん中の部分が、3回足されて3回引かれて0回になっているので、最後に1回足し戻す。それだけです。

【原理】この章の芯

① 重複を許して選ぶ問題は、○と仕切り棒の列に翻訳する。
② ○が \(r\) 個、仕切りが（種類数 −1）本。公式ではなく絵を覚える。
③ 「1個以上」は、先に1個ずつ配ってから0個以上の問題にする。
④ 玉を区別するなら玉から、区別しないなら箱から考える。
⑤ 「空箱なし」は、全体から包除原理で引く。

オリジナル問題で確かめる

問題1（重複順列）

1. 4種類の記号から重複を許して6文字の暗証番号を作る方法は何通りか。
2. 区別できる6個の玉を、区別できる4つの箱に入れる方法は何通りか（空箱があってもよい）。

問題2（重複組合せ）

4種類のパンがそれぞれたくさんある。この中から合計8個を買う方法は何通りか（同じ種類を何個買ってもよく、買う順番は区別しない）。

問題3（方程式の整数解）

次の個数を求めよ。

1. \(x+y+z = 10\) を満たす0以上の整数の組 \((x,y,z)\) の個数
2. \(x+y+z = 10\) を満たす正の整数の組 \((x,y,z)\) の個数
3. \(x+y+z \le 10\) を満たす0以上の整数の組 \((x,y,z)\) の個数

問題4（条件つき）

\(x+y+z = 12\) を満たす整数の組で、\(x \ge 1,\ y \ge 2,\ z \ge 3\) を満たすものの個数を求めよ。

問題5（4通りの配り方）

玉6個を3つの箱に入れる。次の各場合について、方法の総数を求めよ（空箱があってもよい）。

1. 玉も箱も区別する
2. 玉は区別しないが、箱は区別する
3. 玉も箱も区別しない

問題6（空箱なし・玉を区別する）

区別できる6個の玉を、区別できる3つの箱に、どの箱も空にならないように入れる方法は何通りか。

問題7（空箱なし・箱を区別しない）

問題6で、箱を区別しない場合は何通りか。

問題8（単調な列）

\(1 \le a \le b \le c \le 5\) を満たす整数の組 \((a,\ b,\ c)\) は何個あるか。

問題9（包除原理）

1から300までの整数のうち、2でも3でも5でも割り切れないものは何個あるか。

解答と解説

問題1の解答

(1)　各桁が4通りずつなので \(4^6 = 4096\)。4096通り。

(2)　各玉が「どの箱に行くか」を4通りから選ぶので \(4^6 = 4096\)。4096通り。

この2つが同じ答えなのは偶然ではありません。「6個のもの、それぞれに4つの選択肢」という同じ構造だからです。問題文の見た目が違っても、構造が同じなら答えも同じ。構造を見抜く目を鍛えてください。

問題2の解答

○が8個、仕切りは \(4-1 = 3\) 本。全部で11個の記号のうち、どの3か所を仕切りにするかを選ぶので

\[{}_{11} \mathrm{C}_{3} = \frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165\]

答え：165通り

問題3の解答

(1)　○10個、仕切り2本。\({}_{12}\mathrm{C}_2 = \dfrac{12 \cdot 11}{2} = 66\)。66個。

(2)　先に1個ずつ配ります。\(x’=x-1\) などとおくと \(x’+y’+z’ = 7\)（0以上）。○7個、仕切り2本で

\[{}_{9}\mathrm{C}_2 = \frac{9 \cdot 8}{2} = 36\]

答え：36個

(3)　不等式なので、そのままでは○と仕切りが使えません。そこで「余り」を受け止める4つ目の箱を用意します。

\[w = 10 – (x+y+z)\]

とおくと \(w \ge 0\) で、条件は

\[x + y + z + w = 10\]

という等式になりました。逆にこの等式の0以上の解を取れば、元の不等式の解が1つ決まります。1対1対応です。

○10個、仕切り3本なので

\[{}_{13}\mathrm{C}_3 = \frac{13 \cdot 12 \cdot 11}{6} = 286\]

答え：286個

「不等式は、余りを受け止める変数を足して等式にする」。これは非常に強力な一手です。「\(\le\) を見たらダミー変数」と覚えておいてください。

問題4の解答

下限がバラバラですが、やることは同じ。先に \(1+2+3 = 6\) 個を配ってしまいます。

\[x’ = x-1, \quad y’ = y-2, \quad z’ = z-3\]

とおくと、条件は \(x’,y’,z’ \ge 0\) かつ

\[x’ + y’ + z’ = 12 – 6 = 6\]

○6個、仕切り2本で

\[{}_{8}\mathrm{C}_2 = \frac{8 \cdot 7}{2} = 28\]

答え：28個

問題5の解答

(1) 玉も箱も区別する：各玉が3通りずつ。\(3^6 = 729\)。729通り。

(2) 玉は区別しない、箱は区別する：○6個、仕切り2本。

\[{}_{8}\mathrm{C}_2 = 28\]

28通り。

(3) 玉も箱も区別しない：これは「6を3つ以下の正の整数の和に分ける（順序は無視、0個の箱も許す）」ということ。公式がないので書き出します。3つの箱の個数を大きい順に並べて

\[(6,0,0),\ (5,1,0),\ (4,2,0),\ (4,1,1),\ (3,3,0),\ (3,2,1),\ (2,2,2)\]

数えて7通り。7通り。

書き出すときは、必ず「大きい順に並べる」というルールを決めてください。ルールがないと、もれと重複が両方起きます。今回は「第1成分 ≥ 第2成分 ≥ 第3成分」と決めたので、\((5,1,0)\) は書くが \((1,5,0)\) は書かない、と機械的に判断できました。

問題6の解答

全体は \(3^6 = 729\) 通り。ここから「少なくとも1箱が空」を引きます。

• 特定の1箱が空：残り2箱に入れる \(2^6 = 64\) 通り。箱の選び方が3通りなので \(3 \times 64 = 192\)
• 特定の2箱が空：残り1箱だけ \(1^6 = 1\) 通り。2箱の選び方が3通りなので \(3 \times 1 = 3\)
• 3箱とも空：\(0\) 通り

包除原理より「少なくとも1箱が空」は \(192 – 3 + 0 = 189\)。したがって

\[729 – 189 = 540\]

答え：540通り

問題7の解答

問題6は「箱を区別する」場合でした。どの箱も空でないので、箱の並べ替え \(3! = 6\) 通りずつが同じ配り方に対応します。

ここで「本当に均等に6個ずつか」を確認します。箱が区別されない状況で、3つの箱の中身はすべて異なる集合です（同じ玉は2つの箱に入れないので）。中身が全部違うので、3つの箱を並べ替えた6通りはすべて別々の（箱を区別した）入れ方になります。だからちょうど6個ずつ。均等です。

\[\frac{540}{6} = 90\]

答え：90通り

「均等かどうかの確認」を1行入れました。この確認をサボると、空箱ありの場合に必ず事故ります。たとえば空箱を許すと、\((6,0,0)\) 型の入れ方は箱の並べ替えで3通りしか現れず、6通りにはなりません。

問題8の解答

\(a \le b \le c\) という「等号つきの単調増加」がポイントです。等号が入るので、これは「1から5までの5種類から、重複を許して3個選ぶ」ことと同じになります。

なぜか。選んだ3個を小さい順に並べれば \(a \le b \le c\) が1つ決まり、逆に \((a,b,c)\) が決まれば選んだ3個が決まるからです。1対1対応です。

○3個、仕切りは \(5-1 = 4\) 本なので

\[{}_{7}\mathrm{C}_4 = {}_{7}\mathrm{C}_3 = 35\]

答え：35個

検算：小さい範囲で確かめます。\(1 \le a \le b \le 3\) を満たす \((a,b)\) は \((1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\) の6個。公式では ○2個・仕切り2本で \({}_4\mathrm{C}_2 = 6\)。一致します。

等号つきの単調増加 → 重複組合せ。等号なしの単調増加 → ふつうの組合せ。
\(a \lt b \lt c\) なら「5個から3個選ぶ」で \({}_5\mathrm{C}_3 = 10\) です。等号があるかないかで、まったく別の公式になるので、問題文の不等号を必ず確認してください。

問題9の解答

「2でも3でも5でも割り切れない」を直接数えるのは大変なので、余事象を取ります。「2または3または5で割り切れる」を数えて、300から引く。

2の倍数の集合を \(A\)、3の倍数を \(B\)、5の倍数を \(C\) とします。

• \(|A| = 300 \div 2 = 150\)
• \(|B| = 300 \div 3 = 100\)
• \(|C| = 300 \div 5 = 60\)
• \(|A \cap B|\)（6の倍数）\(= 50\)
• \(|B \cap C|\)（15の倍数）\(= 20\)
• \(|C \cap A|\)（10の倍数）\(= 30\)
• \(|A \cap B \cap C|\)（30の倍数）\(= 10\)

包除原理より

\[|A \cup B \cup C| = 150+100+60-50-20-30+10 = 220\]

したがって

\[300 – 220 = 80\]

答え：80個

別解として、こういう見方もできます。300は \(2 \times 3 \times 5 = 30\) の倍数なので、1〜30の中で条件を満たす数を数えて10倍すればよい。1〜30で2・3・5のどれでも割れないのは \(1, 7, 11, 13, 17, 19, 23, 29\) の8個。よって \(8 \times 10 = 80\)。一致しました。

ちなみにこの8という数は、\(30 \times \left(1-\dfrac12\right)\left(1-\dfrac13\right)\left(1-\dfrac15\right) = 30 \cdot \dfrac12 \cdot \dfrac23 \cdot \dfrac45 = 8\) と計算できます。包除原理を展開すると、実はこの積の形になっているのです。

よくある誤解

誤解1：重複組合せの公式で \(n\) と \(r\) を取り違える
公式ではなく絵で考えてください。「○が選ぶ個数、仕切りが種類数マイナス1」。絵を描けば取り違えません。

誤解2：玉を区別しないのに \(k^n\) を使う
\(k^n\) は「各玉が行き先を選ぶ」という数え方なので、玉が区別できることが前提です。

誤解3：空箱を許したまま \(k!\) で割る
重複が均等でなくなるので割れません。空箱なしの場合だけ使える手です。

誤解4：\(\le\) と \(\lt\) を区別せずに数える
等号があると重複組合せ、なければふつうの組合せ。まったく別の答えになります。

よくある質問

Q. ○と仕切りは、いつ使えばいいですか？

「合計が決まっていて、それを何種類かに振り分ける」という形が見えたら使えます。果物を買う、方程式の整数解、玉を箱に入れる、お金を分ける。全部この形です。

Q. 包除原理は3つより多くても使えますか？

使えます。「奇数個の共通部分は足す、偶数個は引く」というルールが続きます。ただし4つ以上になると項が増えて大変なので、入試では別の見方（問題9の別解のような）が用意されていることが多いです。

Q. 「箱を区別しない」問題が出たらどうすればいいですか？

まず「箱を区別する」で数える。そのあと、空箱がなければ \(k!\) で割る。空箱があるなら、空箱の個数で場合分けするか、素直に書き出す。いきなり「区別しない」で数えようとしないことが最大のコツです。

次の章へ

数え上げの技術がひととおり揃いました。次の第14章からは確率です。確率は「場合の数の割り算」だと思われがちですが、そこにいちばん大きな落とし穴があります。「同様に確からしい」とは何なのか。ここを疑えるかどうかで、確率の正答率が変わります。

◀ 第12章：「場合の数」のいちばん大切なこと──数えるとは1対1対応
▶ 第14章：「確率」のいちばん大切なこと──「同様に確からしい」を疑う
▶ 『数学の原理』全24章の目次に戻る