Transcript Counting
COUNTING By Patrick, Andrew, Jared & Jonathan COUNTING Counting is the study of the enumeration of discrete, finite sets (“counting objects”) Ex. If there are 5 symbols with which we are given, to create a 4 symbol license plate, how many plates can we make? (Symbols can be repeated) (5)(5)(5)(5) = 625 MULTIPLICATION PRINCIPLE FOR COUNTING If an activity can be performed as a sequence of “k” independent steps, and step “i” can be accomplished in “ni” ways, than the entire activity can be performed in (n1)(n2)(n3)…(nk) ways. When can this be used? Ex. If we must create a license plate in which two of the symbols can be of a given set of 6 letters or two of the symbols can be of a given set of 5 numbers, how many unique plates can we make? (5)(5) + (6)(6) = 61 ADDITION PRINCIPLE FOR COUNTING If an activity can be divided into “k” disjoint subsets of activities (separate activities), and the ith of these sets contains ni elements, than total number is n1+ n2+ n3+….+ nk. PERMUTATION A permutation of “n” distinct objects x1, x2, x3…xn is any ordering of “n” objects. P(n,r) = n!/(n-r)! where one chooses “r” items from “n” items (order matters). Where does it come from? EXAMPLE If there are 16 baseball players who need to be put into a 3 player batting order, how many different batting orders are possible? P(16,3) = 16!/(16-3)! = 16!/13! = 3,360. There are 3,360 unique batting orders which are possible. COMBINATIONS Combinations are Permutations where the order of the objects being counted doesn’t matter. For example: 1, 2, and 3 can be arranged in 6 different ways if order matters but only 1 way if order does matter: Matters 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 Doesn’t Matter 1,2,3 COMBINATIONS CONT’D The table from the previous page shows that for a set of (1,2,3) if you want to order the numbers with a Permutation you will get 6 outputs, but with a Combination, you only receive 1. This shows that there are 6 times as many Permutations than combinations for this set. This works for any P(n,r) and C(n,r). Since there are 3 digits, you divide the number of permutations by another 3! which is equal to 6. COMBINATIONS EQUATION To reach this conclusion we reduce the formula by how many ways the objects could be in order which accounts for the r! on the bottom. P(n,r) = C(n,r)*r! COMBINATIONS WITH REPETITION Combinations with repetition are also referred to as “Multichoose” problems. The equation is How does it work? MULTICHOOSE Let’s say you have 5 different flavors of ice cream, and you can have 3 scoops. Your 3 scoops can be any flavor, with repetition, how many different combinations of ice cream scoops can you have? We will say the flavors are banana, chocolate, lemon, strawberry and vanilla. MULTICHOOSE CONT’D Think about the ice cream being in containers, you could say "skip the first, then 3 scoops, then skip the next 3 containers" and you will end up with 3 scoops of chocolate! So there are r + (n-1) positions, and we want to choose r of them to have circles. EXAMPLE If we refer back to the previous problem about batting orders, we will take the same number of players, 16, but this time 3 players will be picked to be team captains. How many ways can they be chosen in groups of 3? C(16,3) = 16!/3!(16-3)! = 16!/3!(13)! = 16*15*14/3*2*1 = 560 In this case, there are only 560 ways that players can be chosen, because order does not matter. IDENTITY 130 Identity: For 0 ≤ k ≤ n k(nk)=n(n-1k-1) Question: How many ways can we create a size k committee of students from a class of n students, where one of the committee members is designated as the chair? IDENTITY 130 CONTINUED There are (nk) ways to choose the committee, then k ways to select a chair. Therefore, there are k(nk) possible outcomes. First, select the chair from the class of n students. Then, from the remaining n-1 students, pick the remaining k-1 members. This can be done n(n-1k-1) ways. IDENTITY 131 We have a question we could ask: How many ways can we make a committee (of any size) from a class of students of n students, where one of them is designated as the chair. Starting this we will ask how many committees we could make. This would be the same as (nk). We must then factor in the people who may be the chair. This is k. IDENTITY 131 CONTINUED Another way to solve the same thing: We see that there are n students to be the chair of committees, so we select the chair of each subcommittee out of n students. There are now n-1 students remaining. It follows that there are 2n-1 ways of filling the remaining committees. We now have n*2n-1 ways of choosing different ways of choosing committees. If we look at the identity we were given, this helps show that the answer we got is correct. THANK YOU TO OUR MENTOR Greg Warrington! REFERENCES SLIDE! Proofs That Really Count; Benjamin/Quinn Introduction to Discrete Mathematics, Burgmeier/Kost HOMEWORK PROBLEMS We have a baseball team made up of 6 players. A. How many different 3 person batting orders can we have? (order matters, Permutation) B. How many different 2 person groups of team captains can we have? (order doesn’t matter, Combination)