LECTURE 4• Readings: Section 1.6Lecture outline• Principles of counting• Many examples– permutations– k-permutations– combinations– partitions• Binomial probabilitiesDiscrete uniform law• Let all sample points be equally likely• Then,P(A)=number of elements of Atotal number of sample points=|A||Ω|• Just count...Basic counting principle• r stages• nichoices at stage i• Number of choices is: n1n2···nr• Number of license plateswith 3 letters and 4 digits =• ... if repetition is prohibited =• Permutations: Number of waysof ordering n elements is:• Number of subsets of {1, . . . , n} =Example• Probability that six rolls of a six-sided dieall give different numbers?– Number of outcomes thatmake the event happen:– Number of elementsin the sample space:– Answer:Combinations•!nk": number of k-element subsetsof a given n-element set• Two ways of constructing an orderedsequence of k distinct items:– Choose the k items one at a time:n(n− 1) ···(n− k+1) =n!(n − k)!choices– Choose k items, then order them(k! possible orders)• Hence:!nk"· k!=n!(n − k)!!nk"=n!k!(n − k)!n#k=0!nk"=Binomial probabilities• n independent coin tosses– P(H)=p• P(HT T HHH)=• P(sequence) = p# heads(1 − p)# tailsP(k heads) =#k−head seq.P(seq.)= (# of k−head seqs.) · pk(1 − p)n−k=!nk"pk(1 − p)n−kCoin tossing problem• event B: 3 out of 10 tosses were “heads”.– Given that B occurred,what is the (conditional) probabilitythat the first 2 tosses were heads?• All outcomes in set B are equally likely:probability p3(1 − p)7– Conditional probability law is uniform• Number of outcomes in B:• Out of the outcomes in B,how many start with HH?Partitions• 52-card deck, dealt to 4 players• Find P(each gets an ace)• Outcome: a partition of the 52 cards– number of outcomes:52!13! 13! 13! 13!• Count number of ways of distributing thefour aces: 4 · 3 · 2• Count number of ways of dealing theremaining 48 cards48!12! 12! 12! 12!• Answer:4 · 3 · 248!12! 12! 12! 12!52!13! 13! 13!
View Full Document
Unlocking...