Counting and Multiplication Rule
What is the multiplication rule in counting?
What is multiplying the number of choices for each step to get the total number of outcomes?
What is an R-permutation?
What is an arrangement of rrr elements from nnn distinct items?
What is an r-combination?
What is a selection of rrr elements from nnn distinct items where order doesn’t matter?
What is an r-combination with repetition?
What is a selection of r elements from n items where items can be repeated?
Which principle states that if there are more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon?
What is the pigeonhole principle?
If there are 4 types of sandwiches and 3 types of drinks, how many meal combinations can you make?
What is 12?
How many ways can you arrange 3 out of 5 letters?
What is P(5,3)P(5, 3)P(5,3) or 60?
What is the formula for r-combinations?
What is n!/(n-r)!r!
What formula is used for r-combinations with repetition?
What is (n+r-1) choose r
Prove that if 6 people are in a room, at least two of them have their birthdays in the same month.
What is by the pigeonhole principle (12 months, 6 people)?
In how many ways can you arrange 5 books on a shelf?
What is 5 factorial or 120?
What formula is used to compute r-permutations?
What is n!/(n-r)!
How many ways can you choose 2 out of 5 items?
What is 10?
How many ways can you choose 3 candies from 5 types of candies if you can pick the same type more than once?
What is 35?
The method of proofs we have been using in class so far.
What is direct proof?
If a menu offers 5 appetizers, 3 main courses, and 4 desserts, how many meal combinations can be chosen?
What is 60?
How many ways can you select and arrange 4 students from a group of 7?
What is P(7,4)P(7, 4)P(7,4) or 840?
How many ways can a 3-member committee be chosen from 6 people?
What is 20?
How many ways can 6 identical apples be distributed among 3 people?
What is 28?
Using a counting proof, how can you show that
nCr = nCn-r
What is by considering choosing rrr objects out of nnn is the same as leaving n−rn-rn−r behind?
A lock requires a 4-digit code. How many possible codes are there if digits can be repeated?
What is 10,000?
If you select 3 numbers from 1 to 6 to create a permutation, how many permutations are possible?
What is 120?
A group of 10 people needs to form a 4-member team. How many teams can be formed?
What is 210?
If you can select 5 items from 4 categories with repetition allowed, how many different selections are possible?
What is 56?
Prove that the number of subsets of a set with n elements is 2n2^n2n.
What is a counting proof using binary representation of subsets?