Counting I 2.3 Putting rules Together Few counting problems can be solved with a single rule. More often, a solution is a flury of sums, products, bijections, and other methods. Let's look at some examples that bring more than one rule into play Passwords The sum and product rules together are useful for solving problems involving passwords, telephone numbers, and license plates. For example, on a certain computer system,a valid password is a sequence of between six and eight symbols. The first symbol must be a letter(which can be lowercase or uppercase), and the remaining symbols must be either letters or digits. How many different passwords are possible? Lets define two sets, corresponding to valid symbols in the first and subsequent posi tions in the password F={a,b,…,z,A,B,…,Z} S={a,b,…,z,A,B,…,Z,0,1,…,9} In these terms, the set of all possible passwords is (F×S5)u(F×S)U(F×S) Thus, the length-six passwords are in set Fx S5, the length-seven passwords are in FxS6, and the length-eight passwords are in FX S. Since these sets are disjoint, we can apply the Sum Rule and count the total number of possible passwords as follows (F×S)U(F×S0)U(F×S)=F×s+|F×S+|F×S( Sum rule FI SP+IF1. ISI+F1. S7 Product rule 625+52·626+52.627 ≈1.8·104 different passwords Subsets of an n-element set How many different subsets of an n element set X are there? For example, the set X Lc1, 12, Is has eight different subsets {}{x1}{x2}{x1,x2} {x3}{x1,x3}{x2,x3}{x1,x2,x3} There is a natural bijection from subsets of X to n-bit Let 1 the elements of X. Then a particular subset of X maps to the sequence(b1,., bn)� � � � � � � � � � � � � � � � 8 Counting I 2.3 Putting Rules Together Few counting problems can be solved with a single rule. More often, a solution is a flury of sums, products, bijections, and other methods. Let’s look at some examples that bring more than one rule into play. Passwords The sum and product rules together are useful for solving problems involving passwords, telephone numbers, and license plates. For example, on a certain computer system, a valid password is a sequence of between six and eight symbols. The first symbol must be a letter (which can be lowercase or uppercase), and the remaining symbols must be either letters or digits. How many different passwords are possible? Let’s define two sets, corresponding to valid symbols in the first and subsequent posi￾tions in the password. F = {a, b, . . . , z, A, B, . . . , Z} S = {a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9} In these terms, the set of all possible passwords is: (F × S5 ) ∪ (F × S6 ) ∪ (F × S7 ) Thus, the length­six passwords are in set F ×S5, the length­seven passwords are in F ×S6 , and the length­eight passwords are in F × S7. Since these sets are disjoint, we can apply the Sum Rule and count the total number of possible passwords as follows: = F × S7 S Sum Rule 5 S6 S7 F × S5 F × S6 (F × ) ∪ (F × ) ∪ (F × ) + + 5 6 7 = |F| · | | S + |F S | · | | + |F S | · | | Product Rule = 52 · 625 + 52 626 + 52 627 · · ≈ 1.8 · 1014 different passwords Subsets of an n­element Set How many different subsets of an n element set X are there? For example, the set X = {x1, x2, x3} has eight different subsets: {} { { { x1} x2} x1, x2} {x3} {x1, x3} {x2, x3} {x1, x2, x3} There is a natural bijection from subsets of X to n­bit sequences. Let x1, x2, . . . , xn be the elements of X. Then a particular subset of X maps to the sequence (b1, . . . , bn)