Combinations & Permutations

Question 1

Combination Formula

Answer 1

_nC_k = n! / (n-k)!k!

• n = number of objects from which a choice can be made
• k = number of objects that are to be chosen

The combination formula is really taking the permutation formula and divide by k!

→ *****Think: How many ways are there to arrange k items in k spots? k!. We don’t want to count all the arrangements of k items.

Question 2

Combination: Box and Fill Method

Answer 2

Let each box represent a specific decision that must be made. Then divide the product of all the numbers in the boxes by the factorial of the number of boxes that have numbers inside.

Question 3

Counting Principle

Answer 3

If there are m ways to perform task 1 and n ways to perform task 2 and the tasks are independent, then there are m x n ways to perform both of the tasks together.

Hard example: A certain mailman has 7 different unaddressed flyers that need to be placed into 5 different mailboxes. If any of the flyers can go into any of the mailboxes, how many possible ways are there for the mailman to distribute the flyers?

• Think from the “flyer POV” instead of mailbox.
• Flyer 1 could be placed into any of 5 different boxes. Same for Flyer 2, Flyer 3…Flyer 7
• Answer = 5⁷

Question 4

Mutually Exclusive Events

Answer 4

• Events are mutually exclusive if they can’t occur together at the same time
• Signaled by the word “or”
• If there are x ways to accomplish event A and y wants to accomplish event B and if A and B are mutually exclusive, then there are x + y ways to accomplish A or B.

Question 5

Combinations with Restrictions:

Some Items Must be Chosen

Answer 5

1. Visualize the items that must be in the subgroup as if they have already been placed in the subgroup.
2. Determine both how many items remain in the main pool and how many spots remain to be filled in the subgroup.

Question 6

Combinations with Restrictions:

Some Items Must NOT be Chosen

Answer 6

1. Mentally eliminate from the main pool those items that are excluded from the subgroup.
2. Note that eliminating items from the main pool doesn’t change the number of spots in the subgroup.

Question 7

Collectively Exhaustive

Answer 7

Two events are collectively exhaustive if, together, the events represent all of the potential outcomes of a situation.

Question 8

Mutually Exclusive & Collectively Exhaustive

Answer 8

Useful when (subtraction from total):

• Calculating the number of ways in which an event can occur when x items are excluded from being together in the same subgroup of y items
• Choosing at least 1 item from a group = total ways - ways to choose none

Question 9

Permutation Formula

Answer 9

_nP_k = n! / (n-k)!

n = number of objects from which a choice can be made

k = number of objects that are to be chosen

Question 10

Permutation Formula for Indistinguishable Items

Answer 10

P = N! / (r₁! x r₂! x r₃! x … r_n!)

• N = total number of items to be arranged
• r = frequency of each indistinguishable object

Example: In how many ways can the letters A,A,B,B be arranged? → 4! / (2! x 2!) = 6

Question 11

Permutation: Box and Fill Method

Answer 11

Let each box represent a specific decision that must be made. Calculate the product of all the numbers in the boxes (no need to divide by the factorial of the number of boxes that have numbers inside).

Question 12

Circular Arrangement

Answer 12

K items can be arranged in a circle in (K - 1)! ways

Example: How many ways can 4 people sitting in a circular table be arranged?

• 4! / 4 → Since there are 4 seats, there are 4 repeated arrangements (rotate 4 times)
• (4 - 1)! → Condition: All 4 chairs are identical. Imagine locking 1 person in 1 seat. 3 seats left to fill.

Question 13

Permutations: Items Next to Each Other

Answer 13

When x items must be together in an arrangement of y items, treat those x items together as one unit. There are now y - x + 1 items that can be arranged in (y - x + 1)! ways. In addition, the x items can be arranged in x!, generating a total of (x!)(y - x + 1)! ways to arrange the y items.

Example: In how many ways can SPENCER be arranged if S and P must always be together and the N and C must always be together?

• (SP) (NC) E E R → 5! / 2! (because 2 E’s) → 60
• (SP) and (NC) each can be arranged in 2! ways → 2! x 2! = 4
• Answer = 240 (60 x 4)

Question 14

Permutations: Items Not Next to Each Other

Answer 14

Take advantage of the collectively exhaustive and mutually exclusive idea. Subtract from total number of ways. In other times, just need to reason it out…

Example: A farmer is planting a row consisting of 4 unique apple trees and 4 unique orange trees. How many ways are there for the farmer to plant the trees such that no apple tree is adjacent to another apple tree and no orange tree is adjacent to another orange tree?

• This means either the orange trees or apple trees must be in the odd-numbered spots. Calculate one of the scenarios then x2
• If apple trees are in the odd positions: AOAOAOAOAO
  → For the apple trees: 4!
  → For the orange trees: 4!
  → Total = 4! x 4! = 24 x 24 = 576
• Answer = 576 x 2 = 1152 ways

Question 15

Permutation: Calculating an Unknown Number of Items in a Group

Answer 15

When we are asked to calculate the number of items in a group based on the number of ways that a subset of that group could be chosen and then ordered, we use a variable to represent the total number of items from which to choose, and then solve the problem using a box-and-fill diagram.

Question 16

Single Elimination Game

Answer 16

It takes n - 1 games to execute a single elimination game, with n = number of teams

Question 17

Permutation: Example

Answer 17

From a group of students, 2 are to be elected as president and vice president.

Order MATTERS

Question 18

Removing Duplicate Team

Answer 18

A manager must assign 9 out of 10 workers to 3 different teams. If each team is composed of 3 workers and no worker is allowed to be on more than one team, in how many different ways can the three teams be formed?

₁₀C₃ x ₇C₃ x ₄C₃ / 3! = (120 x 35 x 4) / 3!

→ Divide by 3! because there are many duplicate 3 team formations. Imagine if we had only 2 people and need to determine the number of ways to form 2 teams of 1. 2C1 x 1C1 = 2, which isn’t correct.

THINK: Similar to the “Box and Fill” method where you need to divide.

Question 19

Combination + Permutation Question

Answer 19

A dance delegation of 4 people must be chosen from 5 pairs of dance partners. If 2 partners can never be together on the delegation, how many different ways are there to form the delegation?

• Permutation: Once a person (out of 10) is selected, that person’s partner can’t be selected. This reduces the second choice to 8 people, and so on. Pattern = 10 x 8 x 6 x 4
• Combination: Need to divide by 4! because the process of selecting the dance partners is a combination.
• Answer: 10 x 8 x 6 x 4 / 4! = 80