Counting with And and Or Background Let s deal with the two connectives and and or They present the greatest challenge to resolving counting issues Before we go any further here s the secret The word and usually implies multiplication principle The word or usually tells us that there is an addition of results after we have used the multiplication principle more than once The word usually is included to cover the obscure possibility that these secrets are not universally true Recall the Example How many 4 digit codes can be created from this set a b c x y z if each character can only be used once The word code implies a permutation process if replacement is not allowed Words license plates ID numbers bank PINs and many other instances involve ordered strings another name for a code My usual example of why this must be true If the traffic camera takes a picture of the license plate ABC 123 running a red light all the people with plates using A B C 1 2 and 3 will be thoroughly upset to get a ticket also Only one of them deserves it Sort of like Mom sending everyone to their rooms because someone broke her favorite lamp Using And with Or We counted before that there are P 9 4 3024 possible permutations of this set Now let s constrain our thinking How many permutations can be created from the set when the permutation must have an a as its first letter This actually simplifies the problem Since it is a permutation world once a is placed first that means we have only eight characters to fill in the remaining spaces So there are P 8 3 336 ways to place the other characters Now the multiplication principle works here in two ways The first is the placement of a in the first position There is exactly one 1 way to do it Then the remainder is placed according to the prevailing rules So in a very technical sense the calculation is 1 P 8 3 1 336 336 ways to complete the arrangement Let s modify the process again Now we require that the a be either at the beginning or at the end of the 4position code Hmmm Two different processes are considered successful We calculate both of them then add because or says we accept both results So we have 1 P 8 3 P 8 3 1 672 possibilities Another modification Let s require that the first letter be a b or the last character be a vowel where we accept y as a vowel Double hmmm What are the acceptable patterns They could be the following i All the codes looking like ii All the codes looking like iii All the codes looking like b There are 1 P 8 3 336 of them a There are P 8 3 1 336 of them y There are P 8 3 1 336 of them Arizona State University Department of Mathematics and Statistics 1 of 7 Counting with And and Or Whups Make that a triple hmmm We just triple counted some possibilities Notice that the b has possibilities within in it that includes the other two since b a and b y are both counted there So how can we fix this Let s try another approach The acceptable codes are below Read the as not i All the codes looking like ii All the codes looking like iii All the codes looking like b There are 1 P 8 3 336 of them b a There are 7 P 6 2 1 210 of them b y There are 7 P 6 2 1 210 of them The final step is to add these results since all are acceptable to us The final number of arrangements is 756 Let s do one where replacement is allowed For the most part codes do not restrict reuse of a symbol They are more likely to require the use of some specific kind of symbol Example My bank account has the following requirements for choosing a password At least 6 positions must include 1 number and 1 letter may use upper and lowercase letters and all special characters on the computer key board Now this is so open ended that it is impossible to count the number of codes possible Let s tone it down a little Here are the rules we will apply 1 Create a 6 position code with replacement 2 We may use the 26 letters of the alphabet both upper and lowercase so A and a are different 3 We may use the digits 4 We must use exactly one of the following somewhere in the code As complex as this seems it really isn t First five 5 positions are free We can use the 52 alphabetic characters and the digits freely So we have 62 characters to use for all 5 positions Since this is a code it must be a process where order matters for these positions So we have 625 possibilities already But we must place one of the special characters There are 7 of them Now we have 625 7 possibilities Finally the special character can be anywhere within the code You could handle this by creating by creating all possible placements Letting T represents the special character T T etc Then calculate each option and add them all However this is very unwieldy It is easier to realize that there are 6 places to put the special character All other characters arrange around it So the final count is 625 7 6 3 847757894 1010 Yikes We have so many possibilities the calculator can only approximate them 2 of 7 Arizona State University Department of Mathematics and Statistics Counting with And and Or This should make you feel a little better about someone breaking into your checking account However if you chose to spell your name and then use a special character all bets are off By the way if we change so that replacement is not allowed the only adjustment to our thinking is to replace 625 with P 62 5 The correct result then is a mere P 62 5 7 6 3 261385 1010 Committees and Slates Now let s get into some of the concepts related to committees This genre of problem deals with composing arrangements when we don t care about order and place restrictions created by the connective or Logically they are similar to PIN problems in the math but they use combination rather than permutations Slates such as political election lists on the other hand do concern themselves about order Here s a very typical example Club 55 28 has a very strict membership policy It can have only exactly 55 members of which 28 must be men The men insist on being in the majority In the bylaws committees must be similarly constituted It is worth noting that when a committee is formed it usually has no internal structure After it is formed the members elect a chair secretary etc from among themselves Let s do three …