加法原理

加法原理[1]rule of sum[2]:66[3]:342addition principle[4][5])是组合计数的基本组合原理。简单而言,若有种方式做某事,又有种方式做另一件事,且恰好要做其中之一,则总共有种方案。[2][4]

严格化的数学中,加法原理是有关集合大小的事实,断言任意有限多个两两互斥的集合大小之和,等于其并集的大小。以符号表示为,若集合两两互斥,则有

[4][5]

简单例子

设学校田径运动会中,学生要报名恰好一个项目,可以是田赛或径赛。若选田赛,则可以选跳高、跳远、铅球三项之一。若选径赛,则可以选一百米跑、四百米跑两项之一。

应用加法原理,共有 种报名方案。

容斥原理

 
三幅文氏图,每个区域标的数,是该图下方算式中,该区域(对应的集合)的元素数了多少次,验证了容斥原理。

容斥原理可以视为加法原理的推广,因为是同样计算若干个集合之的大小,但不要求各集合两两互斥。其断言,若 为有限集,则

 [4]

参考文献

  1. ^ 国家教育研究院. addition rule. 双语词𢑥、学术名词暨辞书资讯网. [2021-09-03]. (原始内容存档于2021-09-04). 
  2. ^ 2.0 2.1 Leung, K. T.; Cheung, P. H. Fundamental Concepts of Mathematics. Hong Kong University Press. 1988-04-01 [2021-09-03]. ISBN 978-962-209-181-8. (原始内容存档于2021-08-14) (英语). 
  3. ^ Penner, R. C. Discrete Mathematics: Proof Techniques and Mathematical Structures. World Scientific. 1999 [2021-09-03]. ISBN 978-981-02-4088-2. (原始内容存档于2021-08-14) (英语). 
  4. ^ 4.0 4.1 4.2 4.3 Biggs, Norman L. Discrete Mathematics. India: Oxford University Press. 2002: 91, 112. ISBN 978-0-19-871369-2. 
  5. ^ 5.0 5.1 enumerative combinatorics. planetmath.org. 22 March 2013 [14 August 2021]. (原始内容存档于2014-07-23). 

参见

  • 其他组合技巧如:
    • 乘法原理——组合计数原理,计算从两集合各取一个元素的方法数
    • 容斥原理——组合数学的计数技巧,重复数算的数目要扣除