数え上げの積の法則

The elements of the set {A, B} can combine with the elements of the set {1, 2, 3} in six different ways.

初等組合せ論における積の法則（せきのほうそく、英: rule of product）あるいは乗法原理 (multiplication principle) は基本的な組合せ原理（英語版）（数え上げの基本原理）の一つである。それは、簡単に言えば「ある場合が $a$ 通り、別のある場合が $b$ 通りあるとき、それらを同時に行う場合は $a\cdotb$ 通りある」ことを述べるものである^[1]^[2]。

例

{A, B, C}

から一つと

{X, Y}

から一つを選ぶことは、

{AX, AY, BX, BY, CX, CY}

を一つ選ぶことである。

この例では、積の法則は $3 \times 2 = 6$ と表すことができる。

この例における集合 ${A, B, C}$ および ${X, Y}$ は互いに交わらないが、それは必要なことではない。

例えば、 ${A, B, C}$ から一つ選び、再度同じ集合から一つ選ぶとすれば、それは ${A, B, C}$ の要素からなる順序対を選ぶことと理解されるから、 $3 \times 3 = 9$ 通りになる。

別な例として、ピザの注文で生地の種類を薄いか厚いかの $2$ 種類と、トッピングをチーズ・ペペロニ・ソーセージの $3$ 種類から選べるとすると、積の法則を用いれば、ピザの注文方法が $2 \times 3 = 6$ 通り可能であるとわかる。

応用

集合論において、乗法原理は基数の積の定義に用いられる^[1]。集合の濃度に関して $|S_{1}|\cdot |S_{2}|\cdots |S_{n}|=|S_{1}\times S_{2}\times \cdots \times S_{n}|$ が成り立つ（右辺の $\times$ はデカルト積演算である）。これらの各集合は有限集合である必要はなく、またこれら因子の数が有限個である必要もない。

参考文献

^ ^a ^b Johnston, William, and Alex McAllister. A transition to advanced mathematics. Oxford Univ. Press, 2009. Section 5.1
^ “[http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut55_count.htm College Algebra Tutorial 55: Fundamental Counting Principle]”. December 20, 2014閲覧。
^ Rosen, Kenneth H., ed. Handbook of discrete and combinatorial mathematics. CRC press, 1999.

外部リンク

Weisstein, Eric W. "Multiplication Principle". mathworld.wolfram.com (英語).
rule of product - PlanetMath.（英語）
Product Rule for Counting at ProofWiki

[transition-1] Johnston, William, and Alex McAllister. A transition to advanced mathematics. Oxford Univ. Press, 2009. Section 5.1

[2] “[http://www.wtamu.edu/academic/anns/mps/math/mathlab/col_algebra/col_alg_tut55_count.htm College Algebra Tutorial 55: Fundamental Counting Principle]”. December 20, 2014閲覧。

[3] Rosen, Kenneth H., ed. Handbook of discrete and combinatorial mathematics. CRC press, 1999.

[1]

[2]

[3]

数え上げの積の法則

例

応用

関連概念

関連項目

参考文献

外部リンク