Let s go through a problem that utilizes both of these rules Here are the rules for a valid phone number 1 The first three digits must all be different 2 The first digit can not be a 1 3 If the first digit is a 5 the last four digits must all be the same Based on our rules we must group our phone numbers into two separate groups A All numbers that start with 5 B All numbers that do NOT start with 5 First we will count all the phone numbers that fit in group A 1 9 8 10 1 1 1 For the first number we have 1 choice 5 For the second number we have 9 choices everything but 5 For the third number we have 8 choices For the fourth number we have all 10 choices but for the rest we only have 1 choice based on our rules Thus we have 1x9x8x10x1x1x1 720 phone numbers that start with 5 Now let s count the phone numbers that do not start with 5 8 9 8 10 10 10 10 for a total of 8x9x8x10x10x10x10 5760000 phone numbers that do not start with 5 Using the sum rule we add this to our other value to get a total of 5 760 720 total possible phone numbers under the given rules Here is a quick problem for you guys How many 3 letter words can you form that have two consonants and a vowel Permutations A permutation of objects is simply an arrangement of those objects A common example of permutations deals with words How many words can you form out of the letters A B C and D without repeating a letter Essentially the question boils down to how many ways can you order a set of objects In this case we know we have four choices for the first object Once we have made that choice it is clear that we will always have three choices for the next object In particular we find the following 4 x 3 x 2 x 1 24 possible permutations In general imagine the number of ways to permute n objects Using the same process as above we find n x n 1 x 2 x 1 n possible permutations Note For those of you unfamiliar with the notation it is read as factorial n is simply defined as the product of all the positive integers in between 1 and n inclusive Now consider the following problem Given n distinct objects how many permutations are there of r of those objects where 1 r n Using the product rule as before we find n x n 1 x n k 1 n n k possible permutations Now consider a situation where you are permuting objects where some of those objects are indiscernible For example how many permutations are there of the word BEER At first we would say 24 but the problem is that we can not tell the difference between the two E s To look at the problem more closely imagine giving subscripts to the 2 Es to discern them and THEN listing out the permutations as follows BEER BERE BREE EBER EBRE EEBR EERB ERBE EREB RBEE REBE REEB B E1 E2 R B E1 R E2 B R E1 E2 E1 B E2 R E1 B R E2 E1 E2 B R E1 E2 R B E1 R B E2 E1 R E2 B R B E1 E2 R E1 B E2 R E 1 E2 B B E2 E1 R B E2 R E1 B R E2 E1 E2 B E1 R E2 B R E1 E2 E1 B R E2 E1 R B E2 R B E1 E2 R E1 B R B E2 E1 R E2 B E1 R E 2 E1 B Thus we see that there are really 12 distinct permutations of BEER 12 pack 12 permutations coincidence Hmmm In particular for every distinct permutation of BEER there are 2 possibilities listed on the RHS with all the permutations assuming distinct E s In fact we can see that if we had a word with 3 E s there would be six possibilities listed 1 for each permutation of the 3 E s assuming that they are distinct In general the number of permutations of n letters where the number of repetitions of each letter are n1 n2 n3 nk is n n1 n2 nk The reasoning behind this is the following If we assume that each of the n letters is distinct ie if all the similar letters had subscripts to distinguish them then n is the correct answer But as we saw in our example before using this method of counting we count the same word multiple times Our goal is to figure out HOW many times we count each word If letter 1 appears n1 times then we can rearrange each of those n1 characters in exactly n1 ways keeping our original permutation unchanged For each of those n1 arrangements we have the following If letter 2 appears n2 times then we can rearrange each of those n2 characters in exactly n2 ways keeping our original permutation unchanged Since these are independent events so to speak we use the product rule to calculate the total number of times we have recounted the same permutation The final answer ends up becoming the product of all the frequencies of all the letters or more mathematically n1 n2 nk Thus to get the true number of permutations with repeats you must divide n by the value above Example of a Combinatorial Proof Let n 2k where k is a positive integer In this situation it turns out that n 2k is an integer We can actually prove this using a combinatorial argument which goes as follows Consider counting the number of permutations of the n symbols x1 x1 x2 x2 xk xk Using the formula derived above we calculate this value to be n 2 k But we know that 2 2 this the final value is n 2k which MUST BE an integer since the number of permutations of a group of letters is ALWAYS an integer Combinations Now consider the following two questions 1 Given a set of n objects how many total possible subsets can you have of those objects A subset simply is any group with a size in between 0 and n inclusive of the n objects The order in which the members of the subset are picked does not matter 2 Given a set of n objects how many subsets of size k can you have of those objects For the first question we can view creating a subset of a group of n objects in the following manner First decide whether or not element 1 is in the subset Next decide whether or not element 2 is in the subset Each of these choices is independent from each of the other choices and for each choice we have two options Thus we can use the product rule to count the total number of possible subsets 2 x 2 x …
View Full Document
Unlocking...