Combinatorics Flashcards
What does combinatorics deals with?
combinations of objects from a specific, finite set
What Restrictions can be formed to apply to combinations?
Repetition
Order
Or other criterion
What are the 3 integral parts of Combinatorics?
- Permutations
- Variations
- Combinations
we use these to determine the number of favorable outcomes OR
the number of all elements in a sample space
What do Permutations represent?
Permutations represent the number of different possible ways we can arrange a set of elements
What is the formula for Permutations?
n!
How are Permutations denoted?
P()
Going back to the Formula 1 example from the lecture, in how many ways can the 20 drivers finish a race?
20!
When we determine the available options for every position in a permutation, can we start with the middle element?
Yes, choosing the order is completely up to us.
What are factorials denoted as?
!
What does n! represent?
The product of the natural numbers from 1 to n
ie. n! = 1 x 2 x 3 x …. x n
3! = 1 x 2 x 3 = 6
What is one odd characteristic of factorials?
Negative numbers don’t have a factorial
What are some important properties of factorials?
n! = (n-1)! x n
(n + 1)1 = n! x (n +1)
What is 5! Equal to?
120
Which of the values below is NOT the equivalent to “6!” ?
A) 123456
B) 7!/7
C) 4!5*6
D) 8!/8
8!/8
Which of the following is equivalent to 5!/3! ?
A) 45/6
B) 123
C) 45
D) 1*2
C) 4*5
What is the formula for Variations without Repetition?
V = n! / (n - p)!
The number of variations without repetition when arranging ‘p’ elements out of a total of ‘n’ elements.
What do Variations express?
The total number of ways we can pick and arrange some elements of a given set
What is ‘n’ in probability theory?
n = the total number of elements we have available
What is ‘p’ ?
p = the number of positions we need to fill
When arranging ‘p’ elements out of a total of ‘n’
What is the Notation and Formula for calculating Variations with Repetition?
V = n to the power of p
V bar, n, p = n to the p
n = the total number of elements we have available
p = the number of positions we need to fill
The number of variations with repetition when picking p-many elements out of n elements, is equal to n to the power of p
What is the formula for Variations with Repeating values?
n to the power of p
When do we use Variations instead of Permutations?
When we are not arranging all elements in the sample space.
Going back to the combinations lock example from last lecture, imagine the correct code consisted of a single 4-letter word. Remember that we can only use the letters A, B and C. How many possible passcodes are there?
3^4
4^3
2^3
26^4
n to p
or
3^4
How do we calculate Variations for events without repetition?
We cannot use the same element twice
example element: person in running schedule
What is the Notation and Formula for Variations without repetition?
n! / (n - p)!
Going back to the relay example from the lecture, what if instead of 5 people on the team, we had 7. We would still have to choose 4 of them and arrange them in what order to run, but in how many ways can we accomplish that?
7!
4!
7!/4!
7!/3!
7!/3!
Going back to the relay example from the lecture, what if instead of 5 people on the team, we had 7. Furthermore, this time we also need to pick a reserve player to be on stand-by. In how many ways can we accomplish that?
(4 positions to fulfill in the race)
7!/2!
7!/5!
7!/4!
7!/3!
7!/2!
Imagine you were asked to order a 3-tier cake for your best friend’ s wedding. They asked you to get a cake with a variety of flavors, so you decide to order different filling for each tier. The pastry shop you contacted offers 5 different fillings, so you want to know how many distinct options you have for the cake.
5!/3!
5!/2!
2!/5!
3!/5!
5!/2!
What do Combinations represent?
the number of different ways we can pick certain elements of a set
Do Variations take into account double counting elements?
No
Do Combinations take into account double counting elements?
Yes
All the different permutations of a single combination are different variations
In Combinations is the order relevent?
No
Example: Alex, Sarah, Dave
How many variations can you have?
How many combinations?
6 variations - why? Pn = n!
1 Combination -
Any of the 6 permutations we showed is a different variation, but NOT a different combination
6 Permutations = P(3) = 6
120 Combinations = C10,3 = 120
720 Variations = V10,3
What is the formula for Combinations without Repetition ?
What is the number of combinations for choosing p-many elements out of a sample space of n elements?
C = V / P
C = number of variations / number of permutations
C = n! / p! * (n - p)!
Imagine you are on a trip to Paris and decide to try some of their famous macaroons. The bakery you go to offers a different size “variety” packs, where you get to choose 3, 5 or 8 macaroons. The only requirement is that they all be different flavors. How many different 3-macaroon packs can you get, considering there are 8 distinct flavors.
8!/(3!5!)
8!/3!
8!/5!
3!/8!
8!/(3!5!)
Now imagine you want to get the medium pack which contains 5 macaroons instead of 3. How many different possible packs can you make?
8!/5!
8!/(5!3!)
8!/3!
5!/8!
8!/(5!3!)
Now imagine the same scenario but this time you want the large box of 8 macaroons. How many different variety packs can you get?
Undefined because we get 0! in the denominator of the formula.
8!(3!5!)
0
1
1
What are Symmetry of Combinations?
We can pick p-many elements in as many ways as we can pick n minus p elements
What is the formula for Combinations with repetition?
C bar = (n + p -1)! / (n -1)! * p!
Can picking more element lead to fewer combinations?
Yes
You are going on a pick nick. You have 6 pieces of fruit. However, our basket only carries 4. How many combinations do you have?
15
C 6,4 = 15
Picking 4 fruits out of 6. What are the two possible ways of choosing this combination?
Picking 4 fruits out of 6 is the same as choosing 2 fruits that will be left out
We can pick p-many elements in as many ways as we can pick n minus p elements
C n = C n
p n - p
When do we use Symmetry of Combinations?
To simplify calculations
What are Combinations of Separate Sample Spaces?
A combination can be a mixture of different small, individual events
You are developing FB ads. You have 3 different Post Descriptions, 5 thumbnails, 3 headings and 2 button options. How many different ads would you have to generate to make sure you’ve tried all possabilities?
90
3 x 5 x 3 x 2
How many different burger menus can we order from a McDonald’s Restaurant if we have a choice of 8 burgers, 3 sizes of fries and 5 different drinks, assuming a menu consist of a burger, some fries and a drink?
835
8! 3! 5!
8!/(3!5!)
8*5^3
835
We use Permutations with Variations when…?
the order is crucial
What are the two Types of Variations and Combinations?
Ones with and without repetition
What are factorials?
the product of an integer and all the integers below it;
What does 0! equal?
0! = 1
