11. Combinatorics & Probability Flashcards
What signals a cominatorics problem?
The question “how many…?”
What is a Factorial (!)?
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).
Are factorials even or odd? (e.g. 13!)
All factorials are even because 2 is a factor. Factorials are considered anti-prime
What is the Fundamental Counting Principle?
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
What do the words “OR” and “AND” mean in the context of combinatorics questions?
OR = add AND = multiply
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?
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
D1 and D2 and D3 and D4 and D5
5 * 8 * 7 * 6 * 6 * 4
There are 6,720 possible combinations
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?)
n!
4 * 3 * 2 * 1 = 24 arrangements
What is the number of ways of rearranging n distinct objects if m members of a group are identical?
n! / m!
What is a Combination?
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
What is a Permutation?
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!
What is the formula for combinations?
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)
What is the formula for permutations?
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)
What are the two types of permutations?
(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)
What is the formula for combinations with repetition?
(n + k – 1)! / k!(n – 1)!
Repetition allowed, order does not matter
What is the formula for permutations with repetition?
n^k
How do you solve permutation and combination problems with multiple groups?
(1) Determine the number of combinations or permutations for the first group
(2) Repeat for the second group
(3) Multiply
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?
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.
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?
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
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?
1, 2, 3, 4, 5, 6, 7, 8,
Y, Y, Y, N, N, N, N, N
8! / 3!5! = 8 * 7 = 56