積と和の法則で公式を作る

Copyright (C) virtual_high_school, 1996-2018

積の法則は、直積集合に関する定理である。直積とは、2つ以上の集合から生成される集合である。文字どおり product なのである。
一方、和の法則は、集合の直和分解に関する定理であって、現にいまここにある集合をこう分けるとこうなる、というものである。一見すると、新たなものを創造しない働きのようだ。

ところが、実際は話は逆なのだ。和の法則の方が、創造的な働きをする。積の法則(順列・組合せ)を使って解ける問題に、わざと和の法則を適用する。すると、思いもかけぬ公式を得ることができる。

【例題】
1,2,3,4,5 の5つの数字から3つの数字を選ぶ方法は何通りか。---

(解) 答は$_{5}C_{3} =10$通りだ。

(別解) 全体を、選んだ3つの中で最も若い番号が「1であるもの」、「2であるもの」、「3であるもの」の3クラスに直和分解する。すると、
　　　$ _{4}C_{2} + _{3}C_{2} + _{2}C_{2} =6+ 3 + 1 =10$通り。

結局、
　　　$_{5}C_{3} = _{4}C_{2} + _{3}C_{2} + _{2}C_{2}$
が成り立つ。


この式を一般化すると
　　　$_{n}C_{3} = _{n-1}C_{2} + _{n-2}C_{2} + \cdots + _{2}C_{2}$
という公式が誕生する。
さらに一般化すれば
　　　$_{n}C_{r} = _{n-1}C_{r-1} + _{n-2}C_{r-1} + \cdots + _{r-1}C_{r-1}$

よって、上の例題の場合、
　　　$_{4}C_{2} = _{3}C_{1} + _{2}C_{1} + _{1}C_{1} = 3+2+1 $
　　　$_{3}C_{2} = _{2}C_{1} + _{1}C_{1} = 2+1 $
　　　$_{2}C_{2} = _{1}C_{1} = 1$
となることから、これらを先の式に代入すると
　　　$_{5}C_{3} = (3+2+1)+(2+1)+1 = 1 \times 3 + 2 \times 2 + 3 \times 1$
すなわち
　　　$ _{5}C_{3} = \displaystyle \sum_{k=0}^{4} k(4-k) $
となる。

これもまた一般化すれば
　　　$_{n}C_{3} = \displaystyle \sum_{k=0}^{n-1} k(n-1-k) $
という公式を得る。

(証明)
　　　右辺$=\displaystyle \sum_{k=0}^{n-1} k(n-1-k) = (n-1) \displaystyle \sum_{k=0}^{n-1} k - \displaystyle \sum_{k=0}^{n-1} k^{2}$
　　　$ = (n-1) \frac{n(n-1)}{2} - \frac{n(n-1)(2n-1)} {6} = \frac{n(n-1)(n-2)}{3!}=$左辺■

教科書によく出てくる例題を挙げておこう。

【例題】
集合の要素の個数を$n$とする。この集合の部分集合は何個あるか。(部分集合全体の集合を元の集合のベキ集合という。)---

(解) $U =\{ a_{1}, a_{2}, \cdots, a_{n} \}$の各要素について、それが部分集合$A$に含まれるか含まれないかの２通りだから、全要素が含まれるか否かは、
　　　$2 \times 2 \times \cdots \times 2 = 2^{n}$通り
の場合がある。したがって、部分集合はそれに対応して、$2^{n}$個ある。

(別解) 要素数が0個の部分集合(すなわち空集合)が$_{n}C_{0}=1$個、要素数が1個の部分集合(すなわち単位集合＝シングルトン)が$_{n}C_{1}=n$個、要素数が2個の部分集合が$_{n}C_{2}=n(n-1)/2!$個、……、要素数が$n$個の部分集合(すなわち全体集合)が$_{n}C_{n}=1$個ある。これらを総計すれば、部分集合の個数は
　　　$_{n}C_{0} + _{n}C_{1} + _{n}C_{2} + \cdots + _{n}C_{n}$個である。

上記のことから
　　　$_{n}C_{0} + _{n}C_{1} + _{n}C_{2} + \cdots + _{n}C_{n} = 2^{n}$
という公式が得られる。もっとも二項定理を使えば
　　　$(x+y)^{n} = _{n}C_{0}x^{n} + _{n}C_{1}x^{n-1}y + _{n}C_{2}x^{n-2}y^{2} + \cdots + _{n}C_{n}y^{n}$
だから、ここに$x=y=1$を代入することによっても証明できる。

このように和の法則と積の法則を両用することによって、役に立つのかどうかは分からないが、とにかく公式がワンサカ出てくる。