乘法原理

乘法原理[1]组合计数的基本计数原理。简而言之,“若有种方法做某事,种方法做另一事,则合共有种方法做此两件事。”[2][3]

集合之元素,与集合的元素可以组成种不同组合。

举例

设在港式粉面店要点一碗汤粉面,主食有三种:粗面、幼面、河粉,要选恰好一款;而配料有两种选择:云吞牛腩,亦要选恰好一款。问可选配搭数为何。

使用乘法原理,答案是 ,总共有六种配搭。

抽象一点,考虑从 三件物件选一,再从 两件物件选一。使用乘法原理,可知总共有 种选法。本例中,可以穷举所有可能性验证:可选的组合有 ,共六种。

上述例子中,集合  不交,即两次选择中,没有选项重复出现,但这并非必要,乘法原理即使两次选择的选项有相同,仍然成立。从 选一个元素,然后再选一次,效果等同选取了一个有序对,其两个分量都在 中,选法的总数为 

应用

集合论中,乘法原理可以视为基数乘积的定义。[2]对于集合 ,以 表示 的元素个数(基数),则有

 

其中 表示笛卡儿积 可以是无穷集,甚至可以考虑无穷多个集合的乘积,参见基数选择公理

参见

  • 加法原理是另一个基本计数原理。简而言之,“若有 种方法做某事, 种方法做另一事,但只能选其一,则合共有 种选择。”[4]
  • 其他组合技巧

参考文献

  1. ^ 国家教育研究院. multiplication rule. 双语词𢑥、学术名词暨辞书资讯网. [2021-09-03]. (原始内容存档于2021-09-03). 
  2. ^ 2.0 2.1 Johnston, William, and Alex McAllister. A transition to advanced mathematics. Oxford Univ. Press, 2009. Section 5.1
  3. ^ College Algebra Tutorial 55: Fundamental Counting Principle. [December 20, 2014]. (原始内容存档于2018-10-11). 
  4. ^ Rosen, Kenneth H., ed. Handbook of discrete and combinatorial mathematics页面存档备份,存于互联网档案馆). CRC pres, 1999.