Combinatorics and Counting Flashcards

1
Q

What is the fundamental principle of counting?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

NpN ( = N!)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

NPK

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the formula of NpK?

A

N!

(N-k)!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

N!

n1! x n2! x … x ni!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

NCK, also called “n choose k”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the formula for NCK?

A

N! / (N-k)!k!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

n choose k with replacement

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What signals a cominatorics problem?

A

The question “how many…?”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a Factorial (!)?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the Fundamental Counting Principle?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

OR = add AND = multiply

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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?)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

n! / m!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a Combination?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a Permutation?

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the formula for combinations?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the formula for permutations?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are the two types of permutations?

A

(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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the formula for combinations with repetition?

A

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

24
Q

What is the formula for permutations with repetition?

A

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

25
Q

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

A

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

26
Q

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?

A

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.

27
Q

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?

A

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

28
Q

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?

A

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

29
Q

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?

A

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

30
Q

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?

A

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

31
Q

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

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

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?

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

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)

A
  1. 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
34
Q

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?

A
  1. 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
35
Q

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?

A
  1. 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
36
Q

What is probability and how is it measured?

A

-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%.

37
Q

What is the formula for calculating probability?

A

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

38
Q

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

A

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

39
Q

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

A

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

40
Q

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?

A

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

41
Q

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?

A

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)

42
Q

What is the probability of A or B happening?

A

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

43
Q

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

A

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)

44
Q

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?

A

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%

45
Q

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?

A

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

46
Q

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?

A
  1. 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
47
Q

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?

A
  1. 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
48
Q

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.

A

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

49
Q

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?

A

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

50
Q

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?

A

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

51
Q

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?

A
  1. 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
52
Q

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?

A
  1. 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.
53
Q

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)

A

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

54
Q

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?

A

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

55
Q

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?

A

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

56
Q

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?

A

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

57
Q

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

A

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