Counting I Rule 2(Sum Rule). If A1, A2, .. An are disjoint sets, then JA1 U A2U... U An=A1+A2+.+Anl Thus, according to Linus budget, Lucy can be out-of-sorts for: CUI∪Sl=C|U|U|s 120 days Notice that the Sum Rule holds only for a union of disjoint sets. Finding the size of a union of intersecting sets is a more complicated problem that we'll take up later 2.2 The product rule The product rule gives the size of a product of sets. Recall that if Pi, P2,..., Pn are sets, then P1×P2 is the set of all sequences whose first term is drawn from Pi, second term is drawn from P and so forth Rule 3 (Product Rule). If P1, P2,... Pn are sets, then P×P2×….×Pn|=|f|·|P2|…|P Unlike the sum rule, the product rule does not require the sets Pi,..., Pn to be disjoint For example, suppose a daily diet consists of a breakfast selected from set B, a lunch from set L, and a dinner from set D pancakes, bacon and eggs L=burger and fries, garden salad, Doritos D=macaroni, pizza, frozen burrito, pasta, Doritos) Then BXLX Dis the set of all possible daily diets. Here are some sample elements pancakes, burger and frie es. pizza (bacon and eggs, garden salad, pasta) (Doritos, Doritos, frozen burrito) The Product rule tells us how many different daily diets are possible B×L×D|=|B·|L·Counting I 7 Rule 2 (Sum Rule). If A1, A2, . . . , An are disjoint sets, then: |A1 ∪ A2 ∪ . . . ∪ An| | | | | | = A1 + A2 + . . . + An| Thus, according to Linus’ budget, Lucy can be out­of­sorts for: | | C ∪ I ∪ S = | | ∪ | | ∪ | | C I S = 20 + 40 + 60 = 120 days Notice that the Sum Rule holds only for a union of disjoint sets. Finding the size of a union of intersecting sets is a more complicated problem that we’ll take up later. 2.2 The Product Rule The product rule gives the size of a product of sets. Recall that if P1, P2, . . . , Pn are sets, then P1 × P2 × . . . × Pn is the set of all sequences whose first term is drawn from P1, second term is drawn from P2 and so forth. Rule 3 (Product Rule). If P1, P2, . . . Pn are sets, then: |P1 × P2 × . . . × Pn| = | | · | P1 P2| · · · |Pn| Unlike the sum rule, the product rule does not require the sets P1, . . . , Pn to be disjoint. For example, suppose a daily diet consists of a breakfast selected from set B, a lunch from set L, and a dinner from set D: B = {pancakes, bacon and eggs, bagel, Doritos} L = {burger and fries, garden salad, Doritos} D = {macaroni, pizza, frozen burrito, pasta, Doritos} Then B × L × D is the set of all possible daily diets. Here are some sample elements: (pancakes, burger and fries, pizza) (bacon and eggs, garden salad, pasta) (Doritos, Doritos, frozen burrito) The Product Rule tells us how many different daily diets are possible: | | B × L × D = |B| · | | · | L D| = 4 3 5 · · = 60