Combinatorics Flashcards
To determine the total number of ways that two or more separate decisions can be made simply multiply the number of ways that each individual decision can be made
4 sizes x 5 colors = 20 different options
What does “he selects no more than one from each category” indicate?
There is an additional option of selecting none for each category so add one to each option then apply counting rule
What is the counting rule?
To determine the total number of ways that two or more separate decisions can be made simply multiply the number of ways that each individual decision can be made
What is a useful technique for handling complex counting problems?
A slot diagram
How do you use a slot diagram?
Draw a series of empty slots corresponding to the number of choices that must be made
Fill each slot w the possible number of options for that slot
Apply fundamental counting principle
When counting digits what numbers are digits? What number should you not forget?
1-9
Dont forget 0
If a code gives you a number, remember to do what when creating your slot diagram?
Put a 1 for that number
Do not put that number in the slot
What should you do if your counting problem restricts two or more options from occurring together?
Subtract the number of restricted options from the total number of potential options
Remember that a two digit number cannot begin w zero
…
What are the two ways to solve an ordering probpem?
Slot diagram
Ordering formula
How do you slot an ordering problem?
Write slots, fill them, multiply
Each slot looses an option so its usually in descending order
432*1
What is the ordering formula?
n!
N= number of objects being ordered
!= n(n-1)(n-2)(n-3)
What is 0!
1
How do you work with factorials shown as fractions?
Cancel the largest common element i.e.
8! / 5!3! = 8*7 (canceled 5! )
How do you determine the number of unique ways a set of repetitious elements can be arranged?
I.e. how many ways can the letters in the word level be aranged?
Divide the factorial of the total number of elements by the factorial of the number of repetitious elements
I.e. for LEVEL 5!/2!2! = 30
What do you do when you have an ordering problem with extra slots?
What if its more than one extra slot?
Consider the slot as an extra object to be ordered
I.e. 5 slots for 4 unique numbers is 5!
Consider empty slots repetitious
What is 1!
1
What is 6!
720
What is 5!
120
How do you solve ordering problems that stipulate that certain objects must be together?
Fuse the group that must be together into a single item
Find the new object amount permutation
And multiply that by the permutation of the group that must be together.
I.e. if 8 objects and 3 must be together
The answer is 6! * 3! = 4320
How do you solve ordering problems if certain objects cant be together ?
Find the permutation of the number of objects
Multiply the permutation of the group and the restricted objects
Find the difference of the two groups
I.e. a group of 7 objects where 3 cant be together would be
7!
5!3!
7! - (5!3!)
Whats the difference between a permutation problem and an ordering problem?
Ordering problems arrange an entire group
Permutation problems arrange a subset of a group
Whats the easiest way to solve a permutation problem?
Use a slot diagram
Only create slots for the subset of the objects being asked about
What is the formula for circular arrangements?
Total possible linear arrangements/ total spots around the circle
A group of elements always has ____ combinations than permutations?
Fewer
Whats the difference between a permutation and a combination?
In combinations items are selected and order doesnt matter
In permutation items are arranged and order matters
What is the formula for combination problems?
Factorial of the total group/ (factorial of the selected group)(factorial of the unselected group)
What are some items that signify a combination problem when the questions asks “how many ways” or “total number of ways”?
Teams, hands, socks
Lines, triangles,diagonals
Toys, tools,trinkets
Colors,labels,tags
What type of problem is one where a path can be navigated between two spots on a grid?
Combinatorics
Whats the formula for solving a grid combinatorics problem?
Factorial of the total number of blocks/ ( factorial of the horizontal blocks x factorial of the vertical blocks ) are
What do you do if you have multiple combinations or arrangements together?
Solve each separately and then multiply their results
How do you solve combination questions with “at least”, “or”, “no more than”?
Add their products
You will have to add a successive series of combinations
I.e. all possible combinations of three or more objects , three or less objects
What is the formula used to answer a combination problem asking about all the possible combinations?
C=2^n - 1
Where n is the number of total objects
“At least one” combination problems are successive combination problems. How do you solve them?
Find the total number of combinations
Then subtract the amount of combinations for the group that is NOT referred to in the “at least” portion of the problem
How do you solve combination problems with restrictions ?
Find the must include numbers
And multiply it by the can include combo
I.e. from the word MAGIC how many three letter subgroups can be selected that include the letter A ?
1= the one for A 6= 4!/(2!2!). For MGIC 6*1= 6
If you have two objects both selected from two different sets . You can calculate the ways of choosing both simultaneously by…
Multiplying them together
I.e. on a menu w 5 apps and 10 entrees there will be 50 different meals
You do straight up factorials for…
Ordering n objects
I.e. the number of ways of ordering the letters ABC is 3! Or 6
