1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 16Milos [email protected] Sennott SquareCountingM. HauskrechtCS 441 Discrete mathematics for CSCourse administrationMidterm exam:• Thursday, March 6, 2014Homework assignment 8: • due after Spring break• An opportunity to practice mathematical induction, and basic counting for the midtermCourse web page:http://www.cs.pitt.edu/~milos/courses/cs441/2M. HauskrechtCS 441 Discrete mathematics for CSCounting• Assume we have a set of objects with certain properties• Counting is used to determine the number of these objectsExamples:• Number of available phone numbers with 7 digits in the local calling area• Number of possible match starters (football, basketball) given the number of team members and their positionsM. HauskrechtCS 441 Discrete mathematics for CSBasic counting rules• Counting problems may be very hard, not obvious• Solution: – simplify the solution by decomposing the problem• Two basic decomposition rules:– Product rule• A count decomposes into a sequence of dependent counts (“each element in the first count is associated with all elements of the second count”)– Sum rule• A count decomposes into a set of independent counts (“elements of counts are alternatives”)3M. HauskrechtCS 441 Discrete mathematics for CSProduct ruleA count can be broken down into a sequence of dependent counts • “each element in the first count is associated with all elements of the second count”Example:• Assume an auditorium with a seat labeled by a letter and numbers in between 1 to 50 (e.g. A23). We want the total number of seats in the auditorium. • 26 letters and 50 numbers• How to count? • One solution: write down all seats (objects) and count themA-1 A-2 A-3 …A-50 B-1… Z-49 Z-501 2 3 50 51 … (n-1) n  eventually we get itM. HauskrechtCS 441 Discrete mathematics for CSProduct ruleA count can be broken down into a sequence of dependent counts • “each element in the first count is associated with all elements of the second count”Example:• assume an auditorium with a seat labeled by a letter and numbers in between 1 to 50 (e.g. A23). We want the total number of seats in the auditorium. • 26 letters and 50 numbers• A better solution?• For each letter there are 50 numbers• So the number of seats is 26*50 = 1300• Product rule: number of letters * number of integers in [1,50]4M. HauskrechtCS 441 Discrete mathematics for CSProduct ruleA count can be broken down into a sequence of dependent counts • “each element in the first count is associated with all elements of the second count”• Product rule: If a count of elements can be broken down into a sequence of dependent counts where the first count yields n1elements, the second n2 elements, and kth count nk elements, by the product rule the total number of elements is:• n = n1*n2* …* nkM. HauskrechtCS 441 Discrete mathematics for CSProduct ruleExample:• How many different bit strings of length 7 are there?• E.g. 1011010 • Is it possible to decompose the count problem and if yes how?Yes.• Count the number of possible assignments to bit 1• For the first bit assignment (say 0) count assignments to bit 2or010001orTotal assignments to first 2 bits: 2*2=45M. HauskrechtCS 441 Discrete mathematics for CSProduct ruleExample:• How many different bit strings of length 7 are there?• E.g. 1011010 • Is it possible to decompose the count problem and if yes how?• Yes.– Count the number of possible assignments to bit 1– For the specific first bit count possible assignments to bit 2– For the specific first two bits count assignments to bit 3– Number of assignments to the first 3 bits: 2*2*2=8M. HauskrechtCS 441 Discrete mathematics for CSProduct ruleExample:• How many different bit strings of length 7 are there?• E.g. 1011010 • Is it possible to decompose the count problem and if yes how?• Yes.– Count the number of possible assignments to bit 1– For the specific first bit count possible assignments to bit 2– For the specific first two bits count assignments to bit 3– Gives a sequence of n dependent counts and by the product rule we have:n = 2* 2 * 2 * 2 * 2 * 2 *2 = 276M. HauskrechtCS 441 Discrete mathematics for CSProduct ruleExample:The number of subsets of a set S with k elements.• How to count them? • Hint: think in terms of bitstring representation of a set?• Assume each element in S is assigned a bit position.• If A is a subset it can be encoded as a bitstring: if an element is in A then use 1 else put 0• How many different bitstrings are there?– n = 2* 2* …2 = 2kk bitsM. HauskrechtCS 441 Discrete mathematics for CSSum ruleA count decomposes into a set of independent counts• “elements of counts are alternatives”, they do not depend on each otherExample:• You need to travel in between city A and B. You can either fly, take a train, or a bus. There are 12 different flights in between A and B, 5 different trains and 10 buses. How many options do you have to get from A to B? • We can take only one type of transportation and for each only one option. The number of options:• n = 12+5+10Sum rule:• n = number of flights + number of trains + number of buses7M. HauskrechtCS 441 Discrete mathematics for CSSum ruleA count decomposes into a set of independent counts• “elements of counts are alternatives”• Sum rule: If a count of elements can be broken down into a set of independent counts where the first count yields n1 elements, the second n2 elements, and kth count nk elements, by the sum rule the total number of elements is:• n = n1+n2+ …+ nkM. HauskrechtCS 441 Discrete mathematics for CSBeyond basic counting rules• More complex counting problems typically require a combination of the sum and product rules. Example: A login password:• The minimum password length is 6 and the maximum is 8. The password can consist of either an uppercase letter or a digit. There must be at least one digit in the password. • How many different passwords are there?8M. HauskrechtCS 441 Discrete mathematics for CSBeyond basic counting rulesExample: A password for the login name. • The minimum password length is 6 and the maximum is 8. The password can consist of either an uppercase letter or a digit. There must be at least one digit in the password. • How to compute