View source for Rule of sum

[[File:AdditionZero.svg|alt=A collection of five dots and one of zero dots merge into one of five dots.|thumb|193x193px|5+0=5 illustrated with collections of dots.]]
In [[Combinatorics|combinatorics]], the '''rule of sum'''<ref name=":0">{{Cite book|last1=Leung|first1=K. T.|url=https://books.google.com/books?id=QqgaZ799QGAC&q=%22rule+of+sum%22|title=Fundamental Concepts of Mathematics|last2=Cheung|first2=P. H.|date=1988-04-01|publisher=Hong Kong University Press|isbn=978-962-209-181-8|language=en}}</ref><ref>{{Cite book|last=Penner|first=R. C.|url=https://books.google.com/books?id=t5r79vZ9ogoC&dq=%22rule+of+sum%22+AND+%22mathematics%22&pg=PA342|title=Discrete Mathematics: Proof Techniques and Mathematical Structures|date=1999|publisher=World Scientific|isbn=978-981-02-4088-2|language=en}}</ref>{{Verify source|date=August 2021}} or '''addition principle<ref name=":1">{{Cite book|last=Biggs|first=Norman L.|title=Discrete Mathematics|publisher=[[Organization:Oxford University Press|Oxford University Press]]|year=2002|isbn=978-0-19-871369-2|location=India|pages=91, 112}}</ref>'''<ref name=":2">{{Cite web|date=22 March 2013|title=enumerative combinatorics|url=https://planetmath.org/EnumerativeCombinatorics|url-status=live|archive-url=https://web.archive.org/web/20140723121944/https://planetmath.org/EnumerativeCombinatorics|archive-date=23 July 2014|access-date=14 August 2021|website=planetmath.org}}</ref> is a basic [[Combinatorial principles|counting principle]].  Stated simply, it is the intuitive idea that if we have ''A'' number of ways of doing something and ''B'' number of ways of doing another thing and we can not do both at the same time, then there are ''A''&nbsp;+&nbsp;''B'' ways to choose one of the actions.<ref name=":0" /><ref name=":1" />
[[File:AdditionShapes.svg|alt=Five shapes split into a group of three shapes and one of two shapes.|left|thumb|110x110px|3+2=5 illustrated with shapes.{{Relevant-inline|date=August 2021}}]]
More formally, the rule of sum is a fact about [[Set theory|set theory]].{{Verify source|date=August 2021}}  It states that sum of the sizes of a finite collection of pairwise [[Disjoint sets|disjoint sets]] is the size of the union of these sets.  That is, if <math>S_{1}, S_{2},..., S_{n}</math> are pairwise disjoint sets, then we have:<ref name=":1" /><ref name=":2" />
<math display="block">|S_{1}|+|S_{2}|+\cdots+|S_{n}| = |S_{1} \cup S_{2} \cup \cdots \cup S_{n}|. </math>

== Simple example ==

A person has decided to shop at one store today, either in the north part of town or the south part of town. If they visit the north part of town, they will shop at either a mall, a furniture store, or a jewelry store (3 ways). If they visit the south part of town then they will shop at either a clothing store or a shoe store (2 ways).

Thus there are 3+2=5 possible shops the person could end up shopping at today.{{Citation needed|date=August 2021}}

== Inclusion–exclusion principle ==

{{main|Inclusion–exclusion principle}}
[[File:Inclusion-exclusion-3sets.png|alt=A series of Venn diagrams illustrating the principle of inclusion-exclusion.|thumb|248x248px|A series of [[Venn diagram|Venn diagrams]] illustrating the principle of inclusion-exclusion.]]
The '''inclusion–exclusion principle''' (also known as the '''sieve principle<ref name=":1" />''') can be thought of as a generalization of the rule of sum in that it too enumerates the number of elements in the union of some sets (but does not require the sets to be disjoint). It states that if ''A''<sub>1</sub>, ..., ''A<sub>n</sub>'' are finite sets, then<ref name=":1" />
<math display="block">\left|\bigcup_{i=1}^n A_i\right| =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| + \sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.</math>

== References ==
{{Reflist}}

== See also ==

*Combinatorial principle
*[[Rule of product]]
*[[Inclusion–exclusion principle]]
[[Category:Combinatorics]]
[[Category:Mathematical principles]]

fi:Todennäköisyysteoria#Tuloperiaate ja summaperiaate

{{Sourceattribution|Rule of sum|1}}