addition principle

File:AdditionZero.svg

In combinatorics, the addition principle{{Sfn|Biggs|2002|p=91}}{{Cite web |last=mps |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}} or rule of sum{{Cite book |last1=Leung |first1=K. T. |url=https://books.google.com/books?id=QqgaZ799QGAC&pg=PA66 |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 |pages=66 |language=en}}{{Cite book |last=Penner |first=R. C. |url=https://books.google.com/books?id=t5r79vZ9ogoC&pg=PA342 |title=Discrete Mathematics: Proof Techniques and Mathematical Structures |date=1999 |publisher=World Scientific |isbn=978-981-02-4088-2 |pages=342 |language=en}} is a basic 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 + B$ ways to choose one of the actions.{{Sfn|Biggs|2002|p=91}} In mathematical terms, the addition principle states that, for disjoint sets A and B, we have $|A\cup B| = |A| + |B|$ , provided that the intersection of the sets is without any elements.

The rule of sum is a fact about set theory,{{Cite web |date=2021-08-24 |title=4.1: Definition and Properties |url=https://math.libretexts.org/Courses/Hartnell_College/Mathematics_for_Elementary_Teachers/04%3A_______Addition_and_Subtraction/4.01%3A_Definition_and_Properties |access-date=2024-05-02 |website=Mathematics LibreTexts |language=en}} as can be seen with the previously mentioned equation for the union of disjoint sets A and B being equal to |A| + |B|.{{Cite web |title=Rule of sum and rule of product {{!}} Combinatorics {{!}} Discrete math {{!}} Math |url=https://hyperskill.org/learn/step/23705 |access-date=2024-05-02 |website=Hyperskill |language=en}}

The addition principle can be extended to several sets. If $S_1, S_2,\ldots, S_n$ are pairwise disjoint sets, then we have:{{Sfn|Biggs|2002|p=91}} $|S_1|+|S_2|+\cdots+|S_{n}| = |S_1 \cup S_2 \cup \cdots \cup S_n|.$ This statement can be proven from the addition principle by induction on n.

Simple example

File:AdditionShapes.svgA 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.

Inclusion–exclusion principle

File:Inclusion-exclusion-3sets.png illustrating the principle of inclusion-exclusion.]]

The inclusion–exclusion principle (also known as the sieve principle{{Sfn|Biggs|2002|p=112}}) 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₁, ..., A_n are finite sets, then{{Sfn|Biggs|2002|p=112}}

$\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\ + (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.$

Subtraction principle

Similarly, for a given finite set S, and given another set A, if $A \subset S$ , then $|A^c| = |S| - |A|$ .{{Cite book |last=Diedrichs |first=Danilo R. |title=Transition to advanced mathematics |date=2022 |others=Stephen Lovett |isbn=978-1-003-04620-2 |location=Boca Raton, FL |page=172 |oclc=1302331608}}{{Cite web |last=Moreno |first=Miguel |date=2018 |title=Lecture notes: Combinatorics |url=https://u.math.biu.ac.il/~morenom3/Combinatorics%20spring%202018.pdf |url-status=live |archive-url=https://web.archive.org/web/20190819024109/https://u.math.biu.ac.il/~morenom3/Combinatorics%20spring%202018.pdf |archive-date=19 August 2019 |access-date=26 November 2022 |website=u.math.biu.ac.il}} To prove this, notice that $|A^c| + |A| = |S|$ by the addition principle.

Applications

The addition principle can be used to prove Pascal's rule combinatorially. To calculate $\binom{n + 1}{k}$ , one can view it as the number of ways to choose k people from a room containing n children and 1 teacher. Then there are $\binom{n}{k}$ ways to choose people without choosing the teacher, and $\binom{n}{k-1}$ ways to choose people that includes the teacher. Thus $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$ .{{Cite arXiv |eprint=2108.04902 |author=Henry Adams |author2=Kelly Emmrich |author3=Maria Gillespie |author4=Shannon Golden |author5=Rachel Pries |title=Counting Rocks! An Introduction to Combinatorics |date=15 November 2021|class=math.HO }}{{Rp|page=83}}

The addition principle can also be used to prove the multiplication principle.

References

= Bibliography =

{{Cite book |last=Biggs |first=Norman L. |title=Discrete Mathematics |publisher=Oxford University Press |year=2002 |isbn=978-0-19-871369-2 |location=India}}