Cartesian Products An ordered pair is a list x y of two things x and y enclosed in parenthesis and separated by a comma Two ordered pairs x y and u v are equal if x u and y v So for example 1 5 cid 54 5 1 The Cartesian product of two sets A and B is another set denoted A B and de ned as A B a b a A b B That is A B is the set of all ordered pairs where the rst item in the pair is a member of A and the second item in the pair is a member of B Example a b 1 2 3 a 1 a 2 a 3 b 1 b 2 b 3 Properties of Cartesian Product Observe that Cartesian products are not commutative nor associative That is generally speaking A B cid 54 B A A B C cid 54 A B C But we can de ne A B C a b c a A b B c C to be the set of ordered triples of elements from A B C Cartesian Powers In general A1 A2 An x1 x2 xn xi Ai for each i 1 2 n and An A A A x1 x2 xn x1 x2 xn A Examples 1 H T 2 H H H T T H T T 2 R2 is the Cartesian plane 3 R3 is 3 dimensional space Cardinality of Cartesian Products Observe that A B A B A1 A2 An A1 A2 An In general Example Suppose on a ight the meal options are beef sh and vegetarian and the beverage options are co ee and tea If passengers are allowed to pick exactly one meal option and exactly one beverage option how many possible combinations are there Answer Let M b f v be the set of meal options and let B c t be the sets of beverage options Then the set of possible combinations is M B b c b t f c f t v c v t and the number of combinations is M B M B 3 2 6 Multiplication Rule of Counting The Multiplication Rule of Counting Suppose in making a list of length k there are n1 possible choices for the rst entry n2 possible choices for the second entry n3 possible choices for the third entry and so on Then the total number of di erent lists that can be made this way is the product n1 n2 n3 nk Applications of Multiplication Rule 1 A restaurant o ers a 3 course meal where there are 4 options for the rst course 5 for the second course and 3 options for the 3rd course How many di erent meals are possible the set 0 1 9 2 1 How many di erent license plates are possible 2 2 How many di erent license plates are possible without any 2 The license plate of a car is a sequence of 6 digits each from repeated digits 2 3 How many di erent license plates are possible which contain the digit 3 and have no repeated digits 2 4 How many license plates are there where consecutive digits are 3 In how many possible ways can we rearrange the letters of the distinct word THEORY