10) Combinations and permutations Flashcards
Counting # of items that meet a certain criteria
Combinations vs permutations
Combinations - when order in which a task is completed DOES NOT MATTER (e.g., groups)
Permutations - when order in which a task is completed MATTERS (e.g., ranks)
MEMORIZE: Combination formula when you have n objects to choose from and you pick k (“from n choose k”)
Strategy 1) Use formula
> Number of combinations = nCk = n! / [(n-k)!*k!]
Strategy 2) Visual method
> Visually think about the number of “slots” to fill and HOW MANY possible options could fill each spot
> Then, divide answer by k! in order to remove duplicates
e.g., 3 slots _ _ _, could have 3! or 321 = 6 ordered sets that represent the same GROUP
ABC
BAC
BCA
CAB
CBA
ACB
Combinations: Fundamental counting principle
Application - choosing k items from multiple independent groups
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 * n ways to perform BOTH the tasks together
e.g., if a nickel is flipped five times, how many different head and tail sequences are possible?
_ _ _ _ _ (independent tasks)
2 options for each flip ^ 5 flips = 32
Combinations: Choosing multiple items from multiple groups using the word “and”
e.g., I’m ordering pizza and can choose my own toppings. I can choose two cheeses from a total of four different cheeses and one veggie from a total of three different veggies. If there are no other toppings and I want two different cheeses and one veggie, how many possible ways are there for me to choose?
e.g., A treasure chest contains 5 different rubies, 4 different emeralds, and 3 different diamonds. If a pirate picks 5 jewels from the chest, 3 of which are rubies, how many possible ways exist for him to pick the jewels?
Strategy for solving:
> Determine the # of combinations for each sub-group
> Then multiply the answers (and = multiply)
e.g., Cheese = “four choose two” = 4C2 = 4!/(2!*2!) = 6 combinations
Veggie = “three choose one” = 3C1 = 3!/(2!*1!) = 3 combinations
So the total number of topping groupings = 6*3 = 18 combinations
ALTERNATIVE APPROACH #2
Cheese = _ _ = (4*3)/2! = 6
Veggie = _ = (3) = 3
6*3 = 18
e.g., Challenging question where we are given a FIXED number of one type and UNKNOWN number of other two types
_ _ _ _ _ = R R R _ _
First figure out the number of different ruby combinations = 5C3 = 10
Then for the remaining two slots, we can pick out of emeralds and diamonds = 7C2 = 21
So ans = 10*21 = 210 different possible ways to pick the jewels
Combinations: Choosing multiple items from multiple groups using the word “or” (choosing between alternatives)
e.g., a treasure chest contains four different coins, five different jewels, and six different daggers. If a pirate were to choose two coins or two jewels or two daggers from the chest and place them into a bag, how many different ways would it be possible for the pirate to fill his bag?
Strategy for solving:
> Determine the # of combinations for each sub-group
> Then add the answers (or = add) –> assumes events are MUTUALLY EXCLUSIVE (cannot occur at the same time)
e.g., two coins + two jewels + two daggers = 4C2 + 5C2 + 6C2
= 31
Combinations: Choosing “at least” some number of items, what does that mean?
e.g., you need to comprise a team of four people among 5 Turkish players and six Iranian players. If a team must have at least two Iranian players, how many different ways are there to produce the team?
e.g., what if you have the produce a team with at least one player from Iran?
“At least” means equal to or greater than
“At least” problems typically involve addition of outcomes
> OR = add
Add up the # of possible events
e.g., 2I and 2T OR 3I and 1T OR 4I and 0T
= 6C25C2 + 6C35C1 + 6C4*5C0
= 150 + 100 + 15
= 265
Special case: “At least 1 item chosen from a larger group” = Total # of ways - None
Combinations: “Must be selected” and “Must not be selected”
e.g., There is a pool of 25 students, including Olivia and Luna, from which we will select an 8-person team. If Olivia and Luna are NOT selected for the team, how many possible combinations are there?
e.g., There is a group of 10 students, including Tabitha and Grover. A team of 3 students is to be selected from those 10 students, and Grover is selected for the team while Tabitha is not. In how many ways can the team be formed?
Case A) Must be selected:
> Visualize the items that MUST be in the subgroup AS IF they have already been placed in the subgroup —> Already chosen, so no need for additional combination
Then determine how many items remain in the main pool vs to be filled in the subgroup —> combination (changes # remaining in the main group AND # spots remaining in the subgroup)
Case B) Must NOT be selected:
> Mentally ELIMINATE these items from the main pool (subgroup spots to be filled does NOT change)
e.g., 23C8
Case C) Some items MUST be chosen and another items CANNOT be chosen
> first figure out the MUST be selected (visualize the # of spots and which spots are fixed)
> then determine how many remain in the MAIN group and how many remain in the SUBGROUP
e.g., G _ _, 8C2 (10 students - Tabitha and Grover, 2 spots left)
Mutually exclusive and collectively exhaustive events - what should you remember?
e.g., A manager at investment firm F must create an investment team, which will consist of two portfolio managers, two assistants, and three analysts. If the manager is limited to constructing his team from a pool of four portfolio managers, four assistants, and five analysts, but two of the analysts cannot be on the same team together, how many different investment team configurations are possible?
Remember this in order to utilize TIME SAVING TACTICS:
If A and B are mutually exclusive yet collectively exhaustive events…
TOTAL # ways a scenario can occur = # ways A can occur + # ways B can occur
Time saving tactics: REARRANGE
> # ways B can occur = Total - # ways A can occur
e.g., # ways where J and B are NOT together = Total - # ways where J and B are together
e.g., Total - # ways two analysts are together
= [4C2 * 4C2 * 5C3] - [4C2 * 4C2 * 3] = 252
Dependent Combinations
e.g., a manager must assign 9 out of 10 workers to 3 different teams, namely a design team, a construction team, and a control team. 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 3 teams be formed?
Dependent combinations are problems where the occurrence of event A CHANGES the number of ways event B can be accomplished
e.g., “no worker is allowed to be on more than one team”
Strategy for solving:
> keep track of limitations and dependencies –> ADJUST the # remaining in the main group accordingly, ONE STEP AT A TIME
Group 1: 10C3 (from 10 workers, choose 3)
Group 2: 7C3 (from 7 remaining workers, choose 3)
Group 3: 4C3 (from 4 remaining workers, choose 3)
= 120 * 35 * 4
MEMORIZE: Permutation formula when you have n objects to arrange from and you pick k (“from n choose k”)
Strategy 1) Use formula
> Number of permutations= nPk = n! / (n-k)!
> similar to combination formula, except we DO NOT divide for duplicates
> n represents total # of items from which a choice can be made
> k represents the # of items to be chosen AND arranged in the order
Strategy 2) Visual method (PREFERRED METHOD)
> Visually think about the number of “slots” to fill and HOW MANY possible options could fill each spot
> Tip: think about using LETTERS to represent objects and keeping track of identical objects
e.g., 3 slots _ _ _, could have 3! or 321 = 6 ordered sets
ABC
BAC
BCA
CAB
CBA
ACB
MEMORIZE: Permutations with indistinguishable items
e.g., You have one gold bar, one silver bar, two identical platinum bars, and one titanium bar. How many different ways can the bars be arranged to form one line?
*** e.g., You have 5 balls, including 3 red and 2 blue and you want to pick two in an ordered way. How many permutations?
*** e.g., In a data set of numbers {2, 3, 3, 4, 4, 4, 4}, how many unique three digit numbers can be formed?
Indistinguishable items should be treated like DUPLICATES (identical items)
In looking for the number of permutations, we are looking for the # of DISTINGUISHABLE permutations
Strategy for solving - we need to DIVIDE the permutation BY the FACTORIAL OF FREQUENCY
Simple permutation (arranging ALL items) –> P = N! / [(frequency of object 1)! * (frequency of object 2)! …]
e.g., Arrange sequence GSPPT
P = 5! / 2! (two identical platinum bars) = 60
Complex permutation (arrange a subgroup of items) –> you CANNOT use the formula… better to think through logically about the different CASES and add them together (since they are mutually exclusive)
> automatically adjust for identical items when you think about different cases
e.g., R R R B B _ _
Case 1: Two identical balls
= 2 ways (RR or BB)
Case 2: Two different balls, R and B
= 2 ways (RB or BR , also # of ways to arrange RB = 2*1 = 2)
Total # of ways = 2 + 2 = 4
e.g., {2, 3, 3, 4, 4, 4, 4}
Case 1: three identical
= only 1 way (444)
Case 2: 2 identical, one different = X X Y
= (3! / 2! —> # of ways to order) * (2 * 2 –> selection for x and y)
= 12 ways
Case 3: All different = X Y Z
= 3!
= 6
Total # of ways = 1 + 12 + 6 = 19
MEMORIZE: Circular arrangements -> formula
Number of ways to arrange set of items in a circle = (K-1)!
Where K represents the number of items that are to be arranged in a circle
Tips for solving permutation problems with restrictions (e.g., two items must be next to each other, first position is fixed, three items must never be next to each other etc.)
e.g., At an airplane show, five different airplanes, the A1, the B2, the C3, the D4, and the E5, are being lined up for a display. In how many different ways can the planes be lined up if the A1, C3, and E5 can never all be next to each other in the line? (That is, they cannot compose a sequence of three airplanes.)
Strategy 1) Anchor method: begin by “anchoring” restricted items in their designated positions BEFORE handling other items that must be arranged
Strategy 2) Link items that must be together (form a single unit) to determine the number of ways to arrange, then MULTIPLY by the number of arrangements in the unit
e.g., Total not together = Total - Total together
Total = 5! (Number of ways to arrange 5 items)
Total together = 3! * 3! (treat three planes as one group, then multiply by the number of ways to arrange the subgroup)
Total not together = 5! - 3!*3!
= 84
Creating codes
e.g., how many three-digit numbers have all even digits?
e.g., a cell phone number is comprised of a three-digit area code, followed by a three-digit county code, followed by a four-digit phone code. If neither the first digit nor the fourth digit can be zero, but all other digits can be the numbers 0-9, inclusive, what is the max number of possible cell phone numbers?
Application of the counting principle
> Pay attention to whether REPEATED items are allowed (e.g., repeated letters of the alphabet creates a counting problem)
and as always, pay attention to restrictions
e.g., repeats allowed, but there are restrictions
> first digit can only be [2, 4, 6, 8]
> middle and last digit can be [0, 2, 4, 6, 8]
> ans = 455 = 100
e.g., repeats are allowed, but there are restrictions
ans = 8.1 * 10^9
