Ch. 15 Combinations and Permutations

Question 1

Combination Formula

Answer 1

“n choose k”
nCk = n! / [(n-k)! k!]

n = number of items to choose from
k = number of items we’re actually choosing

Question 2

How to handle “at least” questions - e.g., there are six different fruits at the market and you must select at least two.

Answer 2

Treat each scenario as a mutually exclusive event:
Scenario 1: You select two fruits
Scenario 2: You select three fruits
Scenario 3: You select four fruits
Scenario 4: You select five fruits
Scenario 5: You select six fruits

You must calculate the number of ways of each scenario individually, then add them up b/c they are mutually exclusive (they cannot occur at the same time)

Question 3

How do you know if a problem is a combination or permutation problem?

Answer 3

Combination = order doesn’t matter (ex: select two out of four coffee types)
Permutation = order matters (ex: select two out of four coffee types and determine which one you’re drinking first then second)

When the order matters, there are two “choices” / two unique arrangements
Dark Roast - French is different from French - Dark Roast

Whereas in a combination, if you choose Dark Roast first, then choose French, or vice versa, it doesn’t matter - both are the same arrangement.

Question 4

Fundamental counting principle - if two tasks are independent, how many possible ways to perform both tasks together?

Answer 4

If there are m ways to perform task 1 and n ways to perform task 2, there are m x n ways to perform the two tasks together.

Perform task 1 AND task 2.

Question 5

What does it mean when two tasks are independent?

Answer 5

You can perform them at the same time; one does not depend on the other!

For example, you can select one bread and one meat for your sandwich, and selecting one bread doesn’t stop you from selecting any meat.

In this scenario, you MUTLIPLY to determine total possible combos.

Question 6

What does it mean when events are mutually exclusive?

Answer 6

They can’t occur at the same time; when one occurs, the other(s) cannot.

Question 7

If tasks A and B are mutually exclusive and there are x ways to accomplish event A and y ways to accomplish event B, how many ways are there to accomplish A or B?

Answer 7

there are x + y ways to accomplish either one

Question 8

How to solve if some items MUST be chosen? i.e., there are 10 fruit, you need to pick 5, two apples must be chosen.

Answer 8

Pretend that they’ve ALREADY been chosen & take them out of the equation.
10 fruit, you must pick 5 = 10 C 5
Remove 2 apples = now there’s a pool of 8 to choose from, and you can only select 3 because 2 have already been selected = 8 C 3

Question 9

How to solve if some items CANNOT be chosen? i.e., there are 10 fruit, you need to pick 5, one pear cannot be chosen.

Answer 9

Eliminate that pear from the main pool (n) - the number of fruits you have to pick is still 5, so keep k = 5.
Initially you had 10 C 5, now it’s 9 C 5 (w/o the pear)

Question 10

How to solve if some items MUST be chosen & others cannot be chosen?

Answer 10

Do one step at a time:
1. If items must be chosen, pretend they’ve already been chosen & remove from pool & number of choices (reduce n & k)
2. If items cannot be chosen, remove from pool (n) but leave k as is b/c you still have to select the same number of items

Question 11

What are collectively exhaustive events?

Answer 11

Two+ events are collectively exhaustive if together they represent ALL possible outcomes

Question 12

If two events, A and B, are both mutually exclusive and collectively exhaustive, what can we do?

Answer 12

All possible outcomes = Number of ways A can occur + Number of ways B can occur

We can play with this formula and do
All possible outcomes - Number of ways A can occur = Number of ways B can occur
(if getting the number of ways B can occur is really time consuming)

Question 13

What’s an alternative way to solve “at least one” combination problems?

Answer 13

B/c none and at least one are mutually exclusive & collectively exhaustive, we can do,
Total = None + at least one
Total - None = at least one

It’s much easier to calculate total & none, then subtract.
(vs. all of the different “at least one” scenarios: select 1, select 2, select 3, select 4, etc.)

Question 14

How can you solve a question where some items CANNOT be together in a group? For example, Juan and Maria can each be chosen, but they cannot BOTH be chosen.

Answer 14

Total possible outcomes = Number of configurations where Juan and Maria are chosen together for the group + Number of Configurations where Juan & Maria are NOT chosen together for the group.

Total - Together = Not together

If it’s a 5 person club, and you can choose 3 members, it’s
Total = 5C3
Together = 3C1 (that’s b/c you’ve already chosen 2 members, so you only need one more and you have 3 left to choose from)
Not together = 5C3 - 3C1

Question 15

How do you solve for the total number of items in the pool (n) when you’re given the number you’re choosing (k) and the total possible outcomes?

Answer 15

Use the box method!
For example, if it’s a combination and k = 2 and the total number of outcomes is 66,
[(n)(n-1)] / 2! = 66 & solve for n.

If permutation, (n)(n-1) = 66

Question 16

What is the basic permutation formula?

Answer 16

nPk = n! / (n-k)!

Question 17

Given equal quantities, what has more unique arrangements, permutations or combinations?

Answer 17

Permutations b/c A,B and B,A are two different arrangements
Whereas in combinations A,B and B,A is a duplicate/ only counted once.

Question 18

What do we do in combinations to get rid of duplicates?

Answer 18

Think of the box method, we divide by the factorial of the number of decisions (we don’t do this in permutations)

Question 19

What do you do if you have repeats / identical items in a permutation?

Answer 19

P = N! / (r1! x r2! x…x rn!)
N = total number of items, and r1 = number of repeats of first item

Question 20

How to get all possible arrangements for the set: B,B,B,R,R,R?

Answer 20

P = 6! / (3! x 3!)
Total items factorial / (number of Bs factorial x number of Rs factorial)
Total factorial / repeats factorials

Question 21

Number of ways to arrange K items in a circle formula

Answer 21

(K - 1)!
* Arrangements are only considered unique if the placement relative to OTHERS is unique, NOT the actual seat.

Question 22

3 Approaches (high level) to solve permutation questions where restrictions are placed (Happy and Jumpy must sit together)

Answer 22

Anchor method, link items together, “collectively exhaustive” approach

Question 23

Steps to link items together when restrictions placed in a permutation problem. Example: you’re arranging 7 items, 3 must be together.

Answer 23

1. Find your new n with linked items: if n = 7 and you want to link 3 items together, your new n = 7 - 3 + 1 = 5
2. Do the permutation: 5P5 = 5! = 120
3. Multiply the permutation by number of items linked together factorial: 3! –> 120 x 3! = 720 possible outcomes.

Question 24

Steps when items can’t be next to each other in permutation problem

Answer 24

1. Total = Items next to each other + items not next to each other
2. Total - items next to each other = items not next to each other
3. Solve for Total & items next to each other (pretend those 2 items have already been chosen, do permutation of n-2, k-2)

Question 25

If you’re creating a three digit code to label products, you’re using letters, and letters can repeat, how many total possible codes are there? What if they can’t repeat?

Answer 25

26 x 26 x 26
26 x 25 x 24

This is due to fundamental counting principle - m ways to do task 1, n ways to do task 2, mn ways to do both (if they’re independent)