CSE115 ENGR160 Discrete Mathematics 04 14 11 Ming Hsuan Yang UC Merced 1 5 1 Basics of counting Combinatorics they study of arrangements of objects Enumeration the counting of objects with certain properties Enumerate the different telephone numbers possible in US The allowable password on a computer The different orders in which runners in a race can reach 2 Example Suppose a password on a system consists of 6 7 or 8 characters Each of these characters must be a digit or a letter of the alphabet Each password must contain at least one digit How many passwords are there 3 Basic counting principles Two basic counting principles Product rule Sum rule Product rule suppose that a procedure can be broken down into a sequence of two tasks If there are n1 ways to do the 1st task and each of these there are n2 ways to do the 2nd task then there are n1 n2 ways to do the procedure 4 Example The chairs of a room to be labeled with a letter and a positive integer not exceeding 100 What is the largest number of chairs that can be labeled differently There are 26 letters to assign for the 1st part and 100 possible integers to assign for the 2nd part so there are 26 100 2600 different ways to label chairs 5 Product rule Suppose that a procedure is carried out by performing the tasks T1 T2 Tm in sequence If each task Ti i 1 2 n can be done in ni ways regardless of how the previous tasks were done then there are n1 n2 nm ways to carry out the procedure 6 Example How many different license plates are available if each plate contains a sequence of 3 letters followed by 3 digits and non sequences of letters are prohibited even if they are obscene License plate There are 26 choices for each letter and 10 choices for each digit So there are 26 26 26 10 10 10 17 576 000 possible license plates 7 Counting functions How many functions are there from a set with m elements to a set with n elements A function corresponds to one of the n elements in the codomain for each of the m elements in the domain Hence by product rule there are n n n nm functions from a set with m elements to one with n elements 8 Counting one to one functions How many one to one functions are there from a set with m elements to one with n elements First note that when m n there are no one to one functions from a set with m elements to one with n elements Let m n Suppose the elements in the domain are a1 a2 am There are n ways to choose the value for the value at a1 As the function is one to one the value of the function at a2 can be picked in n 1 ways the value used for a1 cannot be used again Using the product rule there are n n 1 n 2 n m 1 one to one functions from a set with m elements to one with n elements 9 Example From a set with 3 elements to one with 5 elements there are 5 4 3 60 one toone functions 10 Example The format of telephone numbers in north America is specified by a numbering plan It consists of 10 digits with 3 digit area code 3 digit office code and 4 digit station code Each digit can take one form of X 0 1 9 N 2 3 9 Y 0 1 11 Example In the old plan the formats for area code office code and station code are NYX NNX and XXXX respectively So the phone numbers had NYX NNX XXXX NYX 8 2 10 160 area codes NNX 8 8 10 640 office codes XXXX 10 10 10 10 10 000 station codes So there are 160 640 10 000 1 024 000 000 phone numbers 12 Example In the new plan the formats for area code office code and station code are NXX NXX and XXXX respectively So the phone numbers had NXX NXX XXXX NXX 8 10 10 800 area codes NXX 8 10 10 800 office codes XXXX 10 10 10 10 10 000 station codes So there are 800 800 10 000 6 400 000 000 phone numbers 13 Product rule If A1 A2 Am are finite sets then the number of elements in the Cartesian product of these sets is the product of the number of elements in each set A1 A2 Am A1 A2 Am 14 Sum rule If a task can be done either in one of n1 ways or in one of n2 ways where none of the set of n1 ways is the same as any of the set of n2 ways then there are n1 n2 ways to do the task Example suppose either a member of faculty or a student in CSE is chosen as a representative to a university committee How many different choices are there for this representative if there are 8 members in faculty and 200 students There are 8 200 208 ways to pick this representative 15 Sum rule If A1 A2 Am are disjoint finite sets then the number of elements in the union of these sets is as follows A1 A2 Am A1 A2 Am 16 More complex counting problems In a version of the BASIC programming language the name of a variable is a string of 1 or 2 alphanumeric characters where uppercase and lowercase letters are not distinguished Moreover a variable name must begin with a letter and must be different from the five strings of two characters that are reserved for programming use How many different variables names are there Let V1 be the number of these variables of 1 character and likewise V2 for variables of 2 characters So V1 26 and V2 26 36 5 931 In total there are 26 931 957 different variables 17 Example Each user on a computer system has a password which is 6 to 8 characters long where each character is an uppercase letter or a digit Each password must contain at least one digit How many possible passwords are there Let P be the number of all possible passwords and P P6 P7 P8 where Pi is a password of i characters P6 366 266 1 867 866 560 P7 367 267 70 332 353 920 P8 368 268 208 827 064 576 P P6 P7 P8 2 684 483 063 360 18 Example Internet address Internet protocol IPv4 Class A largest network Class B medium sized networks Class C smallest networks Class D multicast not assigned for IP address Class E future use Some are reserved netid 1111111 hostid all 1 s and 0 s How may different IPv4 addresses are available 19 Example Internet address Let the total number of address be x and x xA xB xC Class A there are 27 1 127 netids 1111111 is reserved For each netid there are 2242 16 …