CountingCarlo TomasiTo count means to determine the cardinality of a set, that is, the number of elements it contains. Thecardinality of a set S is denoted by ](S).This note shows two different counting methodologies. The first one establishes a calculus for the car-dinalities of sets constructed from sets of known cardinalities through the following composition operators:(i) union of disjoint sets (“set addition”); (ii) set difference between a set and a subset of it (“set subtrac-tion”); (iii) Cartesian product of sets. In contrast with other set operators such as union and intersection, thecardinalities of the sets obtained through these three operators are known functions of the cardinalities ofthe constituent sets.The second method can be applied whenever a set can be defined by specifying a procedure for con-structing its elements. The cardinality of the set in question is then determined by counting the optionsavailable for constructing a general member of the set.1 Counting through Set CompositionSets are often built by applying composition operators such as union, intersection, complement, Cartesianproduct, and so forth to other sets. It would be convenient if were possible to express the cardinality of suchcompositions as a function of the cardinalities of the constituent sets. This is possible for the cross product(or Cartesian product) of sets:](A × B) = ](A)](B) . (1)When cross products are computed, the universes UAand UBin which A and B are defined are multipliedas well to yield U = UA× UBfor A × B.Unfortunately, no counting rules are generally associated with the other set-composition operators. Forinstance, the cardinality of the union or intersection of two sets A and B cannot be determined from thoseof A and B. We only have bounds:max(](A), ](B)) ≤ ](A ∪ B) ≤ ](A) + ](B)where the lower bound is attained when one set is contained in the other, and the upper bound is attainedwhen the two sets are disjoint. Similarly,0 ≤ ](A ∩ B) ≤ min(](A), ](B)) .Here, the lower bound is attained when the two sets are disjoint and the upper bound when one set iscontained in the other.When A and B are not disjoint, the following inclusion-exclusion formula holds:](A ∪ B) = ](A) + ](B) − ](A ∩ B)1because the elements in the intersection are counted once in ](A) and once again in ](B). Similar resultscan be obtained by partitioning the union of A and B, that is, by rewriting it as a union of disjoint sets:A ∪ B = A ∪ (A ∩ B) = (A ∩ B) ∪ B = (A ∩ B) ∪ (A ∩ B) ∪ (A ∩ B) .This then yields the following three partitioned counting formulas:](A ∪ B) = ](A) + ](A ∩ B) = ](A ∩ B) + ](B) = ](A ∩ B) + ](A ∩ B) + ](A ∩ B) . (2)These results are useful when the cardinalities of the various intersections that appear in them can be com-puted in some separate way. Fortunately, this is often the case.Exercise. Draw Venn diagrams for all the formulas above.A useful formal device for counting is to use a different symbol for the union of two sets when the twosets are disjoint:A + B =½A ∪ B if A ∩ B = ∅undefined otherwiseand to say that in that case A and B are added together. Set addition should not be viewed as a new setoperator, but merely as the old union operator with emphasis added on the fact that A and B are disjoint. Itis an error to write A + B if A and B are not disjoint, just as it would be an error to write0abc0+ 2 withouthaving defined the meaning of ’+’ when applied to a string and a number.If C = A + B, then we can write A = C − B or B = C − A as long as we interpret the set subtractionoperator ’−’ as follows:C − B =½C \ B if B ⊆ Cundefined otherwisewhere ’\’ is the set difference. Note in particular that if U is the universe, then the complement of a set Acan be written as A = U −A. This is useful whenever computing the cardinality of A is hard but computingthose of U and A is easier, or vice versa.In summary, the elements of a set S can be counted as follows:• Determine a collection of basic sets S1, . . . , Snwhose cardinality is known.• Write S as a combination of cross products and set addition and subtraction operations, starting fromthe basic sets.• In the resulting combination, replace the basic sets with their cardinalities, set additions with sums,set subtractions with differences, and set cross products with products.• Compute the value of the resulting formula.2 ExampleConsider a simplified password scheme for some security application. Valid characters for a password arethe 26 letters of the alphabet (case insensitive, so ’A’ and ’a’ are the same letter) and the ten digits from 0 to9. A password is a nonempty string of up to three characters, at least one of which must be a digit. If more2digits are present, they must be different. For instance, the strings ’2’ ’15’, ’317’, ’A6C’, ’2B’ are valid.Examples of invalid passwords are ’C11’ (digit repetition), ’ABC’ (no digit), and ’BC36’ (too long). Howmany passwords are possible in this scheme?In this case, basic sets are simple to define: The universe C for each character in the password is the setof alphanumeric characters, and ](C) = 36. Digits and letters form the sets D and L with cardinality 10and 26, respectively.The set P of passwords can be written as the set addition of the sets of valid passwords with one, two,or three characters:P = P1+ P2+ P3whereP1= {passwords with one character}P2= {passwords with two characters}P2= {passwords with three characters} .These sets are disjoint, because a password cannot have two different lengths at the same time. A one-character password must be a digit, so we easily haveP1= D ,a basic set. P2can be written as the set Q2of all two-character passwords that ignore the rule about distinctdigits, minus the set V2of those that violate it (a subset of Q2). Violations are most easily listed:V2= {00, 11, 22, 33, 44, 55, 66, 77, 88, 99} ,so this can be considered a basic set. The set Q2can be specified in different ways. One is to first start witha unionQ2= {two-character passwords starting with a digit}∪ {two-character passwords ending with a digit} .[Note that the first component of Q2contains all the repeated-digit pairs in V2.] These two sets are notdisjoint, so they can be partitioned:Q2= {two-character passwords starting with a digit}+ {two-character passwords starting with a letter and ending with a digit}(without this partitioning, we
View Full Document
Unlocking...