CMSC 250 Discrete StructuresCounting Elements in a ListProve: # elements in listHow many in list divisible by somethingProbability likelihood of a specific eventFlipping Two CoinsStandard Playing CardsRolling Two Six-Sided DiceMulti-level ProbabilityCombination ExamplesMultiplication RuleTournament PlayWhat if A wins 2 of every 3 games?Permutation ExampleSlide 15Slide 16ExamplesSlide 18Probabilities with PINsSlide 20Difference Rule FormallyPINs with less specified length Addition RuleAddition Rule FormallyAnother example for Multiplication Rule and Addition RuleWhere Multiplication Rule Doesn’t WorkSlide 26Inclusion/Exclusion RuleInclusion/Exclusion ExampleSlide 29Slide 30FactorialComputing CombinationsPermutationsTheater SeatingSlide 35r-PermutationsCombinationsCombinations ExampleHarder Examples selecting “class representatives”Different Types of MembersStudent Council (Counting Subsets of a Set)Slide 42Combinations with RepetitionSlide 44r-Combinations w/ RepetitionsPermutation w/ Repeated ElementsPermutations w/ Repeated ElementsPermutations but of indistinguishable itemsCombinations with RepititionCombinations w/ Repetition ExampleSlide 51Probability with CombinationsProperties of r-Permutations and proofs of those propertiesProperties of Combinations (Can you prove this?)Pascal’s TriangleBinomial TheoremConditional ProbabilityCMSC 250Discrete StructuresCountingJanuary 14, 2019 Counting 2Counting Elements in a ListHow 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 3Prove: # elements in listBase case (List of size 1, x=y)–y – x + 1 = y – y + 1 (by substitution) = 1IH (generic x, y=k [where x k])–Assume size of list x to k, is k – x + 1IS–Show size of list x to k + 1, is (k + 1) – x + 1–ProveSplit into two lists …January 14, 2019 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 = 180January 14, 2019 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 January 14, 2019 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 differJanuary 14, 2019 Counting 7Standard Playing CardsValues: 2,3,4,5,6,7,8,9,10,J,Q,K,ASuits: D(), H( ), S(), C()Probability of drawing the Ace of SpadesProbability of drawing a SpadeProbability of drawing a face cardProbability of drawing a red face cardJanuary 14, 2019 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?January 14, 2019 Counting 9Multi-level ProbabilityIf 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 5212121212121525January 14, 2019 Counting 10Combination ExamplesBreakfast–Main–FruitRed, White, Blue marbles–How can you arrange 10 of them–__ __ __ __ __ __ __ __ __ __–3 3 3 3 3 3 3 3 3 3 = 310January 14, 2019 Counting 11Multiplication Rule1st step can be performed n1 ways2nd step can be performed n2 ways…Kth step can be performed nk waysOperation 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) = 24January 14, 2019 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?January 14, 2019 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?January 14, 2019 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!January 14, 2019 Counting 15Permutation ExampleHow many ways to rewrite CAT?3! = 6cat, cta, act, atc, tca, tacJanuary 14, 2019 Counting 16Multiplication RuleIf there are n steps to a decision, each step having c(k) choices, the total number of choices is:niic1)(January 14, 2019 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 34January 14, 2019 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,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,680January 14, 2019 Counting 19Probabilities with PINsNumber of 4 digit
View Full Document
Unlocking...