場合の数の和の法則の解説と例題

場合の数の和の法則についてと、例題を挙げます。

事象A,Bがあるとします。
$A \cap B = \varnothing$
(2つの事象に重複がない)とすると

$n(A \cap B) = n(A) + n(B)$

が成り立ちます。
重複がないので、加算することができます。

両者の事象が共通点がないので、加算することができるため和の法則とつけたのでしょう。

では、和の法則を使うことになる例題を

まず、硬貨を全て使うという条件なので、
支払う対象となる金額は、

400 - (10 + 50 + 100) = 240

となります。

支払う硬貨の枚数を100円,50円,10円をそれぞれ
x,y,zとすると、x,y,zは0以上の整数で

10x + 5y + z = 24

とおくことができるので、この場合の数を考えていきます。

ここで、大きい金額xを基準にして、場合わけしていきます。

x = 2の時
5y + z = 4

よって
(y,z) = (0,4)

x = 1の時
5y + z = 14

よって
(y,z) = (2,4),(1,9),(0,14)

x = 0の時
5y + z = 24

よって
(y,z) = (4,4),(3,9),(2,14),(1,19),(0,24)

x = 2,1,0の場合は同時に起こらないので、和の法則より各々の場合の数を足して

9通りとなります。

数が大きい場合は、数値を一般化して求めていきます。
まず、400円のケースと同様にして

10x + 5y + z = 984

xを基準に考えると、
x = 98,97,・・・,1,0

x = 98の時、5y + z = 4となり、
400円の時のケースと変わりません。

よって、このxの値に対して満たす(y,z)の組みの個数はそれぞれ、
1,3,5,・・・,195,197となります。

197は相関を考えて、99 × 2 - 1から求めます。

よって求める場合の数は、
1 + 3 + 5 + ・・・ + 195 + 197 = 9801通り

と求められます。

初版:2018/6/22