1!Combinatorial Analysis !1!Combinatorial analysis"Stat 100A-Intro Probability "Juana Sanchez"UCLA Dept of Statistics "[email protected] !Counting methods!http://www.mediacy.com/index.aspx?page=SS_InsectSurvey!You need these counting techniques in the special case in !which the outcomes of the sample space are equally likely, !so we study them separately before we apply them. !Then, in a separate lecture, we apply them to compute !probabilities. You may find more material in Ch. 1 of Ross.!Today "Ref. reading: Chapter 1 Ross, Chapter 2, section 2.5 13.6.27! Combinatorial Analysis !2!1. Introduction. Fundamental Rule of Counting "2. Ordering n objects when some are indistinguishable " from each other "3. Ordering r objects selected from n distinguishable " objects "4. Combinations, permutations of r objects taken from n " objects when objects are indistinguishable"5. Allocating n objects to r groups. 12.10.5! Combinatorial Analysis !Stat 100A Intro Probability/Sanchez!3!1. Introduction. Fundamental rule of counting ! In his “Art Conjectanding,” Bernoulli described combinatorics as the art of enumerating all the possible ways in which a given number of objects may be mixed and combined so as to be sure of not missing any possible result. !2!Counting is used to find probabilities when we have sample spaces with equally likely outcomes Example: Suppose there are 40 people in a group (25 women and 15 men). We must select a random sample of 7 people at random. What is the probability that the sample contains 4 women and 3 men? !Let A be event 4 women and 3 men.!(Because outcomes in S equally likely_!13.6.27! Combinatorial Analysis !4! P(A) =# outcomesin the eventTotal # of outcomes inS=254⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 153⎛ ⎝ ⎜ ⎞ ⎠ ⎟ 407⎛ ⎝ ⎜ ⎞ ⎠ ⎟ =12650 × 45518643560=575575018643560= 0.3087Example If there are 12 strangers in a room, what is the probability that no two of them celebrate their birthday in the same month?!Let A be event “all different birthmonth”!13.6.27! Combinatorial Analysis !5! P(A) =# outcomes in A# outcomes in S=12!1212See if we can do this at the end of the lecture today • There are 20 men and 30 women in a concert. 5 of these people are randomly chosen to take part in a discussion. What is the probability that at least one woman is chosen? !Combinatorial Analysis !6!3!..and this An instructor gives her class a set of 20 problems with the information that the final exam will consist of a random selection of 10 of them. If a student has figured out how to do 15 of the problems, what is the probability that he or she will answer correctly !(a) All 10 problems !(b) At least 8 of the problems!June 27, 2013 ! Combinatorial Analysis !7!13.6.27! Combinatorial Analysis !8!Fundamental rule of counting! A number of multiple tasks are to be made to achieve one goal. There are m1 ways to do the first task, m2 ways to do the second, m3 for the third etc. If these choices can be combined freely, the total number of possibilities for the whole set of choices is equal to ! m1x m2 x m3…….. !13.6.27! Combinatorial Analysis !9!Example 1! If a man has three shirts and 2 ties, in how many ways can he dress up (put on one of each)? !There are two tasks involved in this problem, 2 and 3 !Should we add: 2+3? or multiply: 2x3? Or perhaps make: 23 or 32!4!13.6.27! Combinatorial Analysis !10!You can start by !• Numbering the shirts: 1, 2, 3!• Numbering the ties: 1,2 !• And then… !Combinatorial Analysis !11!prepare the set of all ordered couples (s,t) such that s=1,2,3 and t=1,2! s!t!1! 2! 3!1! (1,1)! (2,1) ! (3,1)!2! (1,2)! (2,2)! (3,2) !Combinatorial Analysis !12!..and the answer to the question is: ! 3x2=6, because the set of ordered pairs has 6 members: (1,1), (1,2), (2,1), (2,2), (3,1), (3,2). !• A tree is another graphical way to visualize this ! 1 2 3 ! 1 2 1 2 1 2!5!Combinatorial Analysis !13!Example 2!• What if the man has also 2 pairs of shoes? In how many ways can he dress up now? !• Now each of the original 2-tuples splits into two 3-tuples and so the total of 3-tuples will be 3x2x2=12!13.6.27! Combinatorial Analysis !14!Example 3!• A menu in a restaurant reads like this: !Choice of one: Soup, Juice, Fruit Cocktail!Choice of one: Beef hash, Roast Ham, Fried Chicken, Spaghetti with Meatballs!Choice of one: Mashed Potatoes, Broccoli, Lima Beans!Choice of one: Ice Cream, Apple Pie!Choice of one: Coffee, Tea, Milk !13.6.27! Combinatorial Analysis !15!How many scenarios of a complete 5-course dinner can you make out of this menu? !3x4x3x2x3=216 6!13.6.27! Combinatorial Analysis !16!What if they run out of juice and fruit cocktail? !• You are no longer free to choose from the first set of choices. How many complete 5 course dinners can you make out of this menu? !1x4x3x2x3=72!13.6.27! Combinatorial Analysis !17!As we just saw in the previous example, sometimes we don’t have free choices, there are constraints; always check that.!13.6.27! Combinatorial Analysis !18!Example 5!• Consider three boys are sent to the headmaster for cheating. They have to line up in a row outside the headmaster’s room and wait for their punishment. No one wants to be first, of course! Suppose the boys are called Andrew, Burt, and Charles (A,B,C for short). How many ways can the boys be lined up? !3x2x1=3! = 6 ways, of course. !• But what if Andrew must go first? How many ordered arrangements of the children can we have then? The first is fixed. So there is only 2 left to order or 2! = 2. !7!13.6.27! Combinatorial Analysis !19!Example 7! A College planning committee consists of 3 freshmen, 4 sophomores, 5 juniors and 2 seniors. A subcommittee of 4, consisting of one person from each class is to be chosen. How many different subcommittees are possible? ! (3)(4)(5)(2) = 120 possible subcommittees. !13.6.27! Combinatorial Analysis !20!Example 8 !Ten workers are to be assigned to 10 different jobs, one to each job. How many different assignments are possible? !The first job can be assigned to 10 workers, the second to 9, the third to 8, …, the 10th to 1.!10(9)(8)(7)(6)(5)(4)(3)(2)(1)= 3628800 ways of allocating the workers to jobs. This is 10!!13.6.27! Combinatorial Analysis !21!Example 9!• How many
View Full Document
Unlocking...