Partitions and Addition Laws
In how many ways can a set be partitioned, broken into subsets, while assuming the independence of elements and ensuring that each element appears in only one subset? This question is often answered, for instance, when deciding how to partition workload across a network of computers. As systems become increasingly complex, the answer allows us to make best use of available resources.
2.3 Partitions of Sets and the Law of Addition
2.3.1 Partitions
One way of counting the number of students in your class would be to count the number in each row and to add these totals. Of course, this problem is simple because there are no duplications, no person is sitting in two different rows. The basic counting technique that you used involves an extremely important first step, namely that of partitioning a set. The concept of a partition must be clearly understood before we proceed further.
Definition 2.3.1: Partition. A partition of set A is a set of one or more nonempty subsets of A : A1, A2, A3, · · ·, such that every element of A is in exactly one set. Symbolically,
(a) A1 ∪ A 2 ∪ A3 ∪ · · · = A
(b) If i ≠ j then Ai ∩ Aj = ∅
The subsets in a partition are often referred to as blocks. Note how our definition allows us to partition infinite sets, and to partition a set into an infinite number of subsets. Of course, if A is finite the number of subsets can be no larger than |A |.
Example 2.3.2: Some partitions of a four element set. Let A = {a, b, c, d}. Examples of partitions of A are:
- {{a}, {b}, {c, d}}
- {{a, b}, {c, d}}
- {{a}, {b}, {c}, {d}}
How many others are there, do you suppose?
There are 15 different partitions. The most efficient way to count them all is to classify them by the size of blocks. For example, the partition {{ a}, {b } , {c, d }} has block sizes 1, 1, and 2.
Example 2.3.3: Some Integer Partitions. Two examples of partitions of set of integers Z are
- {{n} | n ∈ Z} and
- {{n ∈ Z | n < 0}, {0}, {n ∈ Z | 0 < n}}.
The set of subsets {{n ∈ Z | n ≥ 0}, {n ∈ Z | n ≤ 0}} is not a partition b ecause the two subsets have a nonempty intersection. A second example of a non-partition is {{n ∈ Z | |n| = k} | k = − 1 , 0, 1, 2 , · · · } because one of the blocks, when k = −1 is empty.
One could also think of the concept of partitioning a set as a “packaging problem.” How can one “package” a carton of, say, twenty-four cans? We could use: four six-packs, three eight-packs, two twelve-packs, etc. In all cases: (a) the sum of all cans in all packs must be twenty-four, and (b) a can must be in one and only one pack.
2.3.2 Addition Laws
Theorem 2.3.4: The Basic Law Of Addition: If A is a finite set, and if {A1, A 2, . . . , An} is a partition of A , then
The basic law of addition can be rephrased as follows: If A is a finite set where A 1 ∪ A2 ∪ · · · ∪ An = A and where Ai ∩ Aj = ∅ whenever i ≠ j, then
Example 2.3.5: Counting All Students. The number of students in a class could be determined by adding the numbers of students who are fresh- men, sophomores, juniors, and seniors, and those who belong to none of these categories. However, you probably couldn’t add the students by major, since some students may have double majors.
Example 2.3.6: Counting Students in Disjoint Classes. The sophomore computer science majors were told they must take one and only one of the following courses that are open only to them: Cryptography, Data Structures, or Javascript. The numbers in each course, respectively, for sophomore CS majors, were 75, 60, 55. How many sophomore CS majors are there? The Law of Addition applies here. There are exactly 75 + 60 + 55 = 190 CS majors since the rosters of the three courses listed above would be a partition of the CS majors.
Example 2.3.7: Counting Students in Non-disjoint Classes. It was determined that all junior computer science majors take at least one of the following courses: Algorithms, Logic Design, and Compiler Construction. Assume the number in each course was 75, 60 and 55, respectively for the three courses listed. Further investigation indicated ten juniors took all three courses, twenty-five took Algorithms and Logic Design, twelve took Algorithms and Compiler Construction, and fifteen took Logic Design and Compiler Construction. How many junior C.S. majors are there?
Example 2.3.6 was a simple application of the law of addition, however in this example, some students are taking two or more courses, so a simple application of the law of addition would lead to double or triple counting. We rephrase information in the language of sets to describe the situation more explicitly.
A = the set of all junior computer science majors
A1 = the set of all junior computer science majors who took Algorithms
A2 = the set of all junior computer science majors who took Logic Design
A3 = the set of all junior computer science majors who took Compiler
Construction
Since all junior CS majors must take at least one of the courses, the number we want is:
|A| = |A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − repeats.
A Venn diagram is helpful to visualize the problem. In this case, the universal set U can stand for all students in the university.
Figure 2.3.8 Venn Diagram
We see that the whole universal set is naturally partitioned into subsets that are labeled by the numbers 1 through 8, and the set A is partitioned into subsets labeled 1 through 7. The region labeled 8 represents all students who are not junior CS majors. Note also that students in the subsets labeled 2, 3, and 4 are double-counted, and those in the subset labeled 1 are triple counted. To adjust, we must subtract the numbers in regions 2, 3, and 4. This can be done by subtracting the numbers in the intersections of each pair of sets. However, the individuals in region 1 will have been removed three times, just as they had been originally added three times. Therefore, we must finally add their number back in.
|A| = |A1 ∪ A2 ∪ A3|
= |A1| + |A2| + |A3| − repeats
= |A1| + |A2| + |A3| − duplicates + triplicates
= |A1| + |A2| + |A3| − (|A1 ∩ A2| + |A1 ∩ A3| + |A2 ∩ A3|) + |A1 ∩ A2 ∩ A3|
= 75 + 60 + 55 − 25 − 12 − 15 + 10 = 148
The ideas used in this latest example gives rise to a basic counting technique:
Theorem 2.3.9: Laws of Inclusion-Exclusion. Given finite sets A1, A2, A3,then
(a) The Two Set Inclusion-Exclusion Law:
|A1 ∪ A2| = |A1| + | A2| − |A1 ∩ A2|
(b) The Three Set Inclusion-Exclusion Law:
|A1 ∪ A2 ∪ A3| = |A1 | + |A2| + |A3|− ( |A1 ∩ A 2 | + |A1 ∩ A3| + | A 2 ∩ A3| ) + |A1 ∩ A2 ∩ A3 |
The inclusion-exclusion laws extend to more than three sets, as will be explored in the exercises.
In this section we saw that being able to partition a set into disjoint subsets gives rise to a handy counting technique. Given a set, there are many ways to partition depending on what one would wish to accomplish. One natural partitioning of sets is apparent when one draws a Venn diagram.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.