GMAT (Subject) / Economist Prep - Combinatorics (Lesson)

<3

This lesson was created by Janaw55.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• Recognizing Combinations and Permutations Questions The number of ways of choosing or arranging items chosen from one or more sources. USE: SeBox - a box of selections.  Every item deserves its own SeBox.: 1) Draw a box with a label on top 2) "how many items can I choose from in this box?" => total number of available options  "OR" means "ADD" - add the number of options in the SeBoxes. "AND" means "Multiply" - multiply the number of options in the SeBoxes.
• Sc 1) Break down any combinations question into a series of SeBoxes one SeBox at a time for each "item". 2) For each SeBox, find the number of choices it represents. 3) Multiply / add the SeBoxes using AND/OR relationships.
• The Coen family consists of a father, a mother, two children and a dog. A photographer is about to take the family's picture. How many different arrangements (of standing in a row) does the photographer have, if it is known that the father insists on standing by his woman, as the song says 1. Treat father + mother as one objects  father/mother + 2 children + 1 dog = 4 places  4! = 24 2. "father+mother" object actually has 2! arrangements possible (father to the right of mother, or to her left), multiply the result by 2!: 4!×2! = 24×2 = 48 different family arrangements.
• Account for is a phrasal verb which means to explain or to make up. A phrasal verb is a verb that is followed by a preposition (e.g., look for, break up, consist of, turn on). Bad posture can __________ pain in the neck and shoulders.
• More than one Scenario If the problem presents several scenarios, or several separate ways to reach the desired combinations: 1) Calculate number of combinations for each scenario separately  2) Since the scenarios present an OR relationship, add the result. E.g. A restaurant offers a business lunch menu composed of a main course and a glass of wine. The main course menu presents a choice of 2 beef dishes (which can go with a glass of either red or white wine) and 2 fish dishes (which only go with white wine). How many combinations of a business lunch menu of a single main course and a single glass of wine can be ordered?
• Forbidden Choices [Total combinations  - "Forbidden" combinations] = Good combinations  1. Calculate the number of combinations involving "forbidden choices": Break down the question {number of forbidden choices} into a series of SeBoxes Choose One SeBox at a time for each "item" For each SeBox, find the number of forbidden choices in the box Multiply/add the number of choices (AND/OR) Substract  [total combinations - "forbidden" combinations] = 180 - 24 = 156 combinations.
• Combinations: What to Do with "Forbidden Choices" [Total combinations  - "Forbidden" combinations] = Good combinations 1) Calculate the total # of combinations using the regular Step-By-Step method. 2) Calculate the total # of forbidden combinations using the same method. Remember to include the other sources (the ones without forbidden choices in them) as well. 3) Subtract the # of forbidden combinations from the total # of combinations to find the # of good combinations.
• Choosing from a Single Source with repetition. A company has installed a combination lock on its front door. The lock requires a 4-digit passkey. The company's paranoid security officer has decided to change the passkey every day. In how many days will he run out of new passkeys? 1. How many SEBoxes? = 4; one for each Digit 2. A single digit can be anything between 0-9 => "10 options" 3. With repetition, the SeBoxes remain the same (k) a single source, with repetition: nk
• How many three-digit numbers that do not contain the digit 2 are there? A three-digit number requires three SeBoxes. 8 AND 9 AND 9  Since the problem asks for NUMBERS, the first digit cannot be 0, and therefore has only 8 options. 648 options
• In the Land of Oz, only one- or two-letter words are used. The local language has 66 different letters. The parliament decided to forbid the use of the seventh letter. How many words have the people of Oz lost because of the prohibition? The lost words are the difference between the number of words before and after the prohibition: --> (66+662)–(65+652) = 66–65+(662–652) = 1+(662–652) Expand the second part using Recycled Quadratic III: a2–b2 = (a–b)(a+b): --> 662–652 = (66–65)(66+65) = 1×131 = 131 Thus, the total number of forbidden words is --> 1+(662–652) = 1+131 = 132
• 1st digit: even 1st digit: even, no 0 ---> 4 options: 2, 4, 6, or 8
• 3rd digit: even 3rd digit: even ---> 5 options: 0, 2, 4, 6, or 8 (remember, zero is even).
• Permutations formula P (n,k) = n! / (n-k)!
• Identifying Permutations problems Choose number of ways to choose k items out of a single source of n possible items, under the following conditions: 1) without repetition 2) the order of choice matters => question will introduce "titles": 1st, 2nd 3rd, Gold, Silver, Bronze President, VP, CFO. A BC and BAC are considered two different orderings. Solve by: 1) Set up the problem: draw k SeBoxes, one for each "title". 2) Find the number of possible items to choose from for each "title", one step at a time. No repetition means n, n-1, n-2,... 3) Multiply the numbers to find the total number of options. Alternative method - plug in n and k into the Permutations formula
• M and N are among the 5 runners in a race, and there can be no tie. How many possible results are there where M is ahead of N? 5 ahead / behind  1. 5! = 120 ways of ordering 5 runners. 2. if there is no possibility for a tie, in how many of these 120 arrangements is M ahead of N?  no possibility of a tie M will be either ahead or behind N. Intuitively, there is no real reason why there would be more results with M ahead of N than behind. There are 5! = 120 ways of ordering 5 runners, and half of that is simply 120/2=60.
• A photographer is to take group photographs of a class of students for the school magazine such that each photograph should have five students. If there are four girls and four boys in the class and each photograph must not have two girls or two boys standing together, how many different photographs can the photographer take? Correct   Let's start with the photographs with girls and boys standing in the order GBGBG. Since there's no repetition, the number of options for each successive child from the same gender decreases: for example, if there are 4 choices for the first girl, there are only 3 choices for the next girl (third place), and two choices for last girl (5th place). The same goes for boys (2nd and 4th places). 4*4*3*3*2 = 288 Now, do the same for photographs with girls and boys standing in the order BGBGB. Note that intuitively, this scenario should have the same number of permutations, as we have an identical 4 boys and 4 girls to choose from. 4*4*3*3*2 = 288 Since there is an OR relationship here between either of the two types of photographs that can be taken, add the combinations. 288 + 288 = 576. Hence, this is the correct answer.
• David and Rachel are getting married. The extended family wants to have its picture taken, but David's father is unwilling to stand next to Rachel's mother. How many options does the photographer have to arrange the 10 family members in a row for the picture? There are 10! options to arrange 10 people in a row. Now, calculate the forbidden options. To do that, consider the two enemies as a single "person". There are 9! ways to arrange 9 people in a row. We're not done: since the two enemies have 2! (=2) internal arrangements between them (Father on the left, then mother, and vice versa), the number of forbidden arrangements is: 9!×2! Subtract the forbidden choice from the total number of choices to get only the good options: 10! - (9!×2)  = ? -->    10! = 10×(9×8×7×6×5×4×3×2×1) can be written as simply 10×9!: -->    10! - (9!×2)  = 10×9! - 2×9! It is then possible to extract 9! as a common factor: -->    10×9! - 2×9! = 9! × (10-2) = 9! ×8
• A class consists of 5 boys and 4 girls. Given that one kid can only hold one title, in how many ways can you pick 2 boys to be the class clown and the teacher's pet or 2 girls to be the most beautiful girl in class and the smartest kid on the block? Note: the relation in this question is "OR". For the boys, you have to pick k=2 out of n=5, where order matters: Same goes for the girls, but here we choose k=2 out of only n=4:  Now, since you have to pick 2 boys OR 2 girls, ADD the two results to get: 20+12=32
• How many options are there for license plate numbers if each license plate can include 2 digits and 3 letters (in that order), or 3 digits and 2 letters (in that order)? (Note: there are 26 letters in the alphabet) Let's start with 2 digits followed by 3 letters. There are 10 digits AND 26 letters, so the number of combinations will look like this: Now for 3 digits followed by 2 letters. There are 10 digits AND 26 letters, so the number of combinations will look like this: Since a license plate can be of the first type OR of the second type, add the combinations: --> 102×263 + 103×262 = 102×262(26+10) = 36×2602
• Combinations formula Calculating the number of ways of choosing k items out of n possible items: C (n,k) = n! / (n-k)! * k! In our case, we want to choose k=3 items out of n=8 possible items. Therefore: C(8,3) = 8! / [(8-3)!·3!] = 8! / [5!·3!] expand 8! in the numerator and 5! in the denominator and reduce: (8×7×6×5×4×3×2×1) / 5×4×3×2×1·3! = (8×7×6) / 3! = (8×7×6) / 3×2×1 = 56.
• Identifying Combinations problems: Problem requires counting the number of ways to choose k items out of a single source of n possible items, under the following conditions: 1) without repetition 2) the order of choice DOESN'T matter. The question doesn't introduce "titles" - it just asks how many ways to choose k items out of n possible items, regardless of the order of choosing. The question deals with groups, rather than with orderings.
• In a certain province in France there are 15 cities. If a single road segment connects only two cities, how many road segments are required in order to connect the cities so that each city is connected to all other cities with a single road segment? The question wants the number of roads to connect each city to all others. If the cities are A, B, C, D, etc. a road segment would be a combination of two letters: A-B, A-C, C-D, E-F, etc. The road A-B is the road leaving from A, going to B Thus, we need only two Seboxes -the first is the letter the road leaves FROM, the second is the letter the road arrives at. Does the order of choosing matter? When paving roads in France (particularly), it doesn't matter if you connect Marseilles to Lyon or Lyon to Marseilles - it's the same road! Therefore, the order of selection of each pair doesn't matter, and to compensate for that you need to divide by the number of possible internal arrangements - in this case for two cities - 2!: COMBINATONS formula
• Work Order Questions for Permutation and Combinations 1) Identify the number of sources to choose from: Are we choosing from a single source (such as children), or multiple distinct sources (such as boys and girls)? For each source: 2) Find the size of the small group that must be chosen. In other words, how many SeBoxes? Or a similar question: what is the value of k? 3) Find the size of the larger group that is chosen from: How many options can I choose from for the first SeBox? Or a similar question: what is the value of n? Fill in the rest of the SeBoxes, Step-by-Step, paying attention to: 4) Repetition: does the problem present a case With repetition (such as digits in a code, where each digit can be used more than once) - SeBox size remains the same: or n × n × n × n ×...Without repetition (such as choosing children for a hall monitor team, where each child can only be chosen once) - SeBox size changes: n × (n-1) × (n-2) ×... 5) Finally, after all SeBoxes have been filled in, comes the crucial question: Order of choice MATTERS or DOESN'T MATTER? If the order of choice matters, leave the calculation as is. In questions where the order of choice MATTERS, the chosen group must have "titles": President, Vice President, and Chairman; gold, silver, and bronze medals (in a race); etc. how many Arrangements / Orderings. If the order of choice doesn't matter, divide by k! - the number of internal arrangements of k items. Look for these words in the question: how many Combinations / Committees / Groups. Important tip: Order DOESN'T MATTER is by far the more common case in GMAT C & P questions, so when in doubt, divide by k!
• Identify Internal arrangements Questions: how many ways are there to arrange a large group composed of several sub groups in which the order doesn't matter Internal ordering Combinations questions: "how many ways are there to arrange a large group composed of several sub groups in which the order doesn't matter"  Combinations questions: "how many ways of choosing a single small group from a large group".
• Internal ordering question - Solution # arrangements = # of ways to arrange a large group / # of internal arrangements of all small groups
• There are n members in a certain department, including Michael. Two representatives are to be selected to attend a company conference. If there are 55 possible combinations in which Michael is not selected, what is the value of n? This problem presents a case of choosing from a Single source - n members. The number of choices which do not include Michael is equal to picking 2 out of n-1 (and not of n, since Michael is not in the game) with no repetition, because you cannot pick the same person twice, and no importance to order of selection, because there aren't any different roles assigned to the chosen ones.  Now that we have reduced the problem to a simple case of choosing k=2 out of n-1, without repetition, order doesn't matter, plug in the answers and use the Combinations formula C (n,k) n-1 * n-2 /k!  (n-1)(n-2) / 2 = 55
• A group of workers picked 590 apples. If each of the workers picked at least 15 apples, what is the greatest possible number of workers in that group? If you want as many workers as possible to work on a given quota, each of them has to do as little work as possible, which in this case is picking 15 apples. Now, since 590 is not divisible by 15, pick the highest multiple of 15 which is smaller than 590. It is no other than 585. --> 585/15= (600-15)/15 = 39 workers. Note that 38 workers will pick 15 apples each, and the last worker will pick the rest - 20 apples.
• A company that ships boxes to a total of 12 distribution centers uses color coding to identify each center. If either a single color or a pair of two different colors is chosen to represent each center and if each center is uniquely represented by that choice of one or two colors, what is the minimum number of colors needed for the coding? (Assume that the order of the colors in a pair does not matter) Combinations formula:     Since the question asks for the minimum number of colors needed, start by plugging Answer choice A back into the question: If there are 4 colors, there are 4 codes that have only 1 color. As for 2 color codes, pick 2 out of 4, not ordered:  So together there are 10 possible codes, which is not enough, since you need at least 12. Eliminate A, and move on to B: If there are 5 colors, there are 5 codes that have only 1 color. As for 2 color codes, pick 2 out of 5, not ordered: So together there are 15 possible codes, which is more than the 12 needed. 
• To find the number of all possible outcomes: Event A AND Event B = (Number of outcomes in A)×(Number of outcomes in B)To find the probability of event A and event B happening together:Probability (A AND B) = Probability (A) × Probability (B)
• Probability; more than 1 scenario Many GMAT probability questions will present several scenarios, or several ways (which may consist of a series of events) of reaching the desired result: 1) Calculate the probability of each scenario separately. 2) Since the scenarios are different ways of reaching the same result with an OR relationship between them - ADD the probabilities together.
• "Ice-Cold" Ice-cream factory produces only tricolor ice-cream products, where each ice-cream has three stripes of different colors. The factory uses the colors pink, purple, orange, silver, blue and red. How many different ice-cream products have at least one stripe out of the following colors: pink, purple or orange (assume that the order of the stripes in a single ice-cream does not matter)? Total number of different ice-creams: Pick 3 colors out of 6, no order, no repetition. C (6,3) = 20 OK. Now, for the forbidden choices - Those are ice-creams that do not contain the colors pink, purple or orange, and thus they contain only the three other colors - silver, blue, and red. There is only one ice-cream with those colors (it's actually picking 3 colors out of 3). And thus, 20-1 = 19 ice-creams have at least one of the wanted colors.
• In a recent street fair students were challenged to hit one of the shaded triangular regions on the large equilateral triangular board below with a ping pong ball. Each of the triangular regions is an equilateral triangle whose side is a third of the length of the large triangle board. If the ping pong ball hits and is equally likely to hit any point on the large triangular region, what is the probability of hitting a shaded triangle? The black triangles are identical to the 6 triangles of the hexagon - their angles must also be 60º (in order to supplement the hexagon's angles, 120º, and they each share a side with the hexagon's triangle. They even look the same area.)
• Bert and Ernie are among 12 tenants on Sesame Street, from which 9 tenants are to be selected for the neighborhood watch. Of the different possible selections, how many contain neither Bert nor Ernie? This problem presents a case of Single source - tenants. If Bert and Ernie are excluded, you have only 10 members to choose from, not ordered, since there aren't any different roles for the chosen. Also, there's no repetition, because you cannot pick the same person twice.  Now that we have reduced the problem to a simple case of choosing k=9 out of n=10, without repetition, order doesn't matter, use the Combinations formula C (n,k).
• What is the probability that out of the combinations that can be made using all the letters of the word EXCESS, Jerome will randomly pick a combination in which the first letter is a vowel and the last letter is a consonant? en move to the other terms:  The second through fifth letters can be anything, but since we already used two letters, there are only 4 choices left for the second letter (2 out of 6 have already been used) and then 3, 2 and 1 choices respectively for the third , fourth, and fifth letters (the number decreases with each consecutive letter, because there is no repetition).  The SeBoxes should therefore look like this:  But! Since we have 2 "E"s and 2 "S"s, this number of arrangements includes some redundant choices displacing similar letters. These double letters turn this question into an internal ordering one. The internal ordering between the two Es and the two Ss doesn't matter, so we need to divide twice by 2! so as to get rid of the redundant arrangements. Thus the good arrangements are actually:   2 * 4 * 3 * 2 * 1 = 48  good choices.  Out of how many combinations? There are 6! arrangements for 6 letters, but since there are 2 "E"s and 2 "S"s, divide twice by 2! to receive: 180 = C ( 6;2) total arrangements. Thus the percentage of good choices is 48/180.
• There are 10 books on a shelf: 5 English books, 3 Spanish books and 2 Portuguese books. What is the probability of choosing 2 books in different languages? Break the problem into a series of events — pulling the first book, then the second book. The probability of choosing 2 books in different language then depends on the language of the first book: 1) picking an English book AND picking a not-English book 2) picking an Spanish book AND picking a not-Spanish book 3) picking a Portuguese book AND picking a not-Portuguese book In questions that present several scenarios, or several ways (which may consist of a series of events) of reaching the desired result: A) Calculate the probability of each scenario separately. B) Since the scenarios are different ways of reaching the same result with an OR relationship between them, ADD the probabilities.     1) There are 5 English books out of 10 total books, so the odds of picking an English book are 5/10. There are 5 books not in English, so the odds of pulling a second book not in English are 5/9 (only 9 books in total, because one is already out after the first pick). So the probability of this scenario is: --> 5/10 × 5/9 = 25/90 2) There are 3 Spanish books out of 10 total books, so the odds of picking a Spanish book are 3/10. There are 7 books not in Spanish, so the odds of pulling a second book not in Spanish are 7/9 (only 9 books in total, because one is already out after the first pick). So the probability of this scenario is: --> 3/10 × 7/9 = 21/90 3) There are 2 Portuguese books out of 10 total books, so the odds of picking a Portuguese book are 2/10. There are 8 books not in Portuguese , so the odds of pulling a second book not in Portuguese are 8/9 (only 9 books in total, because one is already out after the first pick). So the probability of this scenario is: --> 2/10 × 8/9 = 16/90 Since there's an "OR" relationship between scenarios, add them to get the total probability: --> 25/90 + 21/90 + 16/90 = 62/90 = 31/45
• Bert and Ernie are among 12 tenants on Sesame Street, from which 9 tenants are to be selected for the neighborhood watch. Of the different possible selections, how many contain neither Bert nor Ernie? 12 - 2 9 2  Question: How many possible selection contain neither Bert nor Ernie?  C (10,9 )  Reduced the problem to a simple case of choosing k=9 out of n=10, without repetition, order doesn't matter, use the Combinations formula C (n,k). C(10,9)= 10!/(10-9)! = 10 combinations that do not include Bert and Ernie.Alternative explanation: You need 9 tenants out of 10. The same decision can be reversed - choosing 9 out of 10 to be included is the same as choosing the one tenant to be excluded

back  |  next 1 / 1