6.041 / 6.431 4. Counting

LECTURE 4 • Readings: Section 1.6 Lecture outline • Principles of counting • Many examples – permutations – k-permutations – combinations – partitions • Binomial probabilities Discrete uniform law • Let all sample points be equally likely • Then, P(A)= number of elements of A total number of sample points = |A| |!| • Just count... Basic counting principle • r stages • ni choices at stage i • Number of choices is: n1n2 ···nr • Number of license plates with 3 letters and 4 digits = • ... if repetition is prohibited = • Permutations: Number of ways of ordering n elements is: • Number of subsets of {1,...,n} = Example • Probability that six rolls of a six-sided die all give different numbers? – Number of outcomes that make the event happen: – Number of elements in the sample space: – Answer: Combinations Binomial probabilities !n": number of k-element subsets • k • n independent coin tosses of a given n-element set – P(H)= p • Two ways of constructing an ordered sequence of k distinct items: • P(HTTHHH)= – Choose the k items one at a time: n! n(n−1) ···(n−k+1)= (n − k)! choices P(sequence) = p# heads(1 − p)# tails • – Choose k items, then order them(k! possible orders)P(k heads) = # P(seq.) • Hence: k−head seq. !n" k!= n! k ·(n − k)! =(# of k−head seqs.) pk(1 − p)n−k ·!nk " = k!(nn− ! k)! = !nk " pk(1 − p)n−k n#!n" = kk=0 Coin tossing problem Partitions • event B: 3 out of 10 tosses were “heads”. • 52-card deck, dealt to 4 players – Given that B occurred, • Find P(each gets an ace) what is the (conditional) probability that the first 2 tosses were heads? Outcome: a partition of the 52 cards • – number of outcomes: All outcomes in set B are equally likely: • 52! probability p3(1 − p)7 13! 13! 13! 13! – Conditional probability law is uniform Count number of ways of distributing the • four aces: 4 3 2· ·Number of outcomes in B:• • Count number of ways of dealing the • Out of the outcomes in B, remaining 48 cards how many start with HH? 48! 12! 12! 12! 12! Answer: • 48! 4 32··12! 12! 12! 12! 52! 13! 13! 13! 13! MIT OpenCourseWare http://ocw.mit.edu 6.041 /6.431 Probabilistic Systems Analysis and Applied Probability Fall 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.