足すのか掛けるのか？樹形図で決める和の法則と積の法則

場合の数の問題は、最後は足すか掛けるかのどちらかに落ちます。この 2 つを分ける規則が和の法則と積の法則で、数え上げ全体の土台になる。

公式を覚える前に、まず全部書き出す道具が要ります。それが樹形図。

樹形図で全部書き出す

樹形図は、選ぶ順に枝を分けていき、いちばん右の枝の本数を数える図である。数が小さいうちは、公式を当てるより書き出すほうが速い。

書き出しているうちに、掛け算で済む形が見えてきます。どの枝からも同じ本数の枝が出ていれば、そこは掛け算にできる。

例：コインを 3 回投げる

1 回目は表と裏の 2 通り。そのそれぞれから 2 回目が 2 通りずつ出て、3 回目も同じように 2 通りずつ出ます。

枝の先は 8 本になりました。$2\times 2\times 2=8$ という計算と合っています。

樹形図を描くと、なぜ掛け算になるかが目で見えます。同じ本数の枝が、前の段の枝の数だけ繰り返されるため。

例：3 人を一列に並べる

A、B、C の 3 人を並べます。先頭に立つ人が 3 通り、残った 2 人のうちどちらが 2 番目かで 2 通り、最後の 1 人は自動的に決まる。

$3\times 2\times 1=6$ 通りです。樹形図では 3 本、2 本、1 本と枝が細っていく形になる。

書き出すと ABC、ACB、BAC、BCA、CAB、CBA の 6 つ。数え落としがないかは、辞書の並び順で書けば確かめられます。

和の法則

2 つのことがらが同時には起こらないとき、総数は足し算になります。

ことがら A の起こり方が $m$ 通り、ことがら B の起こり方が $n$ 通りで、A と B が同時には起こらないとする。このとき A または B の起こり方は $m+n$ 通りである。

英語では rule of sum、または addition principle と呼びます^[2]。集合の言葉に直すと、共通部分を持たない 2 つの集合について次が成り立つ、という主張になる。

$$|A\cup B|=|A|+|B|$$

大事なのは「同時には起こらない」という条件のほう。この条件が抜けると、重なったぶんを二重に数えます。

例：サイコロ 2 個の目の和が 5 か 9

大小 2 個のサイコロを振ります。目の和が 5 になるのは $(1,4)$、$(2,3)$、$(3,2)$、$(4,1)$ の 4 通り。

和が 9 になるのは $(3,6)$、$(4,5)$、$(5,4)$、$(6,3)$ の 4 通りです。

和が 5 と和が 9 は同時には起こりません。だから足して $4+4=8$ 通り。

例：重なりがあると足せない

1 から 30 までの整数で、3 の倍数または 5 の倍数はいくつあるか考えます。

3 の倍数は 10 個、5 の倍数は 6 個。ここで $10+6=16$ としたくなりますが、これは誤りです。

15 と 30 は両方に入っているので、2 回数えています。正しくは重なりの 2 個を引いて 14 個。

同時に起こることがあるなら、和の法則はそのまま使えません。引き算で直す方法が必要になる。

積の法則

続けて起こることがらは、掛け算でつながります。

ことがら A の起こり方が $m$ 通りあり、そのどの場合についてもことがら B の起こり方が $n$ 通りあるとする。このとき A と B が続けて起こる場合の数は $m\times n$ 通りである。

英語では rule of product、multiplication principle と呼ばれます^[1]。集合の言葉では直積の要素の個数にあたる。

$$|A\times B|=|A|\times |B|$$

条件は「A のどの場合をとっても B が $n$ 通り」という部分です。この本数がそろっていないと掛け算にならない。

図の左は、青の 3 通りと赤の 2 通りが交わらない場合。右は、青を選んでから赤を選ぶ場合です。

同じ 3 と 2 でも、答えが 5 と 6 に分かれる。どちらの図にあたるかを見分ける。ここが最初の仕事です。

例：定食の選び方

主菜が 4 種類、副菜が 3 種類、汁物が 2 種類あります。1 つずつ選ぶ組み合わせを数える。

主菜をどれにしても副菜は 3 通り、副菜をどれにしても汁物は 2 通りです。段ごとの本数がそろっている。

$$4\times 3\times 2=24$$

24 通りになります。3 段の樹形図を描けば、いちばん右の枝が 24 本。

例：4 桁の暗証番号

0 から 9 までの数字を使い、同じ数字を何度使ってもよいとします。

各桁が 10 通りで、前の桁が何であっても次の桁は 10 通りのまま。だから $10^4=10000$ 通り。

同じ数字を使えない場合は本数が変わります。$10\times 9\times 8\times 7=5040$ 通り。

後者でも積の法則は使えます。1 桁目に何を置いても、2 桁目の候補はつねに 9 個だからです。

積の法則が使えるかどうかの見分け

「前の選択によって次の通り数が変わる」ように見えても、数さえそろっていれば掛けられます。

逆に、数そのものが変わる場合は掛けられません。そのときは場合分けして和の法則に持ち込む。

例：本数が崩れる場合

1、2、3、4 の 4 枚のカードから 2 枚を選んで 2 桁の偶数を作ります。

十の位を先に決めると、一の位に置ける偶数の枚数が変わってしまう。十の位が 2 なら残る偶数は 4 だけ、十の位が 1 なら 2 と 4 の 2 枚。

そこで一の位から決めます。一の位は 2 か 4 の 2 通り、十の位は残り 3 枚から 1 枚で 3 通り。

$2\times 3=6$ 通りです。制限のきつい場所から決めると、本数がそろいます。

例：約数の個数

72 の正の約数がいくつあるか数えます。まず素因数分解する。

$$72=2^3\times 3^2$$

72 の約数は $2^a\times 3^b$ の形に限られます。$a$ は 0 から 3 までの 4 通り、$b$ は 0 から 2 までの 3 通り。

$a$ をどう選んでも $b$ は 3 通りのままなので、積の法則が使えます。$4\times 3=12$ 個。

図のように長方形に並ぶので、個数は縦と横の掛け算になります。

一般に $N=p^a{q}^b{r}^c$ と素因数分解できるなら、正の約数の個数は次の式で出ます。

$$(a+1)(b+1)(c+1)$$

指数に 1 を足すのは、指数 0 も選べるためです。

例：約数の総和

同じ表を使うと、約数の合計も出せます。すべてのマスを足すことになる。

行ごとに足してから縦に足す代わりに、和の積の形に括ってしまいます。

$$(1+2+4+8)(1+3+9)=15\times 13=195$$

展開すると 12 個のマスがちょうど 1 回ずつ現れる。だから括った形と表の合計が一致します。

和と積を組み合わせる

実際の問題では、両方を続けて使う場面が多くなります。場合分けの中で掛け算をして、最後に足す形。

外で足し、中で掛ける。この二段構えを意識すると、複雑な問題でも道筋が立ちます。

例：3 桁の偶数を作る

1、2、3、4、5 の 5 枚のカードから 3 枚を選んで 3 桁の整数を作ります。偶数はいくつできるか。

一の位が 2 の場合と 4 の場合に分けます。この 2 つは同時には起こりません。

一の位が 2 なら、百の位は残り 4 枚、十の位はさらに残り 3 枚で $4\times 3=12$ 通り。一の位が 4 でも同じく 12 通り。

足して 24 通りです。外側が和の法則、内側が積の法則になっている。

例：硬貨の支払い方

10 円玉が 3 枚、50 円玉が 2 枚、100 円玉が 4 枚あります。この中から何枚か使って払える金額は何通りか。

まず、それぞれの硬貨を何枚使うかを決める通り数を数えます。10 円玉は 0 枚から 3 枚で 4 通り、50 円玉は 3 通り、100 円玉は 5 通り。

$4\times 3\times 5=60$ 通りの選び方があります。ただし全部 0 枚の場合は 0 円なので、支払いとしては除いて 59 通り。

ここで止めると誤りになります。50 円玉 2 枚と 100 円玉 1 枚は、どちらも 100 円で金額が同じ。

金額の種類を聞かれているなら、重なりをとり除く必要があります。何枚使うかを聞かれているなら 59 通りのままです。

問題文が「支払い方」を聞いているのか「金額」を聞いているのかで、答えが変わる。ここは読み違えやすいところ。

例：長方形の個数

縦 4 本、横 5 本の直線が格子状に並んでいます。この中にできる長方形の個数を数える。

長方形は、縦線 2 本と横線 2 本を選べば 1 つ決まります。逆に長方形が決まれば 4 本の線も決まる。

縦線の選び方は 4 本から 2 本で 6 通り、横線は 5 本から 2 本で 10 通りです。

$6\times 10=60$ 個になります。図形の問題でも、決め手になる要素に分ければ積の法則が効く。

例：じゃんけんの手

3 人がじゃんけんを 1 回します。手の出し方は全部で何通りか。

1 人につきグー、チョキ、パーの 3 通りで、他人の手に左右されません。$3^3=27$ 通り。

このうちあいこになるのは、全員同じ手の 3 通りと、3 種類がそろう $3!=6$ 通りを合わせて 9 通り。

勝負がつくのは $27-9=18$ 通りです。全体から引くほうが、勝ちの形を数えるより速い。

数え落としと重複を防ぐ

数え上げでいちばん多い失敗は、数え落としと二重数えです。どちらも順序を決めれば減ります。

最後の確認がいちばん効きます。$n=2$ や $n=3$ で手を動かせば、式の誤りはたいてい見つかる。

例：小さい場合で確かめる

「$n$ 人が一列に並ぶ並び方は $n!$ 通り」という式を確かめます。

$n=1$ なら 1 通りで、$1!=1$ と合う。$n=2$ なら AB と BA の 2 通りで、$2!=2$ と合います。

$n=3$ は先ほど書き出した 6 通りで、$3!=6$ と一致する。3 つ合えば、まず安心してよい。

例：0 を含む数字の並べ方

0、1、2、3 の 4 枚のカードから 3 枚を選んで 3 桁の整数を作ります。

百の位に 0 は置けません。この制限のある位から決めます。百の位は 1、2、3 の 3 通り。

十の位は 0 を含む残り 3 枚から 1 枚で 3 通り、一の位は残り 2 枚で 2 通り。

$3\times 3\times 2=18$ 通りになります。制限のきついところを先に決める。これが定石です。

例：塗り分け

3 つの区画を、赤、青、黄、緑の 4 色で塗り分けます。隣り合う区画は違う色にする。区画は横一列に並んでいるとします。

左の区画は 4 色から自由に選べて 4 通り。真ん中は左と違えばよいので 3 通り。

右は真ん中と違えばよいので、これも 3 通りです。左の色と同じでもよい。

$4\times 3\times 3=36$ 通り。隣としか比べないので、段ごとの本数がそろっている。

例：試合数を数える

8 チームの総当たり戦で、試合は全部で何試合か。

1 チームは他の 7 チームと戦うので $8\times 7=56$ ですが、これは 1 試合を 2 回数えています。

A 対 B と B 対 A は同じ試合。だから 2 で割って 28 試合になります。

順序が意味を持たないときは、掛けたあとに割る。この割り算が、組み合わせの考え方につながっていく。

例：握手の回数

同じ形の問題として、10 人が全員と 1 回ずつ握手する回数を数えます。

1 人あたり 9 回、10 人で $10\times 9=90$ ですが、1 回の握手を 2 人が数えている。

$90÷2=45$ 回です。総当たり戦とまったく同じ構造になっている。

よくある誤り

どれも、いきなり式を立てたときに起きます。何を数えているのかを日本語で言い切ってから式にすると防げる。

参考文献

^[1] と ^[2] は 2 つの法則の英語圏での標準的な述べ方、^[3] から ^[5] は各国語の教科書的なまとめです。