Combinatorics and Counting

Question 1

What is the fundamental principle of counting?

Answer 1

If an event can occur in n1 ways, and a second event in n2 ways, and a third in n3 ways, … and an i-th event in ni different ways, then the total number of ways the sequence 1 to i can occur is i! (i factorial)

Question 2

In how many was can N objects be chosen from a set of N distinct objects where the order is important?

Answer 2

NpN ( = N!)

Question 3

In how many ways can k objects from a set of N distinct objects be chosen, where k < N?

Answer 3

NPK

Question 4

What is the formula of NpK?

Answer 4

N!

(N-k)!

Question 5

How do you calculate the number of permutations of N objects when n1 are alike in one respect, n2 are alike in a second respect, …, and ni are alike in an i-th respect

Answer 5

N!

n1! x n2! x … x ni!

Question 6

How do we choose k objects from N if order is unimportant?

Answer 6

NCK, also called “n choose k”

Question 7

How many ways can k objects be chosen from a set of N when objects are replaced?

Answer 7

Question 8

What is the formula for NCK?

Answer 8

N! / (N-k)!k!

Question 9

In how many ways can K objects from a set of N distinct objects be chosen when you can replace them?

Answer 9

n choose k with replacement

Question 10

What signals a cominatorics problem?

Answer 10

The question “how many…?”

Question 11

What is a Factorial (!)?

Answer 11

The symbol for factorial is the exclamation point (!). n! is the product of all integers less than or equal to n. 4! = 4 * 3 * 2 * 1 = 24. In practice, the number 1 can be ignored (because 1 multiplied by anything does not change the product).

Question 12

Are factorials even or odd? (e.g. 13!)

Answer 12

All factorials are even because 2 is a factor. Factorials are considered anti-prime

Question 13

What is the Fundamental Counting Principle?

Answer 13

When making a number of separate decisions, multiply the number of ways to make each individual decision in order to find the number of ways to make all of the decisions. Example: Given a choice of 3 candidates for President and 2 candidates for Treasurer, there are 3*2 = 6 possible combinations for the President – Treasurer team

Question 14

What do the words “OR” and “AND” mean in the context of combinatorics questions?

Answer 14

OR = add AND = multiply

Question 15

An office manager must choose a five-digit lock code for the office door. The first and last digits of the code must be odd, and no repetition digits is allows. How many different lock codes are possible?

Answer 15

Set up “Slots” for each decision to be made and fill in the number of options. The first digit can be 1 or 3 or 5 or 7 or 9. There are 5 options for the first digit, and there are 4 remaining odd numbers remaining for the last digit The second through fourth digit are the probabilities of selecting the remaining available numbers. We subtract 1 from each remaining selection because we remove 1 possibility from the pool. Therefore, we get:

D1 * D2 * D3 * D4 * D5 which becomes

5 * 8 * 7 * 6 * 4

There are 6,720 possible combinations. We multiply these because we are making 5 selections.

Question 16

What is the number of ways of rearranging n distinct objects if there are no restrictions? (e.g. how many ways are there to arrange 4 people in 4 chairs in a row?)

Answer 16

n! 4 * 3 * 2 * 1 = 24 arrangements

Question 17

What is the number of ways of rearranging n distinct objects if m members of a group are identical?

Answer 17

n! / m!

Question 18

What is a Combination?

Answer 18

A subset of items chosen from a larger pool in which the order of items does not matter (REMEMBER: combinations sound less complicated). Example: When choosing 5 people from a pool of 10 to be on a basketball team, it doesn’t matter if Juliette is chosen first and Susie is chosen second or vice versa; if they are both chosen, in any order, then both are part of that 5-person team The formula is n! / [(n - k)! * k!], where n is the total number of items in the pool and k is the number of items to be chosen. In the above example, n = 10 and k = 5

Question 19

What is a Permutation?

Answer 19

A subset of items chosen from a larger pool in which the order of items does matter (REMEMBER: permutations sound more complicated) The formula is n! / (n - k)!, where n is the total number of items in the pool and k is the number of items to be chosen. In the above example, n = 10 and k = 3 Example: Ten people are running a race and three ribbons are to be awarded to the first (blue), second (red), and third (yellow) place finishers. If Juliette finishes first and Susie finishes second, this is a different scenario than Juliette finishing second and Susie finishing first; they are going to receive different ribbons depending upon how they finish!

Question 20

What is the formula for combinations?

Answer 20

nCk = n! / k!(n – k)! N = number of elements in the set k = number of elements in the subset *Without repetition (i.e. assumes that you cannot have the same element twice) *Use when the order of the smaller group that is being drawn from the larger group does NOT matter (e.g. think of the combination of salad toppings)

Question 21

What is the formula for permutations?

Answer 21

nPk = n! / (n – k)! N = number of elements in the set k = number of elements in the subset *Without repetition (i.e. assumes that you cannot have the same element twice) *Use when the order of the smaller group that is being drawn from the larger group matters (e.g. think about the three digit code to a lock)

Question 22

What are the two types of permutations?

Answer 22

(1) Repetition is allowed (e.g. three digit lock combination could be 333) (2) No repetition is allowed (e.g. the first three people to finish a race; you cannot be first and second)

Question 23

What is the formula for combinations with repetition?

Answer 23

(n + k – 1)! / k!(n – 1)! Repetition allowed, order does not matter

Question 24

What is the formula for permutations with repetition?

Answer 24

Source: https://www.mathsisfun.com/combinatorics/combinations-permutations.html

Question 25

How do you solve permutation and combination problems with multiple groups?

Answer 25

(1) Determine the number of combinations or permutations for the first group (2) Repeat for the second group (3) Multiply

Question 26

If you know how many subgroups of a certain size can be chosen from an unknown original larger group, can you deduce the size of the larger group?

Answer 26

One concept that you need to know for the exam is that when dealing with combinations and permutations, each result corresponds to a unique set of circumstances. For example, if you have z people and know that choosing two of them would result in 15 different possible groups of two, it must be true that z = 6. No other value of z would yield exactly 15 different groups of two. So if you know how many subgroups of a certain size you can choose from an unknown original larger group, you can deduce the size of the larger group.

Question 27

7 people enter a race. There are 4 types of medals given as prizes for completing the race. The winner gets a platinum medal, the runner-up gets a gold medal, the next two each get a silver medal, and the last 3 racers get bronze medals. What is the number of different ways the medals can be awarded?

Answer 27

Create an Anagram Grid in order to arrange members of a group. The number of columns in the grid will always be equal to the number of members of the group. The two silver medals and the 3 bronze medals are indistinguishable. Therefore, you need to divide the total possible arrangements 7! By 2! AND 3! 1, 2, 3, 4, 5, 6, 7 P, G, S, S, B, B, B 7! / 3!2! = 7 * 6 * 5 * 2 = 420

Question 28

A local card club will send 3 representatives to the national conference. If the local club has 8 members, how many different groups of representatives could the club send?

Answer 28

1, 2, 3, 4, 5, 6, 7, 8, Y, Y, Y, N, N, N, N, N 8! / 3!5! = 8 * 7 = 56

Question 29

The Beta Theta Pi fraternity must choose a delegation of three senior members and two junior members for an annual inter-fraternity conference. If Beta Theta Pi has 6 senior members and 5 junior members, how many different delegations are possible?

Answer 29

First, note that you are choosing senior members AND junior members. These are two different decisions, so you need to determine each separately and then multiply the possible arrangements. 6! / 3!3! = 5 * 4 = 20 5! / 2!3! = 5 * 4 / 2 = 10 So there are 20 possible senior delegations AND 10 possible junior delegations. Together there are 20 * 10 = 200 possible delegations

Question 30

The yearbook committee has to pick a color scheme for this year’s year-book. There are 7 colors to choose from (red, orange, yellow, green, blue, indigo, and violet. How many different color schemes are possible if the committee can select at most 2 colors?

Answer 30

Although this question concerns only one group (colors), it also involves multiple decisions. The question states that there can be at most 2 colors chosen. That means the color scheme can contain 1 color OR 2 colors. 1 color chosen and 6 colors not chosen = 7! / 1!6! = 7 2 colors chosen and 5 colors not chosen = 7! / 2!5! = 21

Question 31

Number Properties Guide, Ch 3, Q 1. In how many different ways can the word “LEVEL” be arranged?

Answer 31

30. There are two repeated E’s and two repeated L’s in the word “LEVEL.” 5! / 2!2! = 30

Question 32

Number Properties Guide, Ch 3, Q 2. Amy and Adam are making boxes of truffles to give out as wedding favors. They have an unlimited supply of 5 different types of truffles. If each box holds 2 truffles of different types, how many different boxes can they make?

Answer 32

10. In every combination, two types of truffles will be in the box, and three types of truffles will not. 5! / 2!3! = 10

Question 33

Number Properties Guide, Ch 3, Q 3. The Natural Woman, a woman’s food store, offers its own blends of trail mix. If the store uses 4 different ingredients, how many bins will it need to hold every possible blend, assuming that each blend must have at least two ingredients? (Also assume that each bin can hold one and only one blend)

Answer 33

11. Trail mix blends contain either 2, 3, or 4 ingredients. Consider each case separately. 2 ingredient blends = 4! / 2!2! = 6 3 ingredient blends = 4! / 3!1! = 4 4 ingredient blends = 1 All in all, there are 6 + 4 + 1 = 11 blends. The store will need 11 bins to hold all the blends

Question 34

Number Properties Guide, Ch 3, Q 4. A pod of 6 dolphins always swims in single file, with 3 females at the front and 3 males in the rear. In how many different arrangements can the dolphins swim?

Answer 34

36. There are 3! Ways in which the 3 females can swim. There are 3! Ways in which the 3 males can swim. Therefore there are 3! * 3! ways in which the entire pod can swim 3! * 3! = 36

Question 35

Number Properties Guide, Ch 3, Q 6. Mario’s Pizza has two choices of crust: deep dish and thin-crust. The restaurant also has a choice of 5 toppings: tomatoes, sausage, peppers, onions, and peperoni. Finally, Mario’s offers every pizza in extra cheese as well as regular. If Linda’s volleyball team decides to order a pizza with four toppings, how many different choices do the teammates have at Mario’s Pizza?

Answer 35

20. There are three decisions to be made. Decision 1: deep OR thin = 1 + 1 = 2 Decision 2: toppings = 5! / 4! = 5 Decision 3: regular OR extra = 1 + 1 = 2 Number of Choices = D1 * D2 * D3 = 2 * 5 * 2 = 20

Question 36

What is probability and how is it measured?

Answer 36

-The likelihood that a certain event will occur -Probability = (number of desired or successful outcomes) / (total number of possible outcomes) -The probability that some event definitely will occur is 1, or 100%; the probability that some event definitely will not occur is 0, or 0% -Further, the collection of all possible outcomes of a particular scenario add up to a probability of 1, or 100%.

Question 37

What is the formula for calculating probability?

Answer 37

Probability = (number of desired or successful outcomes) / (total number of possible outcomes) *Numerators and denominators of probabilities are related, but they must be calculated separately

Question 38

How do you calculate the number of outcomes for either the numerator or the denominator?

Answer 38

(1) Use an appropriate combinatorics formula (2) Manually count the number of outcomes

Question 39

Two number cubes with faces numbered 1 to 6 are rolled. What is the probability that the sum of the rolls is 8?

Answer 39

Start with the total number of possible outcomes (the denominator) using combinatorics. Rolling two cubes is like rolling cube 1 AND cube 2. For each of these rolls, there are 6 possible outcomes (the numbers 1 to 6). Since AND means multiply, there are 6 * 6 = 36 possible outcomes Here are the rolls that sum to 8: 2-6, 6-2 3-5, 5-3 4-4 Thus, the probability of a sum of 8 is 5/36

Question 40

Molly is rolling a number cube with faces numbered 1 to 6 repeatedly. When she receives a 1, she will stop rolling the cube. What is the probability that Molly will roll the die less than 4 times before stopping?

Answer 40

We are looking for Molly getting a 1 in either the first, second, or third roll. The question also is include to throws 1-3 (because it is fewer than 4 throws). In other words, we want to sum the following (following the OR rule):

P(1) = 1/6

P(1,something else) = 1/6*5/6

P1(1, something else, something else) = 1/6 * 5/6 * 5/6

Therefore, the probably of Molly getting a 1 in 3 or less dice is:
P(getting a 1 in fewer than 4 throws) = 1/6 + (1/6*5/6) + (1/6*5/6*5/6) == 0.4212962963

Note that you can also use the inverse law of probability where P(event) == 1 - P(event not happening). In otherwords, you can use the formula for the probability of NOT getting a 1 in three dice rolls to get the same answer.

P(Not getting a 1 in 3 dice rolls) = 1 - (5/6*5/6*5/6) = 0.4212962963

Question 41

What is the probability that, on three rolls of a numbered cube with faces numbered 1 to 6, at least one of the rolls will be a 6?

Answer 41

For complicated probability problems, decide whether it is easier to calculate the probability you want (X) or the probability that you don’t want (1 – X) For each of the three rolls, there is 5/6 probability that the die will NOT yield a 6. P(Not a 6) = (5/6)(5/6)(5/6) = 125/216 P(6) = 1 – X = 91/216 Takeaway: -REMEMBER: if you need to calculate the probability of an even (P(A)P, there are two ways to calculate the probability: P(A) or 1 – P(Not A)

Question 42

What is the probability of A or B happening?

Answer 42

P(A or B) = P(A) + P(B) – P(A and B) *When A and B are mutually exclusive (i.e. cannot happen at the same time), P(A and B) = 0

Question 43

What is the probability of A and B happening for independent and dependent events?

Answer 43

Independent (with replacement): P(A and B) = P(A) * P(B) Example: flipping a coin, rolling dice Dependent (without replacement): P(A and B) = P(A) * P(B|A) Where P(B|A) = P(A and B) / P(A)

Question 44

Number Properties Guide, Ch 4, Q 3. There is a 30% chance of rain and 70% chance of shine. If it rains, there is a 50% chance that Bob will cancel his picnic, but if the sun is shining, he will definitely have his picnic. What is the chance that Bob will have his picnic?

Answer 44

85%. There are two possible chains of events in which Bob will have the picnic: (1) The sun shines: P = 70% (2) It rains AND Bob chooses to have the picnic anyways = 0.3(0.5) = 15% P(Bob has picnic) = 70% + 15% = 85%

Question 45

Number Properties Guide, Ch 4, Q 5. A magician has five animals in his magic hat: 3 doves and 2 rabbits. If he pulls two animals out of the hat at random, what is the chance that he will have a matched pair?

Answer 45

40%. There are 5! / 2!3! = 10 possible pairs. List the pairs in which the animals will match R(a)-R(b) D(x)-D(y) D(x)-D(z) D(y)-D(z) There are four possible pairs in which the animals will be a matched set. Thus, there is a 40% chance that he will have a matched pair

Question 46

Alicia lives in a town whose streets are on a grid system, with all streets running east-west or north-south without breaks. Her school, located on a corner, lies three blocks south and three blocks east of her home, also located on a corner. If Alicia only walks south or east on her way to school, how many possible routes can she take to school?

Answer 46

20. Alicia will have to walk south three times and east three times on her way to school. That’s 6 blocks in total that she will walk. That’s also 6 decisions in a row that she will make: walk south or walk east. You are arranging 6 decisions but you also have repeats: 3 blocks south and 3 blocks east. Routes to school = 6! / 3!3! = 5 * 4 = 20

Question 47

Greg, Marcia, Peter, Jan, Bobby and Cindy go to a movie and sit next to each other in 6 adjacent seats in the front row of the theater. If Marcia and Jan will not sit next to each other, in how many different arrangements can the six people sit?

Answer 47

480. To solve this problem, ignore the constraint for now. Just find the number of ways in which six people can sit in 6 chairs. 6! = 720 To count the ways in which Jan MUST sit next to Marcia, use the Glue Method: For problems in which items or people must be next to each other, pretend that the items “stuck together” are actually one larger item. Imagine that Jan and Marcia are stuck together. There are now effectively 5 people. JM, G, P, B and C. These people can be arranged in 5! = 120 different ways Each of those 120 different ways, though, represents two different possibilities, because the stuck together moviegoers could be in order J-M or M-J. Therefore, the total number of seating arrangements with Jan next to Marcia is 2 * 120 = 240. Finally, the 240 possibilities are the ones to be excluded from consideration. The number of allowed seating arrangements is therefore 720 – 240, or 480

Question 48

In a box with 10 blocks, 3 of which are red, what is the probability of picking out a red block on each of your first two tries? Assume that you do NOT replace the first block after you have picked it.

Answer 48

3/10 * 2/9 = 1/15 *Do not forget to analyze events by considering whether one event affects subsequent events *The first roll of a die or flip of a coin has no effect on any subsequent rolls or flips *However, the first pick of an object out of a box does affect subsequent picks if you do not replace that object

Question 49

A miniature gumball machine contains 7 blue, 5 green and 4 red gumballs, which are identical except for their colors. If the machine dispenses three gumballs at random, what is the probability that it dispenses one gumball of each color?

Answer 49

1/4. Consider one specific case: blue first, then green, then red. By the domino effect rule, the probability of that case is: 7/16 * 5/15 * 4/14 = 1/24 Now consider another case: green first, then red, then blue. The probability of this case is: 5/16 * 4/15 * 7/14 = 1/24. Notice that all we have done is swap around the numerators. We get the same final probability because the order in which the balls come out does not matter! Therefore, the overall probability is 6 * 1/24 = 1/4 Takeaway: -In general, when you have a symmetrical problem with multiple equivalent cases, calculate the probability of one case (often using the domino effect rule); then multiply by the number of cases

Question 50

Renee has a bag of 6 candies, 4 of which are sweet and 2 of which are sour. Jack picks two candies simultaneously and at random. What is the chance that exactly 1 of the candies he has picked is sour?

Answer 50

8/15. Even though Jack picks the two candies simultaneously, you can pretend that he picks them in sequence. This trick allows you to set up a probability tree that reflects Jack’s picks at each stage Sour First (2/6) * Sweet Second (4/5) = 8/30 Sweet First (4/6) * Sour Second (2/5) = 8/30 Finally, EITHER one scenario OR the other scenario works: in either case, Jack picks exactly one sour candy. So you add these probabilities: 8/30 + 8/30 = 16/30 = 8/15 Takeaway: -Avoid setting up overly complicated trees, which GMAT problems almost never require; instead use trees to conceptualize a path through the problem

Question 51

Number Properties, Ch 7, Q1. Three gnomes and three elves sit down in a row of six chairs. If no gnome will sit next to another gnome and no elf will sit next to another elf, in how many different ways can the elves and gnomes sit?

Answer 51

72. The only way to ensure that no two gnomes and no two elves sit next to each other is to alternate seats (GEGEGE or EGEGEG). Begin by seating the gnome. The first gnome can sit anywhere and therefore has 6 choices. The second gnome must sit in an odd chair or an even chair depending on the first gnomes choice. Therefore, the second gnome has 2 choices. The last gnome only has one choice. Then begin seating the elves. The first elf can sit in any of the three empty chairs, the second in any of the other two, and the last in the final remaining chair. Therefore, the first elf has three choices, the second elf has two choices, and the third elf has one choice Finally, find the product of the number of choices for each person: Seating Arrangements = (6 * 2 * 1) * (3 * 2 * 1) = 72

Question 52

Number Properties, Ch 7, Q2. Gordon buys 5 dolls for his 5 nieces. The gifts include two identical Sun-and-Fun beach dolls, one Elegant Eddie dress-up doll, on GI Josie army doll, and one Tulip Troll doll. If the youngest niece does not want the GI Josie doll, in how many different ways can he give the gifts?

Answer 52

48. The anagram looks like this: S, S, E, G, T Total Number of Arrangements = 5! / 2! = 60. First solve the problem without considering the constraint. There are 5 nieces and 5 dolls with 2 repeats. Arrangements Assuming Youngest Gets G = 4! / 2! = 12. Next calculate the number of arrangements in which the youngest niece does get the GI doll. If the youngest niece does get G, then there are four nieces remaining and S, S, E, and T. Arrangements Assuming Youngest Does Not Get G = 60 – 12 = 48. Finally, subtract the number of arrangements in which the youngest niece gets the GI doll from the total possible number of arrangements.

Question 53

Number Properties, Ch 7, Q4. In a bag of marbles, there are 3 red, 2 white, and 5 blue. If Bob takes 2 marbles out of the bag, what is the probability that he will have one white and one blue marble? (Assume that Bob does not replace the marbles in the bag)

Answer 53

2/9. List the winning scenarios and add their probabilities P(Blue-White) = 5/10 * 2/9 = 1/9 P(White-Blue) = 2/10 * 5/9 = 1/9 P(Blue & White) = 1/9 + 1/9 = 2/9

Question 54

Number Properties, Ch 7, Q5. A florist has 2 azaleas, 3 buttercups and 4 petunias. She puts two flowers together at random in a bouquet. However, the customer calls and says that she does not want two of the same flower. What is the probability that the florist does not have to change the bouquet?

Answer 54

13/18. The anagram looks like this: A, A, B, B, B, P, P, P, P P(A-A) = 2/9 * 1/8 = 2/72 = 1/36 P(B-B) = 3/9 * 2/8 = 2/24 = 1/12 P(P-P) = 4/9 * 3/8 = 12/72 = 1/6 P(Same) = 1/36 + 3/26 + 6/36 = 10/36 = 5/18 P(Different) = 13/18

Question 55

Number Properties, Ch 7, Q6. Five A-list actresses are vying for three leading roles in the new film, “Catfight in Denmark.” The actresses are Julia Robards, Meryl Strep, Sally Fieldstone, Lauren Bake-all, and Hallie Strawberry. Assuming that no actress has any advantage in getting any role, what is the probability that Julia and Hallie will star in the film together?

Answer 55

3/10. Two alternatives: probability logic or counting methods Probability logic: P(Julia-Hallie-Something) = 1/5 * 1/4 * 3/3 = 1/20 Arrangements = 3! = 6 P(Julia & Hallie Star) = 6/20 = 3/10 Counting methods: Number of Different Combinations Starring Julie and Hallie = 5! / 3!2! = 10 There are three possible combinations that feature both Julia and Hallie: Julia-Hallie-Sally Julia-Hallie-Meryl Julia-Hallie-Lauren Therefore, the probability that Julia and Hallie will star together is 3/10

Question 56

Number Properties, Ch 7, Q7. For one roll of a certain die, the probability of rolling a two is 1/6. If this die is rolled 4 times, what is the probability equation that the outcome will be two at least 3 times?

Answer 56

P(Exactly 4) = (1/6)^4. First, calculate the probability of rolling two exactly four times. P(2,2,2,Something) = (1/6)^3 * (5/6). Then, calculate the probability of rolling two exactly three times out of four attempts. Arrangements = 4! / 3! = 4. And incorporate the number of different ways you can roll two exactly three times out of four attempts. Apply that to the probability P(Exactly 3) = 4[(1/6)^3 * (5/6)] P(At Least 3 Times) = 4[(1/6)^3 * (5/6)] + (1/6)^4

Question 57

For questions that ask for “at least one” outcome, how can you simplify figuring out the probability?

Answer 57

Treat as the opposite situation (i.e. NONE)