Rule of sum
Encyclopedia
In combinatorics
, the rule of sum or addition principle is a basic counting principle
. Stated simply, it is the idea that if we have a ways of doing something and b 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.
More formally, the rule of sum is a fact about set theory
. It states that sum of the sizes of a finite collection of pairwise disjoint sets is the size of the union of these sets. That is, if
are pairwise disjoint sets, then we have:
Thus there are 3+2=5 possible shops the woman could end up shopping at today.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, the rule of sum or addition principle is a basic counting principle
Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.The rule of sum, rule of product, and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets...
. Stated simply, it is the idea that if we have a ways of doing something and b 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.
More formally, the rule of sum is a fact about set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
. It states that sum of the sizes of a finite collection of pairwise disjoint sets is the size of the union of these sets. That is, if
are pairwise disjoint sets, then we have:Simple example
A woman has decided to shop at one store today, either in the north part of town or the south part of town. If she visits the north part of town, she will either shop at a mall, a furniture store, or a jewelry store (3 ways). If she visits the south part of town then she will either shop at a clothing store or a shoe store (2 ways).Thus there are 3+2=5 possible shops the woman could end up shopping at today.
Inclusion-exclusion principle
The inclusion-exclusion principle 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 A1, ..., An are finite sets, thenSee also
- Combinatorial principle
- Rule of productRule of productIn combinatorics, the rule of product or multiplication principle is a basic counting principle...
- Inclusion-exclusion principleInclusion-exclusion principleIn combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...