STAT 3 Combinatorics PDF

STAT 3 Chapter 1 Lesson 4 Combinatorics Rosarie Gillera - Sanchez  Combinatorics Many times, a person must know the number of all possible outcomes for a sequence of events (sample space). To determine this number, there are rules that can b...

STAT 3 Chapter 1 Lesson 4 Combinatorics Rosarie Gillera - Sanchez  Combinatorics Many times, a person must know the number of all possible outcomes for a sequence of events (sample space). To determine this number, there are rules that can be used: 1. Tree Diagram 2. Fundamental Counting Principle 3. Permutations 4. Combinations Rosarie G. Sanchez - Instructor Tree Diagram A tree diagram is a diagram consisting of branches corresponding to the outcomes of two or more probability experiments that are done in sequence. When constructing a tree diagram, use branches emanating from a single point to show the outcomes for the first experiment, and then show the outcomes for the second experiment using branches emanating from each branch that was used for the first experiment, etc. Rosarie G. Sanchez - Instructor  Using a Tree Diagram to Find a Sample Space Example #1: Use a tree diagram to find the sample space for the genders of three children in a family. SOLUTION: There are two possibilities for the first child, boy or girl, two for the second, boy or girl, and two for the third, boy or girl. So the tree diagram can be drawn as shown below. Rosarie G. Sanchez - Instructor After a tree diagram is drawn, the outcomes can be found by tracing through all of the branches. In this case, the sample space would be {BBB, BBG, BGB, BGG, GBB, GBG, GGB, GGG}. Rosarie G. Sanchez - Instructor  Computing a Probability Example #2: If a family has three children, find the probability that they have at least one boy and one girl. (Assume that each child is equally likely to be a boy or girl.) SOLUTION: The sample space we found in Example 2 has eight outcomes, and only two of them have three kids with the same gender. So six of the eight outcomes have at least one boy and one girl, making the probability 𝟔 𝟑 = 𝟖 𝟒 Rosarie G. Sanchez - Instructor  Using a Tree Diagram to Compute Probabilities Example #3: A coin is flipped, and then a die is rolled. Use a tree diagram to find the probability of getting head on the coin and an even number on the die. SOLUTION: First, we’ll use a tree diagram to find the sample space. The coin will land on either heads or tails, and there are six outcomes for the die: 1, 2, 3, 4, 5, or 6. The total number of outcomes for the experiment is 12. The number of ways to get a head on the coin and an even number on the die is 3: H2, H4, or H6. So, the probability of getting a head and an even number when a coin is tossed and a die is rolled is 𝟑 𝟏 = 𝟏𝟐 𝟒 𝟏 𝟑 𝟑 𝟏 𝑷 𝑯 𝒂𝒏𝒅 𝒆𝒗𝒆𝒏 𝒏𝒖𝒎𝒃𝒆𝒓 = 𝒙 = = 𝟐 𝟔 𝟏𝟐 𝟒 Rosarie G. Sanchez - Instructor Tables Another way of determining a sample space is by making a table. Example: Consider the sample space of selecting a card from a standard deck of 52 cards. (The cards are assumed to be shuffled to make sure that the selection occurs at random.) SOLUTION: There are four suits - hearts, diamonds, spades, and clubs, and 13 cards of each suit consisting of the denominations ace (A), 2, 3, 4, 5, 6, 7, 8, 9, 10, and 3 picture or face cards - jack (J), queen (Q), and king (K). Rosarie G. Sanchez - Instructor The Fundamental Counting Principle In a sequence of n events in which the first one has 𝒌𝟏 possibilities and the second event has 𝒌𝟐 and the third has 𝒌𝟑 , and so forth, the total number of possibilities of the sequence will be 𝒌𝟏 𝒌𝟐 𝒌𝟑 𝒌𝒏 Note: In this case, we need to multiply all the possibilities or choices. Rosarie G. Sanchez - Instructor Example #1: If you buy two pairs of pants, four shirts, and two pairs of shoes, how many new outfits consisting of a new pair of pants, one shirt, and one pair of shoes would you have? SOLUTION: pants shirt shoes No. of ways 2 4 2 16 Rosarie G. Sanchez - Instructor Example #2: A die is rolled and a coin is tossed. Determine the number of different possible outcomes. SOLUTION: die coin No. of ways 6 2 12 Rosarie G. Sanchez - Instructor Example #3: How many possible outcomes are there if a coin is tossed thrice. SOLUTION: 1st toss 2nd toss 3rd toss No. of outcomes 2 2 2 8 Rosarie G. Sanchez - Instructor Example #4: In how many ways can the 1st, 2nd, and 3rd prizes be awarded in a Singing Contest with 10 contestants? SOLUTION: 1st prize 2nd prize 3rd prize No. of ways 10 9 8 720 Rosarie G. Sanchez - Instructor Example #5: The canteen offers following: A) Main courses: Menudo, Adobo, Sinigang, Tinolang Manok B) Desserts: Salad, Leche Flan, Ice Cream C) Drinks: Soda, Water, Coffee, Frappe How many meal combos are possible (1 from a, 1 from b, and 1 from c)? SOLUTION: A B C No. of combos 4 3 4 48 Rosarie G. Sanchez - Instructor Example #6: Three cards are drawn in succession and without replacement from a deck of 52 cards. Find the total number of ways in which the three cards can be dealt. SOLUTION: 1st card 2nd card 3rd card No. of ways 52 51 50 132,600 Rosarie G. Sanchez - Instructor  Permutations & Combinations Factorial Notation For any counting n: 𝒏! = 𝒏 𝒏 − 𝟏 𝒏 − 𝟐 … 𝟏 Examples: 5! (read as 5 factorial) = 5 · 4 · 3 · 2 · 1 9! (read as 9 factorial) = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 0! (read as 0 factorial) = 1. Factorial notation is being used in finding the permutations and combinations. ❖ Permutations are understood as arrangements and combinations are understood as selections. Rosarie G. Sanchez - Instructor Permutation Permutation is an arrangement of the group of things in a definite order. In this rule of counting, arrangement or order of things is very important. This rule helps us arrange 𝒏 distinct object, taking 𝒓 of them at a time. That is When taken all at once, Rosarie G. Sanchez - Instructor Example #1: In how many ways five books (Math, English, Filipino, Biology and Physics) be arranged on a shelf? SOLUTION: Using 𝒏𝑷𝒏 with 𝒏 = 𝟓, we have Rosarie G. Sanchez - Instructor Example #2: In how many ways may we arrange, a, b, c all at a time without repetition? SOLUTION: Rosarie G. Sanchez - Instructor Example #3: In how many ways can 7 people sit if there are only 3 vacant chairs available? SOLUTION: Rosarie G. Sanchez - Instructor Example #4: In how many ways may we arrange, a, b, and c, two at a time? SOLUTION: Rosarie G. Sanchez - Instructor Permutation of 𝒏 Object Some are Alike We have considered so far the permutation of n distinct objects. However, there are times that the objects that we are dealing with are alike or identical. In this case, the number of permutations are reduced depending on the number of identical elements. To deal with this kind of problem, we will have a new formula: where 𝑛 = 𝒏𝟏 + 𝒏𝟐 + 𝒏𝟑 +... + 𝒏𝒌 and 𝒏𝟏 , 𝒏𝟐 , … 𝒏𝒌 refers to the number of times each item is repeated (or the repeated items) Rosarie G. Sanchez - Instructor Example #5: How many ways can we arrange the letters of the word DEED? SOLUTION: In this case, there are 4 letters taken 4 at a time. But there are 2 letter D and 2 letter E. Rosarie G. Sanchez - Instructor To illustrate the 6 different ways, these are the possible permutations Rosarie G. Sanchez - Instructor Example #6: In how many ways may we arrange the letters of the word CHURCH? SOLUTION: Rosarie G. Sanchez - Instructor Example #7: How many ways can you arrange the letters of the word KASUBAY if we can take only 3 letters at time? SOLUTION: KASUBAY has a total of 7 letters in which letter A occur twice. Rosarie G. Sanchez - Instructor Example #7: In how many ways may we arrange two girls and two boys in a row of four seats? SOLUTION: Rosarie G. Sanchez - Instructor Circular Permutation Arranging different objects in a circular formation or manner is called circular permutation. In a circular permutation, the permutation in Figure A and Figure B cannot be considered as different permutations if the dots are just moved in clockwise direction. Therefore, we have to fix one dot and permute the other remaining dots. Thus, the number of the formula for circular permutation is (𝒏 − 𝟏)!. Rosarie G. Sanchez - Instructor  Suppose, three dots labelled as A, B and C will be arranged on a circle. How many ways we can do it? Based on the formula for circular permutation: To illustrate the 2 permutations, we have to fix one dot. In this case, the dot is labelled as A. Rosarie G. Sanchez - Instructor Combination Combination is also deals with the arrangement of orders with no particular order. In combination, letters ABC, ACB, BAC, BCA, CAB and CBA is counted as 1 combination of letters A, B and C. The formula for combination is given as Rosarie G. Sanchez - Instructor Example #1: Suppose there are 4 letters A, B, C and D. How many combinations of these letters if can only take 2 letters at a time? By using the formula, 𝑛 = 4 and 𝑟 = 2. SOLUTION: Plugging in the formula we got These 6 combinations are AB, AC, AD, BC, BD, CD. There are no more combinations aside from these six given. Rosarie G. Sanchez - Instructor Example #2: In how many ways may a class of ten students select three representatives for that class? SOLUTION: Rosarie G. Sanchez - Instructor Example #3: In how many ways can a committee of 3 members be chosen from a group with 6 members? SOLUTION: Rosarie G. Sanchez - Instructor Example #4: In how many ways can we select a group of 3 men and 2 women out of 6 men and 4 women? To do this, we have to multiply the number of combinations of men and women. SOLUTION: No. of ways = combinations of men x combinations of women Rosarie G. Sanchez - Instructor