場合の数から順列・組合せ、組合せ論へ｜武蔵野個別指導塾

樹形図で数える工夫が、順列・組合せや二項定理、大学の包除原理と母関数へつながります。順番を区別する理由と、重複を取り除く仕組みを具体例でたどり、公式を選ぶ前に考える問いを身につけましょう。

場合の数から順列・組合せ、組合せ論へ

書き出した答えを、どう信じるか

よくあるのは、文化祭の係を決める相談のあと、教室の後ろの机で「代表と副代表を選ぶのも、係を選ぶのも、同じ人数なら同じ数では」とノートに書く場面です。人を選ぶという言葉は同じでも、役割を入れ替えたときに別の結果と考えるかどうかで、答えは変わります。場合の数で最初に必要なのは、計算の速さより、この違いを言葉にすることです。

「全部書けばよいのに、なぜ公式を習うのでしょうか」。この問いには理由があります。少ない人数なら書き出せても、人数や条件が増えると、一覧を眺めるだけでは漏れや重複を見つけにくくなります。数学は、数え終わった答えだけでなく、全部をちょうど一度ずつ数えたという説明も求めます。

中学の樹形図や表、高校の順列と組合せ、大学の組合せ論は、その説明の道具を広げていく学びです。同じものを別々に数えていないか、まだ数えていないものが残っていないか。この問いを手元に置いて、先の数学まで歩いてみましょう。

中学の樹形図と表は、数える順番を決める道具

場合の数とは、決められた条件を満たす結果が何通りあるかという数です。ここで大事なのは「結果」を先に決めることです。赤・青・白の札から異なる札を選び、左と右に並べるなら、赤青と青赤は別の結果です。袋に入れる札を選ぶだけなら、どちらも赤と青を選んだ同じ結果になります。

まず、左と右に並べる場合を考えます。左の札を赤に決めると、右は青か白です。左を青にすると、右は赤か白です。左を白にすると、右は赤か青です。こうして最初の選択ごとに枝を分け、その先に次の選択を書く図が樹形図です。

できる並びは、赤青・赤白・青赤・青白・白赤・白青で、合計は 3 × 2 = 6 通りです。左に置く札を選ぶ方法が 3 通りあり、そのどれについても右に置く札は 2 通りだから、かけ算で求められます。樹形図の枝の先端と、完成した並びが一対一に対応していることが、この計算を支えています。

表にする方法もあります。行を左の札、列を右の札とすると、全部で 3 × 3 = 9 個のますができます。同じ札を繰り返し使えないので、赤赤・青青・白白の 3 個を除き、9 − 3 = 6 通りです。樹形図では許される枝だけを伸ばしました。表ではいったん広く数え、条件に合わないますを取り除きました。数え方は違っても、最後に残る並びは同じです。

この比較から、たし算とかけ算の役割も見えてきます。重ならない場合に分け、それぞれの個数を合わせるときはたし算です。段階を踏んで選び、各段階の選択肢の数がそれまでの選び方によらず一定なら、かけ算が使えます。「選ぶ問題だからかける」と決めるのではなく、どんな枝分かれになっているかを確認します。

一方、選んだ札を袋に入れるだけなら、赤青と青赤を別々に数える必要はありません。先ほどの 6 通りは、赤と青、赤と白、青と白という各組を、それぞれ 2 回ずつ数えています。そこで 6 ÷ 2 = 3 通りとなります。ただし、いつでも最後に 2 で割ってよいわけではありません。どの組も同じ回数だけ重複している、と説明できることが必要です。

樹形図を書くときは、枝を思いついた順に足すより、赤・青・白という順を毎回そろえると確認しやすくなります。また、完成した結果のうち一つを指し、「これはどの枝の先にあるか」と逆向きにたどってみましょう。どの結果も必ず置き場所を持ち、その置き場所が一つに定まるなら、漏れと重複の両方を点検できます。

場合の数は確率の計算にも登場しますが、数えた結果がすべて同じ起こりやすさだとは限りません。数えることと、起こりやすさを考えることは分けて扱います。ここではまず、条件に合う結果の一覧を正しく作ることに集中しましょう。

高校では、並べることと選ぶことを式で区別する

高校の順列は、異なるものからいくつかを選び、順番をつけて並べる考え方です。異なる n 個から r 個を選んで並べる数を P(n,r) と書くことにします。n と r は整数で、0 ≦ r ≦ n とします。最初に選べるものは n 個、次は残りの n−1 個というように、樹形図の枝の数をまとめたものが順列の式です。

階乗 n! は、正の整数 n について 1 から n までの整数をすべてかけた数です。また、0! = 1 と定めます。この記号を使うと、P(n,r) = n!/(n−r)! と書けます。ここにある感嘆符の形の記号は、数学で階乗を表す記号です。r = 0 のときも、何も選ばない結果を一つと数えることで式が成り立ちます。

たとえば、異なる 5 人から代表と副代表を選ぶなら、代表が 5 通り、その人を除いた副代表が 4 通りなので、5 × 4 = 20 通りです。同じ人が両方の役を兼ねないという条件が、選択肢を一つ減らしています。代表と副代表を交換すれば別の結果になるため、順列として数えます。

この 5 人から、役割の区別がない係を 2 人選ぶ場合は組合せです。異なる n 個から順番を区別せず r 個を選ぶ数を C(n,r) と書きます。先ほどの 20 通りでは、同じ係の組が役の交換によって 2 回ずつ現れます。したがって、係の選び方は 20 ÷ 2 = 10 通りです。

一般に、選ばれた r 個の並べ方は r! 通りです。順列はどの組合せも r! 回ずつ数えているので、次の式が得られます。

C(n,r) = n!/{r!(n−r)!}

組合せの式を忘れても、まず順番つきで数え、同じ組を何回数えたかで割る、という順序に戻れます。ただし、ここで扱っているのは異なるものを重複なく選ぶ場合です。同じものを繰り返し選べる問題では、条件に合わせて数え方を組み立て直します。

組合せは、式の展開にも顔を出します。次の式を見てください。

(a+b)³ = a³ + 3a²b + 3ab² + b³

左辺は、同じ形のかっこを 3 個かけたものです。展開するときは、それぞれのかっこから a または b を選びます。a²b になる項を作るには、3 個のかっこのうち、どの 1 個から b を取るかを決めます。その選び方が C(3,1) = 3 通りなので、係数が 3 になるのです。同じ文字の積ができる経路の数を、係数が記録しています。

一般の非負整数 n についても、(a+b) を n 個かけた式で、b を取るかっこを r 個選ぶ方法は C(n,r) 通りです。したがって、a の n−r 乗と b の r 乗の積につく係数は C(n,r) になります。これが二項定理の中心です。展開の規則と選び方の問題が、同じ仕組みで説明されます。

パスカルの三角形は、こうした係数を行ごとに並べたものです。最初を 1 とし、その下を 1, 1、さらに 1, 2, 1、その次を 1, 3, 3, 1 と並べます。両端は 1 で、内側の数は直上の左右の数の和です。この規則にも、場合分けの理由があります。

n 人のうち特定の一人に注目し、r 人の係を選ぶとします。その人を含めるなら、残る n−1 人から r−1 人を選びます。含めないなら、残る n−1 人から r 人を選びます。この二つは重ならず、すべての選び方を覆うので、1 ≦ r ≦ n−1 のとき、次の関係が成り立ちます。

C(n,r) = C(n−1,r−1) + C(n−1,r)

三角形の足し方は、暗記用の模様ではなく、選び方を二つに分けた記録です。

大学の組合せ論は、重なりや構造まで数える

組合せ論は、主に離散的な対象の選び方や配置、その構造を調べる数学です。離散的とは、この場面では、人の組や札の並びのように、一つずつ区別して扱えるという意味です。大学では、条件が絡み合って樹形図が複雑になる問題でも、全体の関係を使って数えたり、詳しく数えずに存在を示したりします。

最初の道具は包除原理です。集合とは、何がそこに含まれるかが明確な対象の集まりです。有限集合 A の要素数を |A| と書きます。A∪B は A または B の少なくとも一方に属する要素の集合、A∩B は両方に属する要素の集合です。包除原理の最も基本的な形は、次の式です。

|A∪B| = |A| + |B| − |A∩B|

A と B を別々に数えて足すと、両方に属する要素だけは 2 回数えられます。その重複分を 1 回引けば、各要素をちょうど一度数えられます。中学の表で余分なますを除いた発想が、集合どうしの重なりを扱う規則になっています。

たとえば、1 から 30 までの整数のうち、2 または 3 で割り切れるものを数えます。2 の倍数は 15 個、3 の倍数は 10 個です。両方の条件を満たすものは 6 の倍数で、5 個あります。よって、求める個数は 15 + 10 − 5 = 20 個です。「または」は、両方の条件を満たす場合も含むことに注意します。

条件が三つなら、それぞれの個数を足し、二つずつの共通部分を引き、最後に三つすべての共通部分を足します。三つに共通する要素は、最初に 3 回足され、次に 3 回引かれるため、そのままでは数が消えてしまいます。最後に一度足す理由はそこにあります。条件の数が増えた場合にも、共通部分を足したり引いたりする規則へ一般化できます。

次の道具は鳩の巣原理です。正の整数 m に対し、m 個の箱に m 個より多いものを入れるなら、少なくとも一つの箱には 2 個以上入ります。どの箱にも高々 1 個しか入らないと仮定すると、全部合わせても m 個までしか入らず、条件と矛盾するからです。箱も鳩も実物である必要はなく、箱は分類先、鳩は分類される対象を表します。

たとえば、整数を 3 で割った余りは 0, 1, 2 のいずれかです。異なる整数を 4 個選ぶと、少なくとも 2 個は余りが同じになります。その二つは 3 の倍数に同じ余りを足した形なので、差は 3 の倍数です。実際にどの二つかを探す前に、そのような組が必ず存在すると結論できます。何通りかを求めることから、条件を満たすものが必ずあると示すことへ、問いが広がっています。

さらに、数を式の係数に保存する方法が母関数です。数列 a₀, a₁, a₂, … に対し、a₀ + a₁x + a₂x² + … という形式的べき級数を、その数列の通常母関数と呼びます。形式的べき級数とは、x の各非負整数乗に係数を割り当て、同じ次数の係数どうしを足すなど、係数の規則で扱う式です。ここでの x は数を代入して値を求めるためというより、対象の大きさを記録する印です。

重さが 1 の品物と、重さが 2 の品物があり、それぞれ一つまで選べるとします。前者の選び方を 1+x、後者を 1+x² で表すと、全体は次の式になります。

(1+x)(1+x²) = 1+x+x²+x³

各かっこの 1 は選ばない場合です。x や x² は選んだ場合の重さを表します。積を作ると、選んだ品物の重さが指数のたし算で合計されます。x³ の係数が 1 なのは、合計の重さを 3 にする選び方が一つあるという意味です。

母関数では、式をかける操作が選択の組合せに対応します。二項定理で展開の係数を数えた見方を、重さなど別の情報の記録へ広げたものです。情報分野では、容量の上限に収まるデータの選び方を考える際に、このような重さごとの分類が役立ちます。対象を全部並べる代わりに、同じ合計を持つ選び方をまとめて管理する発想は、計算手順を設計する入口にもなります。

一本の線は「一つの結果を一度だけ」にある

中学では、樹形図の先端や表のますに結果を置きました。高校では、順番つきの結果をまとめ、同じ組が何回現れたかを考えて組合せを求めました。大学の包除原理では、重複する部分そのものを数え、足し引きで修正しました。表し方が変わっても、一つの結果を最終的に一度だけ数えるという目標は共通しています。

ただし、重複の取り除き方には違いがあります。順列から組合せに移るときは、どの組も同じ回数現れるので割れます。包除原理で扱う和集合では、一方だけに属する要素と両方に属する要素で数えられる回数が異なります。そこで全体を一律に割るのでなく、重なった部分を引きます。割るか引くかは、覚えた問題の形より、重複の仕方から判断できます。

また、高校の二項定理と大学の母関数をつなぐのは、係数を「その結果を作る方法の数」と読む姿勢です。文字式は計算の対象であると同時に、数えた結果をしまう場所にもなります。樹形図の一つの経路が、展開の一つの項に姿を変えていると考えると、学ぶ内容のつながりが見えます。

鳩の巣原理は、さらに別の方向を開きます。正確な個数を最後まで求めなくても、分類先より対象が多いという関係だけで、重複の存在を保証できます。数学が求める答えは数値だけではありません。なぜ必ずそうなるのかを説明する力も、数え上げから育っていきます。

つながりを使った学び方

取り組むときの第一歩は、「何を一つの結果とするか」を短い文にすることです。「役割まで決まった人の組」なのか、「選ばれた人だけが決まった組」なのかを書きます。問題文にある「選ぶ」という動詞だけでは判断できません。二人を入れ替えた結果が同じか違うかを、名前の代わりの文字で確かめましょう。

第二歩は、条件を減らした小さな問題を実際に書き出すことです。その際、元の問題から何を変えたかも横に残します。対象の個数を小さくしただけなら考え方を試せますが、重複を許すかどうかまで変えてしまうと、別の問題になります。書き出しは正解を見るためだけでなく、自分が使おうとしている規則の条件を点検するために行います。

第三歩は、式の各部分に説明を添えることです。かけ算には「各段階で何を選ぶか」、わり算には「一つの結果を何回数えたか」、引き算には「何が余分に含まれたか」を書きます。説明が途中で止まる箇所が、次に確かめる場所です。計算を続ける前に、そこだけ樹形図や表へ戻します。

第四歩は、別の表現で答えを照合することです。樹形図と表、順列からの計算と組の一覧、展開式と選び方などを対応させます。答えが一致するだけで終えず、同じ一つの結果が両方の方法でどこに現れるかを指せると、考え方の接続を確認できます。

塾で担うのは、誤答に対して公式名を伝えるだけでなく、どこで結果の区別が変わったかを一緒にたどることです。式が正しくても理由を言いにくい場合には、問題の条件を一つ変えて考えてもらいます。順番を区別する条件を外したとき、図や式のどこが変わるかを見ると、理解している部分と支えが必要な部分を見つけられます。

家庭では、お子さまの説明を受け取る役割を持てます。「この一つはどこで数えたの」「入れ替えても同じなの」と、ノートの具体的な箇所について尋ねてみてください。その場で公式まで説明し直す必要はありません。言い切れなかった問いを残しておけば、次の授業で確かめる材料になります。

よくある質問

樹形図が書ければ、公式は覚えなくてもよいですか

樹形図は、公式の意味を確かめる土台です。ただ、対象が増えると図も大きくなるため、高校では式にまとめて扱う力が必要になります。まず小さな問題で枝の数と式を対応させ、その後は式から樹形図の形を思い浮かべられるようにしましょう。公式を使う速さと、条件に合うかを判断する力を結びつけます。

順列と組合せを見分ける言葉はありますか

特定の言葉だけで決めるより、入れ替えの意味を調べます。「人を選ぶ」問題でも、代表と副代表を決めるなら役割を区別します。「並べる」問題でも、見た目が同じものを含む場合には別の注意が必要です。何を同じ結果と見なすかを先に定めると、計算の方針が立ちます。

母関数には、無限の式の計算が必要ですか

入口では、有限の多項式だけでも仕組みを学べます。品物の例のように、選択を一つのかっこで表し、その積の係数を読んでみましょう。形式的べき級数でも、ある次数の積の係数は有限個の係数から計算できます。実数を代入して無限の和の値を考える場合には、さらに収束の条件が必要になります。

場合の数で足が止まったら、答えの数より先に「今、何を一つと呼んだか」を確かめてみてください。その問いは、樹形図にも、組合せの公式にも、母関数にも届きます。書いた一組を指さし、数えた場所と重複の扱いを説明できたとき、紙の上の計算は自分の判断につながります。武蔵境の武蔵野個別指導塾にとって、ノートの小さな重複には、学びを先へつなぐ対話の出発点があります。