跳转到内容

加法原理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

加法原理[1]rule of sum[2]:66[3]:342addition principle[4][5])是組合計數的基本組合原理。簡單而言,若有種方式做某事,又有種方式做另一件事,且恰好要做其中之一,則總共有種方案。[2][4]

嚴格化的數學中,加法原理是有關集合大小的事實,斷言任意有限多個兩兩互斥的集合大小之和,等於其聯集的大小。以符號表示為,若集合兩兩互斥,則有

[4][5]

簡單例子

[编辑]

設學校田徑運動會中,學生要報名恰好一個項目,可以是田賽或徑賽。若選田賽,則可以選跳高、跳遠、鉛球三項之一。若選徑賽,則可以選一百米跑、四百米跑兩項之一。

應用加法原理,共有種報名方案。

容斥原理

[编辑]
有左中右三幅圖,三幅畫的圖形一樣,但字不同。圖形是三個兩兩相交的圓,將平面總共分成八個區域。左邊一幅,僅被一個圓包圍的區域標1,僅被兩個圓包圍的區域標2,三個圓一同包圍的最中間區域標3,一共有三個1,三個2,一個3。左邊的圖下方算式是
三幅文氏圖,每個區域標的數,是該圖下方算式中,該區域(對應的集合)的元素數了多少次,驗證了容斥原理。

容斥原理可以視為加法原理的推廣,因為是同樣計算若干個集合之的大小,但不要求各集合兩兩互斥。其斷言,若為有限集,則

[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). 

參見

[编辑]
  • 其他組合技巧如:
    • 乘法原理——組合計數原理,計算從兩集合各取一個元素的方法數
    • 容斥原理——組合數學的計數技巧,重複數算的數目要扣除