目次 ／ 場合の数と確率 ／ 数学A

第2章　場合の数（和の法則・積の法則）

—— 「または」は足し、「それぞれに」はかける ——

第1章では集合の要素の個数を数えました。この章では、ものごとの「起こり方」が何通りあるかを数えます。まず、樹形図と辞書式配列を使って、もれなく重なりなく書き出す方法を身につけます。次に、数え方の2本の柱である和の法則と積の法則を学び、約数の個数と総和、「少なくとも1つ」の数え方に応用します。ここで身につける2つの法則は、第3章の順列・第4章の組合せの公式の土台になります。

問題マップ記録を読み込み中…
基1基2基3基4基51234567891011121314151617181920
未回答 25× 0○ 01か月定着 0

樹形図でもれなく数える

第1章では、集合の要素が何個あるかを数えました。この章では、ものごとの「起こり方」が何通りあるかを数えます。ある事柄の起こり方の総数を、その事柄の場合の数といいます。たとえば硬貨を1回投げると表か裏かの2通りなので、場合の数は 22 です。

起こり方が少ないうちは頭の中で数えられますが、少し増えるとすぐに数え落としや二重に数えるミスが起こります。そこで、書き出し方にルールを決めます。

公式1：樹形図と辞書式配列
  1. 起こり方を「1つめ → 2つめ → …」の順に決め、枝分かれの図にかいて書き出す。この図を樹形図という。
  2. 文字や数の並びを書き出すときは、辞書の見出しと同じ順（1文字目が小さい順、1文字目が同じなら2文字目が小さい順、…）に並べる。この並べ方を辞書式配列という。
  3. どちらも、もれなく、重なりなく書き出すための方法である。
1回目 2回目 3回目 表 裏 表 裏 表 裏 表 裏 表 裏 表 裏 表 裏 表表表 表表裏 ← 表2回 表裏表 ← 表2回 表裏裏 裏表表 ← 表2回 裏表裏 裏裏表 裏裏裏 葉（右端）の数　2 × 2 × 2 = 8 通り

硬貨を3回投げる場合で、樹形図をかいてみます。1回目で「表」「裏」の2本に分かれ、2回目でそれぞれがまた2本に、3回目でさらに2本ずつに分かれます。右端の「葉」（枝の先）が1つの出方に対応していて、全部で 88 通りです。樹形図の良いところは、枝分かれの順番が決まっているので、同じ出方を2回書くことも、書き忘れることも起こりにくい点です。

国語辞典の並び方を思い出してください。「あい」「あお」「いか」…と、まず1文字目で分け、1文字目が同じ言葉は2文字目で並べます。どの言葉も入る場所がただ1つに決まるので、何万語あっても重なりも抜けもなく並べられます。場合の数を書き出すときも、同じように「小さい順」の決まりを1つ決めておくと、樹形図を横に読んだ形でもれなく書き出せます。

起こり方は、決める順番を決めて樹形図や辞書式配列で書き出すと、もれなく重なりなく数えられるということです。

例題1：樹形図で数える

(1) 硬貨を3回投げるとき、表が2回以上出る出方は何通りあるか求めなさい。

(2) 50 円玉、10 円玉、5 円玉を使って 100 円を支払う方法は何通りあるか求めなさい。ただし、どの硬貨も十分な枚数があり、使わない硬貨があってもよいものとする。

【解答】

(1) 樹形図（上の図）で、表が2回の出方は「表表裏」「表裏表」「裏表表」の 33 通り、3回の出方は「表表表」の 11 通りです。合わせて 4 通り‾\underline{4 \text{ 通り}} です。

(2) 金額の大きい硬貨から枚数を決めていきます。50 円玉の枚数で枝分かれさせ、その中で 10 円玉の枚数を決めると、5 円玉の枚数は残りの金額から1つに決まります。

50 円玉10 円玉5 円玉通り
22 枚00 枚00 枚11
11 枚00〜55 枚1010〜00 枚66
00 枚00〜1010 枚2020〜00 枚1111

50 円玉が 11 枚のとき、残り 5050 円を 10 円玉 00〜55 枚で払い、足りない分を 5 円玉で払うので 66 通りです。50 円玉が 00 枚のときも同じように 1111 通りです。合わせて 11+6{}+ 6+11{}+ 11=18 通り‾{}= \underline{18 \text{ 通り}} です。

和の法則

例題1(2)の最後で、11+6{}+ 6+11{}+ 11 と足しました。50 円玉が 22 枚の場合と 11 枚の場合は同時には起こらないので、それぞれの場合の数を足せば全体になります。これを法則として述べます。

公式2：和の法則

2つの事柄 AA，BB が同時には起こらないとき、AA の起こり方が mm 通り、BB の起こり方が nn 通りならば、AA または BB が起こる場合の数は

m\displaystyle m+n 通り\displaystyle {}+ n \text{ 通り}

である。3つ以上の事柄についても、どの2つも同時に起こらなければ同じように足せばよい。

これは、第1章の「共通な要素がなければ n(A∪B)n(A \cup B)=n(A){}= n(A)+n(B){}+ n(B)」を、起こり方の言葉で言いかえたものです。第1章の厳密定義ページで「重なりのない場合に分けて足す考え方が和の法則として出てくる」と予告したのは、このことでした。同時に起こることがあるなら、第1章の公式2のように重なりを引かなければなりません。

大小2個のさいころを投げるときの目の和を、表にまとめておきます。行が大きいさいころの目、列が小さいさいころの目です。

大＼小112233445566
11223344556677
22334455667788
33445566778899
4455667788991010
556677889910101111
66778899101011111212

同じ和は右上から左下への斜めの線に並びます。和が 77 の斜めがいちばん長く、66 通りです。「大が 11 で小が 22」と「大が 22 で小が 11」は別の出方として数えます。

駅の出口を思い浮かべてください。改札を出て地上に上がるのに、東口の階段が 33 本、西口の階段が 22 本あれば、上がり方は 33+2{}+ 2=5{}= 5 通りです。東口と西口の両方から同時に出ることはできないので、そのまま足せます。

同時には起こらない場合に分けたら、それぞれの場合の数を足せば全体の場合の数になるということです。

例題2：和の法則

大小2個のさいころを投げるとき、次の場合の数を求めなさい。

(1) 目の和が 44 の倍数になる場合

(2) 目の和が 55 以下になる場合

【解答】

(1) 目の和は 22 から 1212 までなので、44 の倍数になるのは和が 44，88，1212 のときです。

  • 和が 44：(大, 小) =(1,3),= (1, 3), (2,2),\ (2, 2), (3,1)\ (3, 1) の 33 通り
  • 和が 88：(2,6),(2, 6), (3,5),\ (3, 5), (4,4),\ (4, 4), (5,3),\ (5, 3), (6,2)\ (6, 2) の 55 通り
  • 和が 1212：(6,6)(6, 6) の 11 通り

これらは同時には起こらないので、和の法則より 33+5{}+ 5+1{}+ 1=9 通り‾{}= \underline{9 \text{ 通り}} です。

(2) 和が 22，33，44，55 の場合はそれぞれ 11，22，33，44 通りです。和の法則より 11+2{}+ 2+3{}+ 3+4{}+ 4=10 通り‾{}= \underline{10 \text{ 通り}} です。

積の法則

樹形図（fig01）では、1回目の2本の枝のそれぞれから、2回目の枝が2本ずつ出ていました。このように「それぞれに対して同じ数だけ枝が出る」ときは、足すのではなく、かけ算で数えられます。

公式3：積の法則

事柄 AA の起こり方が mm 通りあり、そのそれぞれに対して事柄 BB の起こり方が nn 通りずつあるとき、AA と BB がともに起こる場合の数は

m×n 通りm \times n \text{ 通り}

である。3つ以上の事柄が続けて起こる場合も同じように、それぞれの起こり方の数をかければよい。

硬貨を3回投げる出方は 2×2×22 \times 2 \times 2=8{}= 8 通りで、樹形図の葉の数と一致します。積の法則は、「nn 通りの枝分かれが mm 本の枝のそれぞれで起こるので、nn を mm 回足す」ことを1回のかけ算で済ませたものです。

大切なのは「それぞれに対して」の部分です。BB の中身は AA の結果によって変わってもかまいません。たとえば 55 人から委員長と副委員長を1人ずつ選ぶとき、委員長が決まると副委員長の候補は残りの 44 人になります。候補の顔ぶれは委員長によって変わりますが、人数はいつも 44 人なので、5×45 \times 4=20{}= 20 通りです。

服のコーディネートで考えます。上着が 33 着、ズボンが 44 本あれば、どの上着を選んでも、それに合わせるズボンが 44 通りずつあります。上着ごとに 44 通りが 33 回くり返されるので、組み合わせは 3×43 \times 4=12{}= 12 通りです。帽子が 22 種類加われば、12 通りのそれぞれに帽子が 22 通りずつで 12×212 \times 2=24{}= 24 通りに増えます。

1つめの決め方のそれぞれに対して2つめの決め方が同じ数ずつあれば、それらをかければ全体の場合の数になるということです。

例題3：積の法則

(1) 式 (a+b+c)(p+q)(x+y+z)(a + b + c)(p + q)(x + y + z) を展開したときの項の個数を求めなさい。

(2) 大中小3個のさいころを投げるとき、3個とも奇数の目が出る場合の数を求めなさい。

(3) 55 人の中から、委員長と副委員長を1人ずつ選ぶ方法は何通りあるか求めなさい。

【解答】

(1) 展開した項は、1つめのかっこから1文字、2つめから1文字、3つめから1文字を選んでかけたものです。選び方は 33 通り、22 通り、33 通りで、どの2つの選び方からも同じ項は出てこない（使う文字がすべて違う）ので、積の法則より 3×2×33 \times 2 \times 3=18 個‾{}= \underline{18 \text{ 個}} です。

(2) 奇数の目は 11，33，55 の 33 通りです。大・中・小のそれぞれで 33 通りずつなので、3×3×33 \times 3 \times 3=27 通り‾{}= \underline{27 \text{ 通り}} です。

(3) 委員長の選び方は 55 通りで、そのそれぞれに対して副委員長は残りの 44 人から選ぶので 44 通りです。5×45 \times 4=20 通り‾{}= \underline{20 \text{ 通り}} です。

約数の個数と総和

積の法則のよく知られた使い道が、約数の個数です。

公式4：約数の個数と総和

自然数 NN が NN=paqbrc{}= p^a q^b r^c（pp，qq，rr は異なる素数）と素因数分解されるとき、NN の正の約数の個数は (a+1)(b+1)(c+1)(a + 1)(b + 1)(c + 1)、NN の正の約数の総和は

(1+p+⋯+pa)\displaystyle (1 + p + \cdots + p^a)×(1+q+⋯+qb)\displaystyle \qquad \times (1 + q + \cdots + q^b)×(1+r+⋯+rc)\displaystyle \qquad \times (1 + r + \cdots + r^c)

素因数が2つや4つ以上のときも、同じようにかっこを並べてかける。

7272=23×32{}= 2^3 \times 3^2 で考えます。7272 の正の約数は、素因数に 22 を 00〜33 個、33 を 00〜22 個含む数、つまり 2i×3j2^i \times 3^j（00≦i{}\leqq i≦3{}\leqq 3，00≦j{}\leqq j≦2{}\leqq 2）の形の数です。ii の選び方が 44 通り、そのそれぞれに jj の選び方が 33 通りなので、積の法則より 4×34 \times 3=12{}= 12 個です。202^0=1{}= 1 のように「00 個」も1通りに数えるので、指数に 11 を足します。整数の性質 第1章で学んだ約数の個数の求め方は、ここで名前のついた積の法則そのものです。

総和は、次の積を展開すると分かります。

(1+2+4+8)(1+3+9)(1 + 2 + 4 + 8)(1 + 3 + 9)

展開した 4×34 \times 3=12{}= 12 個の項は、1つめのかっこから 2i2^i、2つめから 3j3^j を1つずつ選んでかけた 2i×3j2^i \times 3^j で、7272 の約数がちょうど1回ずつ出てきます。だから約数の総和は 15×1315 \times 13=195{}= 195 です。

財布の中の硬貨で考えてみましょう。100 円玉が 33 枚、10 円玉が 22 枚あるとき、何枚ずつ出すかは、100 円玉が 00〜33 枚の 44 通り、10 円玉が 00〜22 枚の 33 通りで、4×34 \times 3=12{}= 12 通りです。約数を選ぶことは、「22 という硬貨を何枚、33 という硬貨を何枚出すか」を決めることと同じなのです。ただし、硬貨の支払いでは「どれも出さない」は支払いにならないので 11 を引いて 1111 通りとしますが、約数では「どれも選ばない」が約数 11 にあたるので引きません。

約数は素因数を何個ずつ使うかの組で決まるので、約数の個数は「指数 +1+1」の積、約数の総和は各素因数の累乗の和の積になるということです。

例題4：約数の個数と総和

720720 の正の約数の個数と、その総和を求めなさい。

【解答】

720720=24×32×5{}= 2^4 \times 3^2 \times 5 と素因数分解できます。

個数は、22 の指数 00〜44 の 55 通り、33 の指数 00〜22 の 33 通り、55 の指数 00〜11 の 22 通りをかけて

(4+1)(2+1)(1+1)\displaystyle (4 + 1)(2 + 1)(1 + 1)=5×3×2\displaystyle {}= 5 \times 3 \times 2=30 個‾\displaystyle {}= \underline{30 \text{ 個}}

総和は

(1+2+4+8+16)\displaystyle (1 + 2 + 4 + 8 + 16)×(1+3+9)(1+5)\displaystyle \qquad \times (1 + 3 + 9)(1 + 5)=31×13×6\displaystyle {}= 31 \times 13 \times 6=2418‾\displaystyle {}= \underline{2418}

です。

「少なくとも1つ」は全体から引く

「少なくとも1つ〜」の場合の数は、11 つの場合、22 つの場合、…と分けて足すと場合分けが多くなります。反対の「1つも〜でない」を数えて全体から引くほうが、たいてい速く済みます。

公式5：「少なくとも1つ」の場合の数
(少なくとも1つ〜である場合の数)\displaystyle (\text{少なくとも1つ〜である場合の数})=(全体の場合の数)\displaystyle {}= (\text{全体の場合の数})−(1つも〜でない場合の数)\displaystyle {}- (\text{1つも〜でない場合の数})

「少なくとも1つ〜である」と「1つも〜でない」は同時には起こらず、合わせると全体になります。和の法則から (全体)(\text{全体})=(少なくとも1つ){}= (\text{少なくとも1つ})+(1つもない){}+ (\text{1つもない}) なので、移項すれば公式5になります。第1章の公式3「補集合の個数は全体から引く」と同じ考え方です。そして「1つも〜でない」は、たいてい積の法則ですぐに数えられます。

パスワードの規則を例にとります。英字 a\mathrm{a}，b\mathrm{b}，c\mathrm{c} と数字 11，22 の5種類の文字を使い、同じ文字をくり返し使ってよいとして3文字のパスワードを作ります。「数字を少なくとも1つ含む」ものを、数字が1文字・2文字・3文字の場合に分けて数えるのは大変です。全部で 5×5×55 \times 5 \times 5=125{}= 125 通り、数字を1つも含まない（英字だけの）ものは 3×3×33 \times 3 \times 3=27{}= 27 通りなので、125125−27{}- 27=98{}= 98 通りと一気に求まります。

「少なくとも1つ」は、場合分けして足すより、全体から「1つもない」場合を引くほうが速いということです。

例題5：「少なくとも1つ」の場合の数

(1) 大中小3個のさいころを投げるとき、目の積が偶数になる場合の数を求めなさい。

(2) 33 桁の整数のうち、数字 00 を少なくとも1つ含むものの個数を求めなさい。

【解答】

(1) 目の積が偶数になるのは、少なくとも1つの目が偶数のときです。全体は 6×6×66 \times 6 \times 6=216{}= 216 通りです。積が奇数になるのは3個とも奇数の目のときで、例題3(2)より 2727 通りです。

216\displaystyle 216−27\displaystyle {}- 27=189 通り‾\displaystyle {}= \underline{189 \text{ 通り}}

(2) 33 桁の整数は 100100 から 999999 までの 900900 個です。数字 00 を1つも含まないものは、百・十・一の位がどれも 11〜99 の 99 通りなので 9×9×99 \times 9 \times 9=729{}= 729 個です。

900\displaystyle 900−729\displaystyle {}- 729=171 個‾\displaystyle {}= \underline{171 \text{ 個}}

全体の 900900 も積の法則で 9×10×109 \times 10 \times 10 と求められます。百の位だけは 00 が使えないので、99 通りになることに注意しましょう。

基礎確認問題（全5問）

まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。

問1

大小2個のさいころを投げるとき、目の和が 55 になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

4 通り‾\underline{4 \text{ 通り}}（(大, 小) =(1,4),= (1, 4), (2,3),\ (2, 3), (3,2),\ (3, 2), (4,1)\ (4, 1)）

自己採点：
記録を読み込み中…

問2

大小2個のさいころを投げるとき、目の和が 1010 以上になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

6 通り‾\underline{6 \text{ 通り}}（和が 1010，1111，1212 の場合がそれぞれ 33，22，11 通り。和の法則で 33+2{}+ 2+1{}+ 1）

自己採点：
記録を読み込み中…

問3

44 種類のおにぎりと 33 種類のお茶から、それぞれ1つずつ選ぶ方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

12 通り‾\underline{12 \text{ 通り}}（積の法則で 4×34 \times 3）

自己採点：
記録を読み込み中…

問4

200200 の正の約数の個数を求めなさい。

つまずいたときは：
答えを見る
答え

12 個‾\underline{12 \text{ 個}}（200200=23×52{}= 2^3 \times 5^2 より (3+1)(2+1)(3 + 1)(2 + 1)）

自己採点：
記録を読み込み中…

問5

硬貨を3回投げるとき、少なくとも1回は表が出る出方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

7 通り‾\underline{7 \text{ 通り}}（全体 2×2×22 \times 2 \times 2=8{}= 8 通りから、3回とも裏の 11 通りを引く）

自己採点：
記録を読み込み中…

実践問題（全20問）

難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。

問1　★

100 円玉、50 円玉、10 円玉を使って 200 円を支払います。どの硬貨も十分な枚数があり、使わない硬貨があってもよいものとします。支払う方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

99 通り

解説

金額の大きい硬貨から枚数を決めます。100 円玉と 50 円玉の枚数が決まれば、10 円玉の枚数は残りの金額から1つに決まります。

  • 100 円玉 22 枚：残り 00 円なので 11 通り
  • 100 円玉 11 枚：残り 100100 円を 50 円玉 00〜22 枚と 10 円玉で払うので 33 通り
  • 100 円玉 00 枚：残り 200200 円を 50 円玉 00〜44 枚と 10 円玉で払うので 55 通り

これらは同時には起こらないので、和の法則より 11+3{}+ 3+5{}+ 5=9 通り‾{}= \underline{9 \text{ 通り}} です。

自己採点：
記録を読み込み中…

問2　★

大小2個のさいころを投げるとき、目の和が 33 の倍数になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

1212 通り

解説

目の和は 22 から 1212 なので、33 の倍数になるのは和が 33，66，99，1212 のときです。

  • 和が 33：(大, 小) =(1,2),= (1, 2), (2,1)\ (2, 1) の 22 通り
  • 和が 66：(1,5),(1, 5), (2,4),\ (2, 4), (3,3),\ (3, 3), (4,2),\ (4, 2), (5,1)\ (5, 1) の 55 通り
  • 和が 99：(3,6),(3, 6), (4,5),\ (4, 5), (5,4),\ (5, 4), (6,3)\ (6, 3) の 44 通り
  • 和が 1212：(6,6)(6, 6) の 11 通り

和の法則より 22+5{}+ 5+4{}+ 4+1{}+ 1=12 通り‾{}= \underline{12 \text{ 通り}} です。

自己採点：
記録を読み込み中…

問3　★

本棚に、数学の参考書が 77 冊、英語の参考書が 55 冊あります。どれも異なる本とします。

(1) 数学か英語の参考書を1冊だけ選ぶ方法は何通りあるか求めなさい。

(2) 数学の参考書と英語の参考書を1冊ずつ選ぶ方法は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 1212 通り　(2) 3535 通り

解説

(1) 数学の本を選ぶことと英語の本を選ぶことは同時には起こらない（1冊だけ選ぶ）ので、和の法則より 77+5{}+ 5=12 通り‾{}= \underline{12 \text{ 通り}} です。

(2) 数学の本の選び方 77 通りのそれぞれに対して、英語の本の選び方が 55 通りずつあるので、積の法則より 7×57 \times 5=35 通り‾{}= \underline{35 \text{ 通り}} です。

「どちらか一方」なら足し、「両方を続けて決める」ならかける、という使い分けを確かめる問題です。

自己採点：
記録を読み込み中…

問4　★

式 (a+b)(p+q+r)(x+y+z+w)(a + b)(p + q + r)(x + y + z + w) を展開したときの項の個数を求めなさい。

つまずいたときは：
答えを見る
答え

2424 個

解説

展開した項は、3つのかっこから1文字ずつ選んでかけたものです。選び方は 22 通り、33 通り、44 通りで、使う文字がすべて違うので、同じ項がまとめられることはありません。

積の法則より 2×3×42 \times 3 \times 4=24 個‾{}= \underline{24 \text{ 個}} です。

自己採点：
記録を読み込み中…

問5　★

360360 の正の約数の個数を求めなさい。

つまずいたときは：
答えを見る
答え

2424 個

解説

360360=23×32×5{}= 2^3 \times 3^2 \times 5 と素因数分解できます。約数は 2i×3j×5k2^i \times 3^j \times 5^k（00≦i{}\leqq i≦3{}\leqq 3，00≦j{}\leqq j≦2{}\leqq 2，00≦k{}\leqq k≦1{}\leqq 1）の形なので、積の法則より

(3+1)(2+1)(1+1)\displaystyle (3 + 1)(2 + 1)(1 + 1)=4×3×2\displaystyle {}= 4 \times 3 \times 2=24 個‾\displaystyle {}= \underline{24 \text{ 個}}
自己採点：
記録を読み込み中…

問6　★

大中小3個のさいころを投げるとき、目の積が奇数になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

2727 通り

解説

積が奇数になるのは、3個とも奇数の目が出るときです（1つでも偶数があると積は偶数）。奇数の目は 11，33，55 の 33 通りなので、積の法則より

3×3×3\displaystyle 3 \times 3 \times 3=27 通り‾\displaystyle {}= \underline{27 \text{ 通り}}
自己採点：
記録を読み込み中…

問7　★

大小2個のさいころを投げるとき、少なくとも一方の目が 55 以上になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

2020 通り

解説

全体は 6×66 \times 6=36{}= 36 通りです。どちらの目も 55 以上でない、つまり2個とも 11〜44 の目が出るのは 4×44 \times 4=16{}= 16 通りです。

36\displaystyle 36−16\displaystyle {}- 16=20 通り‾\displaystyle {}= \underline{20 \text{ 通り}}

確かめると、大が 55 以上（2×62 \times 6=12{}= 12 通り）と小が 55 以上（1212 通り）を足し、両方 55 以上（2×22 \times 2=4{}= 4 通り）を引いても 1212+12{}+ 12−4{}- 4=20{}= 20 通りです。

自己採点：
記録を読み込み中…

問8　★

108108 の正の約数の総和を求めなさい。

つまずいたときは：
答えを見る
答え

280280

解説

108108=22×33{}= 2^2 \times 3^3 と素因数分解できます。約数の総和は

(1+2+4)(1+3+9+27)\displaystyle (1 + 2 + 4)(1 + 3 + 9 + 27)=7×40\displaystyle {}= 7 \times 40=280‾\displaystyle {}= \underline{280}

右辺を展開すると、2i×3j2^i \times 3^j（00≦i{}\leqq i≦2{}\leqq 2，00≦j{}\leqq j≦3{}\leqq 3）の 3×43 \times 4=12{}= 12 個の項、つまり 108108 の約数がちょうど1回ずつ出てきます。

自己採点：
記録を読み込み中…

問9　★★

A 町と B 町を結ぶ道が 33 本、B 町と C 町を結ぶ道が 44 本あります。A 町から B 町を通って C 町へ行き、B 町を通って A 町へ戻ります。帰りは、行きに通った道を1本も通らないとき、往復の道順は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

7272 通り

解説

行きは、A→B が 33 通り、そのそれぞれに B→C が 44 通りで、3×43 \times 4=12{}= 12 通りです。

帰りは、行きに使った道を除くので、C→B は残りの 33 本、B→A は残りの 22 本から選びます。3×23 \times 2=6{}= 6 通りです。

行きの 1212 通りのそれぞれに対して帰りが 66 通りずつあるので、積の法則より

12×6\displaystyle 12 \times 6=72 通り‾\displaystyle {}= \underline{72 \text{ 通り}}

帰りの道の候補は行きの道順によって変わりますが、本数はいつも同じなので積の法則が使えます。

自己採点：
記録を読み込み中…

問10　★★

10 円玉が 33 枚、50 円玉が 22 枚、100 円玉が 22 枚あります。これらの一部または全部を使って、ちょうど支払うことのできる金額について考えます。

(1) 支払い方は何通りあるか求めなさい。ただし、硬貨の枚数の組が異なれば、金額が同じでも異なる支払い方とする。

(2) 支払うことのできる金額は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 3535 通り　(2) 2727 通り

解説

(1) 10 円玉は 00〜33 枚の 44 通り、50 円玉は 00〜22 枚の 33 通り、100 円玉は 00〜22 枚の 33 通りです。積の法則より 4×3×34 \times 3 \times 3=36{}= 36 通りですが、すべて 00 枚の場合は支払いにならないので除き、3636−1{}- 1=35 通り‾{}= \underline{35 \text{ 通り}} です。

(2) (1) のままでは、「50 円玉 22 枚」と「100 円玉 11 枚」のように同じ金額を2回数えてしまいます。そこで、100 円玉 11 枚を 50 円玉 22 枚に置きかえて考えます。すると 50 円玉が 22+2×2{}+ 2 \times 2=6{}= 6 枚分あることになり、50 円単位の金額は 00〜300300 円の 77 通りすべてが作れます。

10 円玉の分は 00〜3030 円の 44 通りで、5050 円未満なので 50 円単位の金額と重なることはありません。金額は 4×74 \times 7=28{}= 28 通りで、00 円を除いて 27 通り‾\underline{27 \text{ 通り}} です。

大きい硬貨が小さい硬貨の組で作れるときは、「支払い方」と「金額」の数が違ってくるので注意しましょう。

自己採点：
記録を読み込み中…

問11　★★

00，11，22，33，44 の5個の数字を使って 33 桁の整数を作ります。同じ数字をくり返し使ってよいものとします。

(1) 33 桁の整数は全部で何個できるか求めなさい。

(2) そのうち偶数は何個あるか求めなさい。

つまずいたときは：
答えを見る
答え

(1) 100100 個　(2) 6060 個

解説

(1) 百の位には 00 が使えないので 11〜44 の 44 通り、十の位と一の位はそれぞれ 55 通りです。積の法則より

4×5×5\displaystyle 4 \times 5 \times 5=100 個‾\displaystyle {}= \underline{100 \text{ 個}}

(2) 偶数になるのは一の位が 00，22，44 のときで 33 通りです。百の位 44 通り、十の位 55 通りと合わせて

4×5×3\displaystyle 4 \times 5 \times 3=60 個‾\displaystyle {}= \underline{60 \text{ 個}}

条件のついた位（百の位・一の位）から先に通り数を決めると、見落としが防げます。

自己採点：
記録を読み込み中…

問12　★★

33 桁の整数のうち、数字 77 を少なくとも1つ含むものの個数を求めなさい。

つまずいたときは：
答えを見る
答え

252252 個

解説

33 桁の整数は全部で 900900 個です。数字 77 を1つも含まないものを数えます。

  • 百の位：00 と 77 以外の 88 通り
  • 十の位・一の位：77 以外の 99 通りずつ

積の法則より 8×9×98 \times 9 \times 9=648{}= 648 個なので

900\displaystyle 900−648\displaystyle {}- 648=252 個‾\displaystyle {}= \underline{252 \text{ 個}}

百の位を 99 通りとしてしまうと、00 を除き忘れて答えがずれます。

自己採点：
記録を読み込み中…

問13　★★

正の約数の個数がちょうど 1010 個である自然数のうち、最小のものを求めなさい。

つまずいたときは：
答えを見る
答え

4848

解説

約数の個数は、素因数分解したときの「指数 +1+1」の積です。これが 1010 になる分け方は、1010=10{}= 10 と 1010=5×2{}= 5 \times 2 の2つだけです。

  • 1010=10{}= 10 のとき：NN=p9{}= p^9（pp は素数）。最小は 292^9=512{}= 512
  • 1010=5×2{}= 5 \times 2 のとき：NN=p4q{}= p^4 q（pp，qq は異なる素数）。小さくするには大きい指数に小さい素数を当てて 24×32^4 \times 3=48{}= 48

4848<512{}< 512 なので、最小のものは 48‾\underline{48} です。

確かめると 4848 の約数は 1,1, 2,\ 2, 3,\ 3, 4,\ 4, 6,\ 6, 8,\ 8, 12,\ 12, 16,\ 16, 24,\ 24, 48\ 48 の 1010 個です。34×23^4 \times 2=162{}= 162 のように指数と素数の組を逆にすると大きくなります。

自己採点：
記録を読み込み中…

問14　★★

方程式 xx+2y{}+ 2y+3z{}+ 3z=12{}= 12 を満たす自然数の組 (x, y, z)(x,\ y,\ z) の個数を求めなさい。

つまずいたときは：
答えを見る
答え

77 個

解説

係数のいちばん大きい zz から値を決めて場合分けします。xx，yy は 11 以上なので xx+2y{}+ 2y≧3{}\geqq 3 で、3z3z≦9{}\leqq 9 より zz=1,{}= 1, 2,\ 2, 3\ 3 です。

  • zz=1{}= 1 のとき xx+2y{}+ 2y=9{}= 9：yy=1,{}= 1, 2,\ 2, 3,\ 3, 4\ 4（xx=7,{}= 7, 5,\ 5, 3,\ 3, 1\ 1）の 44 個
  • zz=2{}= 2 のとき xx+2y{}+ 2y=6{}= 6：yy=1,{}= 1, 2\ 2（xx=4,{}= 4, 2\ 2）の 22 個
  • zz=3{}= 3 のとき xx+2y{}+ 2y=3{}= 3：yy=1{}= 1（xx=1{}= 1）の 11 個

和の法則より 44+2{}+ 2+1{}+ 1=7 個‾{}= \underline{7 \text{ 個}} です。

自己採点：
記録を読み込み中…

問15　★★

540540 と 720720 の正の公約数の個数と、その総和を求めなさい。

つまずいたときは：
答えを見る
答え

個数 1818 個、総和 546546

解説

540540=22×33×5{}= 2^2 \times 3^3 \times 5，720720=24×32×5{}= 2^4 \times 3^2 \times 5 です。公約数は最大公約数の約数なので、各素因数の指数の小さいほうをとって、最大公約数は

22×32×5\displaystyle 2^2 \times 3^2 \times 5=180\displaystyle {}= 180

180180 の正の約数の個数は (2+1)(2+1)(1+1)(2 + 1)(2 + 1)(1 + 1)=18 個‾{}= \underline{18 \text{ 個}}、総和は

(1+2+4)(1+3+9)(1+5)\displaystyle (1 + 2 + 4)(1 + 3 + 9)(1 + 5)=7×13×6\displaystyle {}= 7 \times 13 \times 6=546‾\displaystyle {}= \underline{546}

です。

自己採点：
記録を読み込み中…

問16　★★

横一列に並んだ 55 つの区画を、赤・青・黄の 33 色で塗り分けます。隣り合う区画は異なる色で塗り、同じ色を何回使ってもよく、使わない色があってもよいものとします。塗り方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

4848 通り

解説

左端から順に塗ります。

  • 左端：33 色のどれでもよいので 33 通り
  • 2番目：左隣と違う色なので 22 通り
  • 3番目〜5番目：それぞれ左隣と違う色なので 22 通りずつ

どの区画も、左隣の色が何であっても選べる色は 22 色ずつなので、積の法則より

3×2×2×2×2\displaystyle 3 \times 2 \times 2 \times 2 \times 2=48 通り‾\displaystyle {}= \underline{48 \text{ 通り}}
自己採点：
記録を読み込み中…

問17　★★★

正方形を縦と横の線で4等分し、左上・右上・右下・左下の 44 つの区画を作ります。これらを赤・青・黄・緑の 44 色で塗り分けます。辺で接している区画は異なる色で塗り、左上と右下のように頂点だけで接している区画は同じ色でもよいものとします。同じ色を何回使ってもよく、使わない色があってもよいとき、塗り方は何通りあるか求めなさい。

つまずいたときは：
答えを見る
答え

8484 通り

解説

辺で接しているのは「左上と右上」「右上と右下」「右下と左下」「左下と左上」の4組です。左上 → 右上 → 右下 → 左下の順に塗ると、最後の左下は右下と左上の両方と接しているので、選べる色の数が「右下が左上と同じ色かどうか」で変わります。そこで場合分けします。

右下が左上と同じ色のとき　左上 44 通り、右上は左上と違う 33 通り、右下は左上と同じ 11 通り、左下は左上（＝右下）と違う 33 通りです。

4×3×1×3\displaystyle 4 \times 3 \times 1 \times 3=36 通り\displaystyle {}= 36 \text{ 通り}

右下が左上と違う色のとき　左上 44 通り、右上 33 通り、右下は右上とも左上とも違う 22 通り、左下は右下とも左上とも違う（この2色は異なる）ので 22 通りです。

4×3×2×2\displaystyle 4 \times 3 \times 2 \times 2=48 通り\displaystyle {}= 48 \text{ 通り}

和の法則より 3636+48{}+ 48=84 通り‾{}= \underline{84 \text{ 通り}} です。

積の法則が使えるのは、「前の決め方によらず、次の選び方の数が同じ」ときだけです。数が変わるところで場合分けし、それぞれを積の法則で数えてから和の法則でまとめます。

自己採点：
記録を読み込み中…

問18　★★★

aa，bb を自然数とします。NN=2a×3b{}= 2^a \times 3^b の正の約数の総和が 403403 であるとき、NN を求めなさい。

つまずいたときは：
答えを見る
答え

NN=144{}= 144

解説

約数の総和は (1+2+⋯+2a)(1 + 2 + \cdots + 2^a) と (1+3+⋯+3b)(1 + 3 + \cdots + 3^b) の積で、これが 403403 です。それぞれのかっこがとりうる値を並べます。

  • 11+2{}+ 2+⋯{}+ \cdots+2a{}+ 2^a（aa≧1{}\geqq 1）：3,3, 7,\ 7, 15,\ 15, 31,\ 31, 63,\ 63, 127,\ 127, 255,\ 255, …\ \ldots
  • 11+3{}+ 3+⋯{}+ \cdots+3b{}+ 3^b（bb≧1{}\geqq 1）：4,4, 13,\ 13, 40,\ 40, 121,\ 121, 364,\ 364, …\ \ldots

403403=13×31{}= 13 \times 31 です。2つめのかっこは 44 以上なので、1つめのかっこは 403÷4403 \div 4 以下、つまり 100100 以下で、候補は 33，77，1515，3131，6363 です。このうち 403403 を割り切るのは 3131 だけで、このとき2つめは 403÷31403 \div 31=13{}= 13 となり、上の列に入っています。

11+2{}+ 2+4{}+ 4+8{}+ 8+16{}+ 16=31{}= 31 より aa=4{}= 4、11+3{}+ 3+9{}+ 9=13{}= 13 より bb=2{}= 2 なので

N\displaystyle N=24×32\displaystyle {}= 2^4 \times 3^2=144‾\displaystyle {}= \underline{144}

確かめると 144144 の約数の総和は 31×1331 \times 13=403{}= 403 です。

自己採点：
記録を読み込み中…

問19　★★★

大中小3個のさいころを投げるとき、目の和が 88 になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

2121 通り

解説

大の目 aa で場合分けし、中と小の目の和 88−a{}- a になる組を数えます。

  • aa=1{}= 1：中＋小 =7= 7 → (1,6),(1, 6), (2,5),\ (2, 5), …,\ \ldots, (6,1)\ (6, 1) の 66 通り
  • aa=2{}= 2：中＋小 =6= 6 → 55 通り
  • aa=3{}= 3：中＋小 =5= 5 → 44 通り
  • aa=4{}= 4：中＋小 =4= 4 → 33 通り
  • aa=5{}= 5：中＋小 =3= 3 → 22 通り
  • aa=6{}= 6：中＋小 =2= 2 → 11 通り

中＋小の個数は、和の法則の表（大小2個の目の和）の斜めの長さです。和の法則より

6\displaystyle 6+5\displaystyle {}+ 5+4\displaystyle {}+ 4+3\displaystyle {}+ 3+2\displaystyle {}+ 2+1\displaystyle {}+ 1=21 通り‾\displaystyle {}= \underline{21 \text{ 通り}}

「目の組み合わせ」だけで {1,1,6}\{1, 1, 6\}，{1,2,5}\{1, 2, 5\}，… と数えると、並べかえの数（{1,2,5}\{1, 2, 5\} なら大中小の割り当てが 66 通り、{1,1,6}\{1, 1, 6\} なら 33 通り）の違いを見落としやすくなります。大中小を区別して数えるのが安全です。

自己採点：
記録を読み込み中…

問20　★★★

大中小3個のさいころを投げるとき、目の積が 44 の倍数になる場合の数を求めなさい。

つまずいたときは：
答えを見る
答え

135135 通り

解説

目を、含む素因数 22 の個数で3つに分けます。

  • 22 を含まない（奇数）：11，33，55 の 33 通り
  • 22 をちょうど1個含む：22，66 の 22 通り
  • 22 を2個含む：44 の 11 通り

積が 44 の倍数でないのは、3個の目に含まれる 22 の個数の合計が 00 個か 11 個のときです。

  • 合計 00 個（3個とも奇数）：3×3×33 \times 3 \times 3=27{}= 27 通り
  • 合計 11 個（1個だけが 22 か 66 で、残り2個は奇数）：どのさいころが 22 か 66 かで 33 通り、その目が 22 通り、残り2個が 3×33 \times 3 通りなので 3×2×93 \times 2 \times 9=54{}= 54 通り

44 の倍数でないのは 2727+54{}+ 54=81{}= 81 通りなので

216\displaystyle 216−81\displaystyle {}- 81=135 通り‾\displaystyle {}= \underline{135 \text{ 通り}}

「44 の倍数になる」側を直接数えると、44 の目がある場合・22 か 66 が2個以上ある場合などが重なり合って複雑になります。重なりのない「ならない」側を数えて全体から引くのが近道です。

自己採点：
記録を読み込み中…

数学小話コーナー

回る円盤で考えを組み合わせた修道士

13 世紀の地中海、マヨルカ島にラモン・リュイ（ラテン語名ルルス）という人物がいました。リュイは、ものごとの性質を表す言葉にアルファベットを割り当て、それを同心円状に重ねた紙の円盤に書き込みました。内側の円盤を回すと、外側の言葉と内側の言葉の組が次々に並びます。外側に 99 個、内側に 99 個の言葉があれば、組は 9×99 \times 9=81{}= 81 通り。円盤を3枚にすれば 9×9×99 \times 9 \times 9=729{}= 729 通りです。リュイは、こうしてあらゆる組み合わせを機械的に作り出せば、真理に一つ残らずたどりつけると考えました（円盤に書いた言葉の数や使い方は、著作によって違います ※諸説あり）。

それから約 400 年後、この発想に強くひかれたのが、のちに微分積分を作ることになるライプニッツです。ライプニッツは 20 歳のころ、1666 年に『結合法論』という論文を書き、リュイの方法を取り上げながら、ものを並べたり選んだりする方法の数を調べました。「すべての考えを基本の概念の組み合わせで表し、計算で正しいかどうかを決められないか」という彼の夢は、のちの記号論理学やコンピューターの考え方の源流の1つといわれています。

回る円盤は「1枚目のそれぞれに対して、2枚目の全部が並ぶ」という積の法則を、そのまま形にした道具でした。

豆知識

1726 年に出版された『ガリバー旅行記』には、単語を書いた木片を取っ手で回して並べかえ、偶然できた文章を書き留めて本を作る「文章製造機」が登場します。作者スウィフトは、リュイやライプニッツの組み合わせの発想を皮肉ったのではないかともいわれます（※諸説あり）。

ルービックキューブは 4325 京通り

ルービックキューブは、ハンガリーの建築家ルビク・エルネーが 1974 年に考案したパズルです。各面 3×33 \times 3 の小さなキューブでできていて、崩れた状態は全部で

43252003274489856000 通り43252003274489856000 \text{ 通り}

（約 43254325 京通り）あります。この途方もない数も、積の法則で組み立てられます。

キューブの角には、3色のついた角の部品が 88 個あります。8か所の置き場所に部品を1つずつ入れていくと、1か所目は 88 通り、2か所目は残りの 77 通り、…で、8×7×6×⋯×18 \times 7 \times 6 \times \cdots \times 1=40320{}= 40320 通り。さらに各部品の向きが 33 通りずつで 383^8 通りです。辺の部品（2色）は 1212 個で、置き方が 12×11×⋯×112 \times 11 \times \cdots \times 1 通り、向きが 2122^{12} 通り。これらをすべてかけると、キューブを一度ばらばらにして組み立て直す方法の数になります。

ところが、ふつうに回すだけでは、このうちちょうど 1212 分の 11 にしかたどりつけません。角の部品の向きの合計、辺の部品の向きの合計、部品の入れかわり方の3つに「回しても変わらない決まり」があり、それぞれ 33 分の 11、22 分の 11、22 分の 11 に絞られるからです。組み立て直しの総数を 1212 で割ったものが、冒頭の 4325 京です。ばらばらにして適当にはめ直したキューブは、1212 回に 1111 回は、どう回しても完成しないのです。

豆知識

どんなに崩れた状態からでも、2020 手あれば必ず完成できることが 2010 年にコンピューターを使って証明されました。この 2020 は「神の数字」と呼ばれています（1回の 180°180° 回転も1手と数える場合）。

モールス信号の「長さ」の設計

電信の時代に使われたモールス信号は、短い音「・」と長い音「−」の並びで文字を表します。たとえば E は「・」、T は「−」、A は「・−」です。では、英語のアルファベット 2626 文字を表すには、符号を何個まで並べれば足りるでしょうか。

符号を1個並べる並びは「・」「−」の 22 通り、2個なら積の法則で 2×22 \times 2=4{}= 4 通り、3個なら 88 通り、4個なら 1616 通りです。長さの違う並びは同時には起こらないので、4個までの並びは和の法則で

2\displaystyle 2+4\displaystyle {}+ 4+8\displaystyle {}+ 8+16\displaystyle {}+ 16=30 通り\displaystyle {}= 30 \text{ 通り}

2626 文字に足ります。3個までだと 22+4{}+ 4+8{}+ 8=14{}= 14 通りしかないので、4個までが必要です。実際、国際モールス信号のアルファベットは 11〜44 個の符号でできていて、数字には5個の符号が使われています。

もう1つの工夫は、どの文字にどの長さを割り当てるかです。英語でいちばんよく使われる E に最短の「・」を、T にも1個の「−」を割り当て、Q や Z のようにあまり使われない文字に4個の符号を回しました。よく送る文字ほど短くしておけば、電文全体を送る時間が短くなります。この「よく使うものほど短く」という考え方は、今のデータ圧縮の技術にも生きています。

豆知識

指で読む点字は、縦 33 行×横 22 列の 66 つの点のそれぞれを「出す・出さない」で表します。262^6=64{}= 64 通りから、点が1つもない場合を除いた 6363 通りが使えます。点字は 1825 年ごろにフランスのルイ・ブライユが考案し、日本語の点字は 1890 年に石川倉次の案が採用されました。

厳密定義（発展）

※ここは発展ページです。本文では和の法則と積の法則を「当たり前の数え方」として使いました。ここでは、場合の数を集合の要素の個数として定め、2つの法則を第1章の定義と定理から証明します。

場合の数と和の法則

定義1：場合の数

ある事柄の起こり方を1つずつ要素とする有限集合を SS とするとき、n(S)n(S) をその事柄の場合の数という。

たとえば「大小2個のさいころの出方」は、SS={(1,1), (1,2), …, (6,6)}{}= \{(1, 1),\ (1, 2),\ \ldots,\ (6, 6)\} という集合の要素の個数です。「数える」ことは、第1章の定義1の「番号を振る」ことにほかなりません。

定理1：和の法則

有限集合 A1,A_1, A2,\ A_2, …,\ \ldots, Ak\ A_k のどの2つも共通な要素をもたないとき

n(A1∪A2∪⋯∪Ak)\displaystyle n(A_1 \cup A_2 \cup \cdots \cup A_k)=n(A1)\displaystyle {}= n(A_1)+n(A2)\displaystyle {}+ n(A_2)+⋯\displaystyle {}+ \cdots+n(Ak)\displaystyle {}+ n(A_k)

証明　kk=2{}= 2 のときは第1章の定理1である。kk≧3{}\geqq 3 のときは、BB=A1∪⋯∪Ak−1{}= A_1 \cup \cdots \cup A_{k-1} とおくと、AkA_k はどの AiA_i（ii<k{}< k）とも共通な要素をもたないので B∩AkB \cap A_k=∅{}= \varnothing である。第1章の定理1より n(B∪Ak)n(B \cup A_k)=n(B){}= n(B)+n(Ak){}+ n(A_k) となり、n(B)n(B) に同じことをくり返せばよい。（証明終）

本文の公式2の「同時には起こらない」は、起こり方の集合が「共通な要素をもたない」ことの言いかえです。

直積と積の法則

積の法則を集合の言葉で述べるために、「組」を要素とする集合を用意します。

定義2：直積

集合 AA，BB に対して、aa∈A{}\in A と bb∈B{}\in B の組 (a, b)(a,\ b) 全体の集合を AA と BB の直積といい、A×BA \times B で表す。

A×B\displaystyle A \times B={(a, b)∣a∈A, b∈B}\displaystyle {}= \{(a,\ b) \mid a \in A,\ b \in B\}

2つの組 (a, b)(a,\ b) と (a′, b′)(a',\ b') は、aa=a′{}= a' かつ bb=b′{}= b' のときに限り等しいとする。

組は順番を区別します。AA=B{}= B={1, 2, …, 6}{}= \{1,\ 2,\ \ldots,\ 6\} のとき、(1, 2)(1,\ 2) と (2, 1)(2,\ 1) は異なる要素で、これが「大が 11 で小が 22」と「大が 22 で小が 11」を区別することにあたります。座標平面の点 (x, y)(x,\ y) も直積の要素です。

定理2：積の法則（直積の要素の個数）

有限集合 AA，BB について

n(A×B)\displaystyle n(A \times B)=n(A)×n(B)\displaystyle {}= n(A) \times n(B)

証明　n(A)n(A)=m{}= m とし、AA={a1, a2, …, am}{}= \{a_1,\ a_2,\ \ldots,\ a_m\} とする。A×BA \times B の要素を、1つめの成分で分けて

Ci\displaystyle C_i={(ai, b)∣b∈B}\displaystyle {}= \{(a_i,\ b) \mid b \in B\}(i=1, 2, …, m)\displaystyle (i = 1,\ 2,\ \ldots,\ m)

とおく。A×BA \times B のどの要素も、ちょうど1つの CiC_i に属するので、A×BA \times B=C1∪⋯∪Cm{}= C_1 \cup \cdots \cup C_m で、どの2つの CiC_i も共通な要素をもたない。

また、BB の要素 bb に CiC_i の要素 (ai, b)(a_i,\ b) を対応させると、これは BB と CiC_i の間の1対1の対応である。BB の番号の振り方をそのまま CiC_i に写せるので、n(Ci)n(C_i)=n(B){}= n(B) である。

定理1より

n(A×B)\displaystyle n(A \times B)=n(C1)\displaystyle {}= n(C_1)+⋯\displaystyle {}+ \cdots+n(Cm)\displaystyle {}+ n(C_m)=n(B)+⋯+n(B)⏟m 個\displaystyle {}= \underbrace{n(B) + \cdots + n(B)}_{m \text{ 個}}=m×n(B)\displaystyle {}= m \times n(B)

である。（証明終）

証明の中身は「かけ算とは同じ数を何回も足すこと」です。CiC_i は、樹形図で aia_i の枝から先に出ている枝の束にあたります。

選べるものが変わる場合

本文では、委員長を選ぶと副委員長の候補が変わる場合にも積の法則を使いました。このときの起こり方の集合は、ちょうどの直積ではありません。そこで定理2を少し広げます。

定理3：積の法則（一般形）

集合 SS の要素が組 (a, b)(a,\ b) の形をしていて、1つめの成分 aa として現れるものが mm 個あり、どの aa についても、(a, b)(a,\ b)∈S{}\in S となる bb がちょうど nn 個ずつあるとする。このとき

n(S)\displaystyle n(S)=m×n\displaystyle {}= m \times n

である。3つ以上の成分の組についても、「それまでの成分をどう決めても、次の成分の選び方がちょうど njn_j 個」ならば n(S)n(S)=n1×n2×⋯×nk{}= n_1 \times n_2 \times \cdots \times n_k である。

証明　1つめの成分として現れるものを a1,a_1, …,\ \ldots, am\ a_m とし、CiC_i={(ai, b)∈S}{}= \{(a_i,\ b) \in S\} とおく。定理2の証明と同じく、SS=C1∪⋯∪Cm{}= C_1 \cup \cdots \cup C_m で、どの2つも共通な要素をもたず、仮定より n(Ci)n(C_i)=n{}= n である。定理1より n(S)n(S)=m×n{}= m \times n となる。

3つ以上のときは、組 (a1, …, ak−1, ak)(a_1,\ \ldots,\ a_{k-1},\ a_k) を「(a1, …, ak−1)(a_1,\ \ldots,\ a_{k-1}) という1つの組」と「aka_k」の2つ組とみなして、2つの場合をくり返し使えばよい。（証明終）

定理2との違いは、CiC_i の中身（2つめの成分の候補）が ii ごとに違ってよいことです。個数さえそろっていれば、足し算の回数は同じなので、かけ算で済みます。逆に、個数が ii によって変わるときは、実践問題 j17 のように場合分けして定理1で足すことになります。

部分集合の個数

積の法則のきれいな使い道を1つ証明しておきます。

定理4：部分集合の個数

nn 個の要素をもつ集合 UU={u1, u2, …, un}{}= \{u_1,\ u_2,\ \ldots,\ u_n\} の部分集合（∅\varnothing と UU 自身も含む）は 2n2^n 個ある。

証明　UU の部分集合 XX に対して、各 uju_j が XX に「入る」なら 11、「入らない」なら 00 を書いて、00 と 11 を nn 個並べた組 (e1, e2, …, en)(e_1,\ e_2,\ \ldots,\ e_n) を対応させる。

逆に、00 と 11 の組が1つ与えられると、eje_j=1{}= 1 となる uju_j だけを集めた部分集合がただ1つ決まる。よって、部分集合全体と、00 と 11 を nn 個並べた組全体の間には1対1の対応がある。

後者は {0, 1}\{0,\ 1\} を nn 個並べた直積なので、定理2をくり返し使って 2×2×⋯×22 \times 2 \times \cdots \times 2=2n{}= 2^n 個である。（証明終）

数と式 第5章で出てきた「部分集合は 2n2^n 個」と、第1章の小話の「4つの集合のベン図には 242^4=16{}= 16 個の部分が必要」は、どちらもこの定理です。後者では、ベン図の各部分に「AA に入るか」「BB に入るか」…の 00・11 の組が対応しています。

本文の公式4（約数の個数）も同じ形をしています。NN=p1a1⋯pkak{}= p_1^{a_1} \cdots p_k^{a_k} の約数と、指数の組 (e1, …, ek)(e_1,\ \ldots,\ e_k)（00≦ej{}\leqq e_j≦aj{}\leqq a_j）の間の1対1の対応は、素因数分解の一意性（整数の性質 第1章 定理3・定理4）から得られます。組の集合は {0, …, a1}×⋯×{0, …, ak}\{0,\ \ldots,\ a_1\} \times \cdots \times \{0,\ \ldots,\ a_k\} という直積なので、定理2より個数は (a1+1)⋯(ak+1)(a_1 + 1) \cdots (a_k + 1) です。

第3章の順列と第4章の組合せの公式は、すべて定理1〜3（と、それを使った「対応させて数える」考え方）から組み立てられます。

この章の学習が終わったら

学習完了テストを受ける