Disjoint Sets and the Addition Rule

  1. The Addition Rule for Disjoint Sets.

    1. If a finite set S equals the union of n distinct and mutually disjoint subsets, then the number of elements in A equals the sum of the numbers of elements in the subsets.

      In other words if finite set S equals the union of n distinct, mutually disjoint subsets A1, A2, ..., An, then

                  n
      N(S) = ∑ N(Ak)
                k=1

    2. Examples:

      1. A password for your computer. Suppose you decide to create a password made up of capital letters of the alphabet, and ≤ 3 characters in length. How many ways can you choose such a password?

        Solution:
        Let S = {passwords from capital letters | length ≤ 3}
        Let A1 = {password from capital letters | length = 1}
        Let A2 = {password from capital letters | length = 2}
        Let A3 = {password from capital letters | length = 3}

        Since S = A1 union A2 union A3, and the subsets are distinct, and the subsets are mutually disjoint, we can apply the Addition Rule.

        What is N(A1)?
        What is N(A2)?
        What is N(A3)?
        What is N(S)? Do the math. Did you get 18,278?

      2. A password for an online shopping account. The rules say that your password must be at least 5 characters long, no more than 8 characters long, and made up of capital letters and digits.

        Solution:
        Let S = {passwords from the 36 letters & digits | 5 ≤ length ≤ 8}

        Now form four distinct, mutually disjoint subsets, calculate the number of elements in each subset, and add up the numbers. Do the math. Did you get 2,901,711,320,064? Or, wouldn't your calculator show that many digits?

  2. The Difference Rule for a Set and a Subset.

    1. If A is a finite set and B is a subset, then N(A - B) = N(A) - N(B).

      This must be true, because B and A - B are disjoint sets whose union is A. Thus, N(A) = N(B) + N(A - B).

    2. In the special case where A is a universal set (the set of all possible outcomes), the difference rule gives us
      P(Bc) = P(U) - P(B), which simplifies to P(Bc) = 1 - P(B).

      Perhaps that seems obvious, since another way to write it is P(B) + P(Bc) = 1
      (every outcome is either in an event or its complement)

    3. Examples:

      1. A password for an online shopping account. The rules say that your password must be at least 3 characters long, no more than 4 characters long, made up of capital letters, and have at least one letter that appears more than once.

        Solution:
        Let U = {password from capital letters | 3 ≤ length ≤ 4}      (passwords with or without repetition)
        Let X = {x element of U | no letters are repeated}                            (passwords without repetition)
        Then our solution set is S = U - X, or Xc                            (passwords with repetition)

        Break U into U3 union U4.
        Use the Multiplication Rule to calculate N(U3) and N(U4).
        Use the Addition Rule to calculate N(U) = N(U3) + N(U4).

        Break X into X3 union X4.
        Use the Multiplication Rule to calculate N(X3) and N(X4).
        Use the Addition Rule to calculate N(X) = N(X3) + N(X4).

        Use the Difference Rule to calculate N(S) = N(U) - N(X).

  3. Inclusion/Exclusion Rule for Overlapping Sets.

    1. If A and B are any finite (possibly overlapping) sets, then

      N(A union B) = N(A) + N(B) - N(A intersection B)

      Similarly, if A, B, and C are any finite sets, then

      N(A union B union C) = N(A) + N(B) + N(C) - N(A intersection B) - N(A intersection C) - N(B intersection C) + N(A intersection B intersection C)

      It should seem reasonable that using mathematical induction we could prove that similar formulas hold for unions of n sets, where n is any integer > 1.

    2. Examples:

      1. How many integers from 1 through 1,000 are multiples of 3 or multiples of 5?

        1, 2, 3=3*1, 4, 5, 6=3*2, 7, ..., 999=333*3 so there are 333 multiples of 3

        1, 2, 3, 4, 5=5*1, 6, 7, 8, 9, 10=5*2, 11, ..., 1000=5*200 so there are 200 multiples of 5.

        1, 2, 3, ..., 15=15*1, ..., 30=15*2, ..., 990=15*66, 991, 992, ..., 1000 so there are 66 multiples of 15

        By the Inclusion/Exclusion Rule for Overlapping Sets:
        N({mults of 3} union {mults of 5}) = N({mults of 3}) + N({mults of 5}) - N({mults of 3} intersection {mults of 5})
        = 333 + 200 - 66 = 467

      2. How many integers from 1 through 1,000 are neither multiples of 3, nor muliples of 5?

        We know how many integers there are in all, and we know how many of them are multiples of 3 or 5, so use the Difference Rule.

      3. Suppose we have a class of students, all students in the class own either an Xbox or a PlayStation, 15 students own an Xbox, 12 students own a PlayStation, and 5 students own both an Xbox and a PlayStation.

        How many students are in the class?

        We know how many are in each of the two subsets, and the intersection, so use the Inclusion/Exclusion Rule to figure out how many are in the class.