CMSC 250Discrete StructuresCounting12 July 2007 Counting 2Counting 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?12 July 2007 Counting 3Prove: # 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 …12 July 2007 Counting 4How many in list divisible by somethingHow many positive three digit integers are there?–(this means only the ones that require 3 digits)–999 –100 + 1 = 900How many three digit integers are divisible by 5?–think about the definition of divisible byx | y ↔ ∃ k ∈Z, y = kx and then count the k’s that work100, 101, 102, 103, 104, 105, 106,… 994, 995, 996, 997, 998, 99920*5 21*5 … 199*5–count the integers between 20 and 199–199 –20 + 1 = 18012 July 2007 Counting 5Probabilitylikelihood of a specific eventSample Space = set of all possible outcomesRandom = outcome of trial is unknownEvent = subset of sample spaceEqual 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:)()()(SnEnEP =12 July 2007 Counting 6Flipping Two CoinsSample 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 coinsCompute the above probabilitiesIf flip two coins 100 times will you get 25-50-25?–Probability & actual outcomes often differ12 July 2007 Counting 7Standard 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 card12 July 2007 Counting 8Rolling Two Six-Sided DiceSample 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?12 July 2007 Counting 9Multi-level Probability If I toss a coin once – the probability of Head = ½ If I toss that coin 5 times – The probability of all heads – The probability of exactly 4 heads 5212121212121=⋅⋅⋅⋅52512 July 2007 Counting 10Combination 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 = 31012 July 2007 Counting 11Multiplication Rule1ststep can be performed n1ways2ndstep can be performed n2ways…Kthstep can be performed nkwaysOperation can be performed n1* n2 *…* nkways Cartesian product n(A)=3, n(B)=2, n(C)=4–n(AxBxC) = 24–n(AxB) = 6, n((AxB)xC) = 2412 July 2007 Counting 12Tournament PlayTeam A and Team B in “Best of 3” TournamentWhere 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?12 July 2007 Counting 13What 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/3How likely is A to win the tournament?How likely is B to win the tournament?12 July 2007 Counting 14Permutation ExampleHow many ways to take a picture?– With 1 person?– With 2 people?– With 3 people?– With 4 people?– With 5 people?Number of ways to arrange n objects– n!– 10n< n!12 July 2007 Counting 15Permutation Example How many ways to rewrite CAT? 3! = 6 cat, cta, act, atc, tca, tac12 July 2007 Counting 16Multiplication Rule If there are n steps to a decision, each step having c(k) choices, the total number of choices is:∏=niic1)(12 July 2007 Counting 17ExamplesChoose 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 ⋅10Choose a 3-value PIN of digits and letters= 36 ⋅36 ⋅36– Without repeats= 36 ⋅35⋅3412 July 2007 Counting 18Permutation ExampleHexadecimal 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,504How 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,68012 July 2007 Counting 19Probabilities 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 eventP(E’) = P(Ec) = 1 – P(E)12 July 2007 Counting 20Permutation ExampleConsider 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 nis 4n– No two adjacent = 4 ⋅3⋅3⋅3 = 4 ⋅3n-1– So 4n– 4 ⋅3n-1What is the probability that a random string of length 10 contains at least one pair of adjacent characters that are the same?%5.924314344910910≅−=⋅−=12 July 2007 Counting 21Difference Rule Formally If A is a finite set and B⊆A, thenn(A – B) = n(A) – n(B) One application:probability of the complement of an eventP(E’) = P(Ec) = 1 - P(E)12 July 2007 Counting 22PINs with less specified lengthAddition 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 of 3 length PINs w/rep allowed: 4 ⋅4 ⋅4 = 64–Number of 4 length PINs w/rep allowed: 4 ⋅4 ⋅4 ⋅4 = 256Number PINs if allowing length of 2, 3 or 4 = 33612 July 2007 Counting 23Addition Rule Formally If A1∪ A2∪ A3∪ … ∪ Ak=Aand A1, A2,
View Full Document
Unlocking...