重複組合せはなぜ仕切りを使うの？【整数解の個数を求める問題で鍛えよう】

2019年10月24日2022年2月21日

こんにちは、ウチダです。

いつもお読みいただきましてありがとうございます。

さて、場合の数の最後の難関。「重複組合せ(ちょうふくくみあわせ)」の解き方は理解できましたか？

というのも、重複組合せの問題はとっても理解しづらい考え方を使って解きます。

よく

[ふきだし set=”悩む男性”]重複組合せの公式の意味がわからない…。そもそも「仕切り」って何？？？[/ふきだし]

[ふきだし set=”悩む女性”]重複組合せの難問、たとえば整数解の個数を求める問題などの解き方が難しいなぁ。[/ふきだし]

こういった声を耳にします。

よって本記事では、重複組合せの問題において“仕切り”を使う理由から、重複組合せの応用問題や入試問題まで、

東北大学理学部数学科卒
教員採用試験に１発合格　→　高校教諭経験アリ
（専門は確率論でした。）

の僕がわかりやすく解説します。

重複組合せはなぜ仕切りを使うの？【玉の個数の問題で解説】　

重複組合せにおいて注意すべき点は、以下の $2$ 点になります。

「それぞれ何個使うか」がわからない。
順列ではないから、並び替えが発生しない。

よく比較されるものとして「重複順列(ちょうふくじゅんれつ)」があります。

重複順列も注意点 $1$ 番の「何個使うかわからない」は満たしていますが、順列であるが故に注意点 $2$ 番の「並び替えが発生しない」は満たしていません。

[ふきだし set=”ウチダ”]思い出してみると、重複順列の総数はとっても簡単に求めることができましたよね。ようは、「注意点 $1$ 番と $2$ 番を同時に満たしてしまうから、重複組合せは難しい」ということになります。重複順列の詳しい解説は「重複順列の問題６選とは【公式よりも応用問題の解き方が大切です】」の記事をご覧ください。[/ふきだし]

ここからは例題を使って考えていきましょう。

例題.　$a$、$b$、$c$ と書かれた玉がたくさんある袋の中から $6$ 個を取り出すとき、玉の組合せは何通りあるか。

注意点を思い出してみると…

「 $a$ の玉を何個使うか」や「 $b$ の玉を何個使うか」はわかりません。( $0$ 以上 $6$ 以下の間の数。)
「玉の組合せ」なので、たとえば $aaabbc$ と $abbaac$ は同じ場合であるとします。

たしかに注意点 $1$、$2$ どちらとも満たしていますね。

さて、ここで登場するのが“仕切り”という考え方です！

どういうことかは、解答の流れの中で説明していきたいと思います。

【解答】

並び替えを考えてはいけないため、左から順に $a$、$b$、$c$ と固定して考える。

また、何個使うかもハッキリと分からないが、合計で $6$ 個使うことだけは決まっている。

よって、まずは玉 $a$、$b$、$c$ を $〇$ に統一し、区別をなくす。

次に、「 $a$ のエリア」「 $b$ のエリア」「 $c$ のエリア」の $3$ つに分割するために、仕切り $|$ を $2$ つ用意する。

以上より、$6$ つの $〇$ と $2$ つの $|$ の順列の総数を求めればよいことがわかるので、$\displaystyle \frac{8!}{6!2!}={}_8{C}_{2}=28$ 通りである。

(解答終了)

考え方の流れは大体掴めましたか？

このように、注意点を明確にしながら考えを巡らせることで、結局は「同じものを含む順列」の話に帰着させることができます。

≫参考記事：同じものを含む順列と組合せは”同じ”です【問題４選もあわせて解説】

また、以上の話を一般化すると、以下の公式ができます。

【重複組合せの公式】
$n$ 種類から $r$ 個取る重複組合せの総数 ${}_n{H}_{r}$ は$${}_n{H}_{r}={}_{n+r-1}{C}_{r}$$

[ふきだし set=”ウチダ”]$3$ 種類のものを使うとき、仕切りは $2$ つ必要でした。これを一般化すると、$n$ 種類のものに対して仕切りが $n-1$ 個必要になる、ということですね。この公式をいきなり覚えようとすると頭が混乱するので、ぜひ意味合いから理解し自然と覚えるようにしてみて下さい。[/ふきだし]

重複組合せの必ず押さえたい応用問題

以上を踏まえ、ここからは重複組合せの応用問題について考えていきます。

まずは、一番代表的かつ必ず押さえたい応用問題です。

問題.　$4$ 個の文字 $a$、$b$、$c$、$d$ から重複を許して $7$ 個取る組合せの総数を求めなさい。ただし、どの文字も必ず $1$ つ以上使うものとする。

最後の一文、

「どの文字も必ず $1$ つ以上使う」ここがポイントです。

重複組合せの基本では、使わない玉(文字)があってもOKでしたが、この問題ではそれがダメです。

ということは…基本に沿って考えると、以下のような解答が導けるはずです！！

【解答】

どの文字も最低 $1$ つは使うのであれば、前もって $1$ つずつ抜き出して考えればよいと気づく。

したがって、${}_4{H}_{3}$ を求めればいいので、$${}_4{H}_{3}={}_6{C}_{3}=\frac{6・5・4}{3・2・1}=20 (通り)$$

(解答終了)

いかがでしょう。

重複組合せの基本に立ち返って、問題を解くことができましたね。

[ふきだし set=”ウチダ”]重複組合せは、「選ばない（ $0$ 個の）ものがあっても良い」という考え方が前提なので、それに上手く帰着させてあげましょう。[/ふきだし]

重複組合せの難問３選

さて、以上の基本と簡単な応用を踏まえて、重複組合せの難問を $3$ 問解いてみましょうか。

具体的には、

整数解の個数の問題（不等式バージョン）
一定の順序を含む順列（「 $≦$ 」バージョン）
早稲田大学の入試問題

この $3$ つを順に解いていきます。

整数解の個数の問題（不等式バージョン）

問題.　$x+y+z≦8$（$x≧0$、$y≧0$、$z≧0$）を満たす整数解の組は何通りあるか求めなさい。

たとえば、「 $x+y+z=8$（$x≧0$、$y≧0$、$z≧0$）」というふうに、不等式でなく方程式であれば単純な重複組合せの問題になります。

つまり、この問題に対して

[ふきだし set=”悩む男性”]どうにかこうにか、不等式を方程式に変える方法はないかな～。[/ふきだし]

という見方で考えることができれば、ゴールは目の前です！！

↓↓↓

【解答】

$8-(x+y+z)=w$ と、新しい変数 $w$ を定める。

すると仮定より、$w≧0$ であり、また$$x+y+z+w=8$$となる。

したがって、$4$ 種類から $8$ 個取る重複組合せになるので、

\begin{align}{}_4{H}_{8}&={}_{11}{C}_{8}\\&={}_{11}{C}_{3}=165 (通り)\end{align}

(解答終了)

どんな問題になっても「重複組合せの基本パターンに帰着させる」

これを忘れずに問題を解いていきましょう。

一定の順序を含む順列（≦バージョン）

問題.　次の条件を満たす $5$ 桁の自然数

\begin{align}N=x_4×10^4+x_3×10^3+x_2×10^2+x_1×10+x_0\end{align}

※この数式は横にスクロールできます。(スマホでご覧の方対象。)
の場合の数を求めよ。
ただし、$0≦x_i≦9（i=0,1,2,3,4）$であり、$x_4≠0$ だとする。
$$条件：x_0≦x_1≦x_2≦x_3≦x_4$$

この問題を解釈すると、つまり $54321$ とか $75520$ みたいに、「各位の数がどんどん小さくなってく自然数」をすべて数え上げればOKです。

さあ、一見するとこの問題は、”順列”のようにも思えてきます。

しかし…！

実は注意深く考えてみると、これは重複組合せの問題であることがわかるんですね～。

↓↓↓

【解答】

たとえば、$54321$ は題意を満たすが、$12345$ や $52431$ などは題意を満たさない。

ここから考えるに、$1$ つの組合せに対して解は $1$ つしかない。

つまり、重複組合せの考え方ができる。

よって、$10$ 種類から $5$ 個取る重複組合せになるので、${}_{10}{H}_{5}={}_{14}{C}_{5}=2002$ 通りと求まるが、

このやり方だと $00000$ が含まれてしまい、この場合のみ不適である。

したがって、答えは $2002-1=2001$ 通りである。

(解答終了)

「 $10$ 種類（ $0$ ～ $9$ ）から $5$ 個（一の位～万の位）取る重複組合せの総数は？」と聞かれると即答できますが、実際の問題でこれを見抜くには慣れが必要ですね。

また、最後の $00000$ の場合は、重複組合せで表現すると

$〇〇〇〇〇｜｜｜｜｜｜｜｜｜$

となり、これは除かなくてはいけません。

[ふきだし set=”ウチダ”]繰り返しになりますが、重複組合せは「選ばない（ $0$ 個の）ものがあっても良い」という考え方が前提です。ものすごく便利な考え方である反面、注意を怠ってはいけません。[/ふきだし]

【入試問題】早稲田大学

問題.　$x+y+z+w=16$（$x≧6$、$y≧4$、$z≧2$、$w≧0$）を満たす整数解の組は何通りあるか求めなさい。
※2015年早稲田大・人間科学AB入試より改題

それでは最後に、早稲田大学の入試問題にチャレンジしてみましょう。

ただ、今までの話がしっかりと理解できていれば、もしかすると以上 $3$ 問の中で一番簡単かもしれません。

ぜひ、基本に立ち返ってお考え下さい。

↓↓↓

【解答】

$X=x-6$、$Y=y-4$、$Z=z-2$ と新たに変数 $X$、$Y$、$Z$ を定める。

すると、

\begin{align}x+y+z+w=16 ⇔ X+Y+Z+w=4　……①\end{align}

※この数式は横にスクロールできます。(スマホでご覧の方対象。)

$$X≧0 , Y≧0 , Z≧0 , w≧0　……②$$

よって、①、②より単純な重複組合せの総数を求める問題に帰着する。

したがって、$4$ 個の $〇$ を $3$ 個の $|$ で分ければよいので、$\displaystyle \frac{7!}{4!3!}={}_7{C}_{3}=35$ 通りである。

(解答終了)

[ふきだし set=”ウチダ”]もちろん「 $a$ を $X$ 個、$b$ を $Y$ 個、$c$ を $Z$ 個、$d$ を $w$ 個」として、$4$ 種類の文字 $a$、$b$、$c$、$d$ から重複を許して $4$ 個取る組合せと考え、${}_4{H}_{4}={}_7{C}_{3}$ と、公式を用いて解いてもOKです。[/ふきだし]