CMSC 250 Discrete Structures Counting Counting Elements in a List How many integers in the list from 1 to 10 How many integers in the list from m to n assuming m n n m 1 Can you prove this January 14 2019 Counting 2 Prove elements in list Base case List of size 1 x y y x 1 y y 1 by substitution 1 IH generic x y k where x k Assume size of list x to k is k x 1 IS Show size of list x to k 1 is k 1 x 1 Prove Split into two lists January 14 2019 Counting 3 How many in list divisible by something How many positive three digit integers are there this means only the ones that require 3 digits 999 100 1 900 How many three digit integers are divisible by 5 think about the definition of divisible by x y k Z y kx and then count the k s that work 100 101 102 103 104 105 106 994 995 996 997 998 999 20 5 21 5 199 5 count the integers between 20 and 199 199 20 1 180 January 14 2019 Counting 4 Probability likelihood of a specific event Sample Space set of all possible outcomes Random outcome of trial is unknown Event subset of sample space Equal Probability Formula Given a finite sample space S where all outcomes are equally likely Select an event E from the sample space S The probability of event E from sample space S n E P E n S January 14 2019 Counting 5 Flipping Two Coins Sample Space H H H T T H T T What do the following events represent Probability of no heads Probability of at least one head Probability of same sides on the two coins Compute the above probabilities If flip two coins 100 times will you get 2550 25 Probability actual outcomes often differ January 14 2019 Counting 6 Standard Playing Cards Values 2 3 4 5 6 7 8 9 10 J Q K A Suits D H S C Probability of drawing the Ace of Spades Probability of drawing a Spade Probability of drawing a face card Probability of drawing a red face card January 14 2019 Counting 7 Rolling Two Six Sided Dice Sample Space Ordered pairs 1 1 1 2 1 3 1 4 1 5 1 6 2 1 2 2 2 3 2 4 2 5 2 6 6 1 6 2 6 3 6 4 6 5 6 6 Simplified 11 12 13 14 15 16 21 22 23 24 25 26 61 62 63 64 65 66 Set representing rolling a 10 The probability of rolling a 10 Set representing rolling a pair Probability of rolling a pair January 14 2019 Counting 8 Multi level Probability If I toss a coin once the probability of Head If I toss that coin 5 times The probability of all heads 1 1 1 1 1 1 5 2 2 2 2 2 2 The probability of exactly 4 heads 5 5 2 January 14 2019 Counting 9 Combination Examples Breakfast Main Fruit Red White Blue marbles How can you arrange 10 of them 3 3 3 3 3 3 3 3 3 3 310 January 14 2019 Counting 10 Multiplication Rule 1st step can be performed n1 ways 2nd step can be performed n2 ways Kth step can be performed nk ways Operation can be performed n1 n2 nk ways Cartesian product n A 3 n B 2 n C 4 n AxBxC 24 n AxB 6 n AxB xC 24 January 14 2019 Counting 11 Tournament Play Team A and Team B in Best of 3 Tournament Where they each have an equal likelihood of winning each game Do leaves add up to 1 Do we have to play 3 games Do A and B have an equal chance of winning January 14 2019 Counting 12 What if A wins 2 of every 3 games Each line for A must have a 2 3 Each line for B must have a 1 3 How likely is A to win the tournament How likely is B to win the tournament January 14 2019 Counting 13 Permutation Example How many ways to take a picture With With With With With 1 2 3 4 5 person people people people people Number of ways to arrange n objects n 10n n January 14 2019 Counting 14 Permutation Example How many ways to rewrite CAT 3 6 cat cta act atc tca tac January 14 2019 Counting 15 Multiplication Rule If there are n steps to a decision each step having c k choices the total number of choices is n c i i 1 January 14 2019 Counting 16 Examples Choose a PIN from a 0 1 2 3 4 A B C keyboard with PIN length 3 8 8 8 83 512 Choose a PIN of the form L where 0 1 2 9 L 0 1 2 9 10 26 10 Choose a 3 value PIN of digits and letters 36 36 36 Without repeats 36 35 34 January 14 2019 Counting 17 Permutation Example Hexadecimal numbers are made using digits 0 1 2 3 4 5 6 7 8 9 A B C D E F with subscript 16 How many 5 digit long begin with a digit 3 through B and end with a digit 5 through F 9 16 16 16 11 405 504 How many 6 digit long begin with one of 4 through D and end with a digit 2 through E 10 16 16 16 16 13 8 519 680 January 14 2019 Counting 18 Probabilities with PINs Number of 4 digit PINs of 0 1 2 With repetition allowed 4 4 4 4 256 With no repetition allowed 4 3 2 1 24 What is the probability that your 4 digit PIN has no repeated characters What is the probability that your 4 digit PIN does have repeated characters Probability of the complement of an event P E P Ec 1 P E January 14 2019 Counting 19 Permutation Example Consider strings of length n over the set a b c d How many strings contain at least one pair of adjacent characters that are the same Total number of length n is 4n No two adjacent 4 3 3 3 4 3n 1 So 4n 4 3n 1 What is the probability that a random string of length 10 contains at least one pair of 9 the same adjacent characters that are 10 9 4 4 3 1 10 4 January 14 2019 3 92 5 4 Counting 20 Difference Rule Formally If A is a finite set and B A then n A B n A n B One application probability of the complement of an event P E P Ec 1 P E January 14 2019 Counting 21 PINs with less specified length Addition Rule Assume it can be a 2 3 or 4 length PIN Partition the problem Number of 2 length PINs w rep allowed 4 4 16 Number …
View Full Document
Unlocking...