乘法原理

乘法原理^[1]是組合計數的基本計數原理。簡而言之，「若有${\displaystyle a}$種方法做某事，${\displaystyle b}$種方法做另一事，則合共有${\displaystyle a\cdot b}$種方法做此兩件事。」^[2][3]

集合${\displaystyle \{A,B\}}$之元素，與集合${\displaystyle \{1,2,3\}}$的元素可以組成${\displaystyle 6}$種不同組合。

舉例

設在港式粉麵店要點一碗湯粉麵，主食有三種：粗麵、幼麵、河粉，要選恰好一款；而配料有兩種選擇：雲吞、牛腩，亦要選恰好一款。問可選配搭數為何。

使用乘法原理，答案是${\displaystyle 3\times 2=6}$，總共有六種配搭。

抽象一點，考慮從${\displaystyle A,B,C}$三件物件選一，再從${\displaystyle X,Y}$兩件物件選一。使用乘法原理，可知總共有${\displaystyle 3\times 2=6}$種選法。本例中，可以窮舉所有可能性驗證：可選的組合有${\displaystyle AX,AY,BX,BY,CX,CY}$，共六種。

上述例子中，集合${\displaystyle \{A,B,C\}}$和${\displaystyle \{X,Y\}}$不交，即兩次選擇中，沒有選項重複出現，但這並非必要，乘法原理即使兩次選擇的選項有相同，仍然成立。從${\displaystyle \{A,B,C\}}$選一個元素，然後再選一次，效果等同選取了一個有序對，其兩個分量都在${\displaystyle \{A,B,C\}}$中，選法的總數為${\displaystyle 3\times 3=9}$。

應用

集合論中，乘法原理可以視為基數乘積的定義。^[2]對於集合${\displaystyle S_{1},S_{2},\ldots ,S_{n}}$，以${\displaystyle |S_{i}|}$表示${\displaystyle S_{i}}$的元素個數（基數），則有

${\displaystyle |S_{1}|\cdot |S_{2}|\cdots |S_{n}|=|S_{1}\times S_{2}\times \cdots \times S_{n}|,}$

其中${\displaystyle \times }$表示笛卡兒積。${\displaystyle S_{i}}$可以是無窮集，甚至可以考慮無窮多個集合的乘積，參見基數和選擇公理。

參見

• 加法原理是另一個基本計數原理。簡而言之，「若有${\displaystyle a}$種方法做某事，${\displaystyle b}$種方法做另一事，但只能選其一，則合共有${\displaystyle a+b}$種選擇。」^[4]
• 其他組合技巧