場合の数の考え方

1. ホーム
2. 本一覧
3. 武器になる数学A
4. 第1章 場合の数
5. 第1回 場合の数の考え方

最終更新日: 2024年5月22日

場合の数の問題では条件を満たすパターンがいくつあるかを求めます。数を数えること自体は日常生活でもするので特別なことではないですが、どう数えると効率的かを今一度、言語化してみます。

例えばある学校の全校生徒の人数を数えたいとします。もちろん一人ずつ数えてもいいのですが、人数が多く途中で数え間違いをしそうです。 そこで一旦、各クラスごとに人数を数えて、それらを合計すれば簡単に求められてミスも少なく、たとえミスが起きたとしてもどこで数え間違えたか探すのが容易になります。

場合の数の問題を解くときもこれと同じように考えます。ちょうど「1次不等式・絶対値と場合分け」に出てきた場合分けと似た考え方です。 ただ、1つ違うのが最後に重複カウントが無いかをチェックする点です。

先程の例で各クラスごとではなく、各部活ごとに集計した場合を考えてみます。（もちろん帰宅部の人数も数えます。） すると、同じように全校生徒の人数を求められそうですが、最後の集計で問題が発生します。

それは「兼部している人がいる場合」です。例えばAさんは水泳部と軽音楽部の両方に所属しているとします。 このときAさんは水泳部の部員としても軽音楽部の部員としてもカウントされることになります。 その結果、当然Aさんは1人しかいないにもかかわらず、単純に合計すると2人分になってしまいます。

これが場合の数特有の注意点です。数を数えているので重複カウントはOUTです。 しかし、毎回クラス分けのように綺麗に重複が発生しない分け方ができるとは限りません。 なので、なるべく重複が起きないように意識して、もし重複が起きてしまった場合はあとで引くようにしましょう。

場合の数は数えやすい場合ごとに分けて数えることと、もし重複カウントをしているときは後で必ず引くことが大切だとお伝えしました。そこで、ここからは複数の場合に分けたときにどのような重複カウントが発生するかを調べていきます。

まずは最も簡単なケースである「重複カウントが発生しない場合」を考えます。例題として$a,a,b$の3個の文字から2個を選んで1列に並べたときにできる文字列の数を求めてみます。この問題は

場合の数は数えやすい場合ごとに分けて考えるとはじめに説明しましたが、そのためにはよく登場する数え方を知っておく必要があります。 そこで、最も基本的な数え方を3つ紹介します。

突然ですがあなたは飲食店でメニューを見ています。メニューによると、セットメニューはごはん大・中・小またはパンが選べて、さらにデザートがA,B,Cの3種類から選べるそうです。 さて、このとき何通りの選び方が考えられるでしょうか？

答えはもちろん$12$通りです。おそらく頭の中で「ごはん・パンの選び方が$4$通りで、デザートの選び方が$3$通りだから$4\times3=12$（通り）」のように考えたと思います。 当たり前に感じるかもしれませんが、このように考えることでわざわざ$12$通りすべてを数えることなく計算によって場合の数を求めることができます。 これを積の法則といいます。

名前自体を覚える必要はありません。筆者もこの記事を書くまで知りませんでした。 先程のセットメニューの例で実際に計算できていた人は大丈夫です。 ただ、試験問題は複雑な状況を出してくるのでいくつか注意点を挙げておきます。

先程のセットメニューの例に照らし合わせて解説していきます。

まず1つ目は、仮に「※ただしパンを選択した場合、デザートは$A$で固定となります。」とあった場合、$4\times3$とするのはまずいです。 なぜならパンに対してデザートの選び方が$3$通り存在しないからです。これが「$m$通りそれぞれに対して本当に$n$通りあるのか確認する」の意味です。

次に2つ目は、例えばごはん・パンの選択をデザートの選択に変えた場合、つまり「デザートを$A,B,C$から選び、さらにデザートを$A,B,C$から選ぶ（2回同じものを注文してもよい）」場合に起きる問題です。 $4\times3$と同じように$3\times3$としたいところですが、ここで問題が発生します。その問題点とは、よく考えると先にデザート$A$を頼んでから$B$を頼むのと、逆に$B$を頼んでから$A$の頼むのは、 結果的にどちらも$A$と$B$を頼んでいて同じなのに、$3\times3$とするとこれらが重複カウントされている点です。これが2つ目の注意点です。

（この問題は重複組合せとよばれる問題で、正解は6通りです。解き方が気になる人は「重複組合せ（準備中）」をご覧ください。）

ジョーカーを除く$52$枚のトランプのカードから$5$枚のカードを取り出して左から右に1列に並べるときの場合の数を求めようと思います。 さすがに1つずつ数えていると日が暮れるのでなんとか計算で求めたいです。

場合の数でパッと解法が思いつかないときは地道に具体例を調べて状況を把握するのが効果的です。例えば??に示すように1番左に♠A（スペードのエース）を並べたとします。

すると、その右隣に並べるカードは♠A以外の$51$枚から選ぶことになります。ここで、1番左が♠Aでない場合も、その右隣に並べるカードは残りの$51$枚から選ぶことに気づくでしょうか。 どの$51$枚になるかは一番左のカードに依存しますが、枚数自体は変わりません。

ということは先程の積の法則を使うことができます。1番左のカードの選び方が$52$通りあり、そのおのおのの場合について、左から2番目のカードの選び方が$51$通りあるので、 この2枚の選び方は$52\x51$（通り）になります。

同様にして$5$枚並べることを考えると、その並べ方は$52\x51\x50\x49\x48$（通り）と計算することができます。 つまり、$311{,}875{,}200\,\tx{通り}$になります。 今考えたことを一般化すると、次のようになります。

先程の5枚のカードを1組の手札にしてポーカーをしようと思います。このとき考えられる手札は何通りあるでしょうか？ 1列に並べる場合と異なり、今度は5枚の順番を区別しないのがポイントです。

実は場合の数で数を数えるときは基本的にすべて区別する方が数えやすいです。 というのは、区別しないと重複カウントが発生しやすくなるからです。 場合の数において区別する・しないの違いは重要なので問題を解くときは意識しましょう。

具体的には順列のときは以下の??の2つを区別しますが、今回は区別しません。

勘の良い人はこの具体例を見て気づいたかもしれませんが、この順序の区別あり・なしによる重複カウントの発生の仕方には法則性があります。 あるポーカーの手札に対して順列を作ると、5枚を一列に並べるため$5!\,\tx{通り}$の並べ方があります。 逆に言えば先程は区別していた$\bm{5!\,\tx{通り}}$が今回は1つにまとめられることになります。

したがって、順列のときの答えを利用すればポーカーの手札の組合せも求められそうです。計算すると、次のようになります。

\begin{align}&\f{\permut{52}{5}}{5!}\\[0.7em]={}&\f{52\x51\x50\x49\x48}{5\x4\x3\x2\x1}\\[0.7em]={}&2{,}598{,}960\end{align}

となり、$2{,}598{,}960\,\tx{通り}$になります。 今考えたことを一般化すると、次のようになります。

ポーカーの例で考えたように$n$個から$r$個取る組合せは、$n$個から$r$個取る順列から重複カウント分を逆算すればよいので、$\permut{n}{r}=\combo{n}{r}\x r!$より

\begin{align}&\combo{n}{r}\\[0.7em]={}&\f{\permut{n}{r}}{r!}\\[0.7em]={}&\f{n(n-1)\dotsm(n-r+1)}{r(r-1)\dotsm1}\q\tx{(分子も分母も$r$個の数字の積)}\\[0.7em]={}&\f{n(n-1)\dotsm(n-r+1)}{r(r-1)\dotsm1}\x\f{(n-r)(n-r-1)\dotsm1}{(n-r)(n-r-1)\dotsm1}\\[0.7em]={}&\f{n!}{r!(n-r)!}\end{align}

となります。実際に数値を計算するときは3番目の式を使いましょう。 この式に$r=n,0$を代入するとわかるように$\bm{\combo{n}{n}=1,}$ $\bm{\combo{n}{0}=1}$です。また、$\combo{n}{r}$には上に書いたような性質が成り立ちます。証明とその意味は以下の補足をご覧ください。

今回の内容をまとめると、

ログインすると学習データを保存できます。アカウントをお持ちでない方は新規登録