Example Counting Questions All taken from past Foundation Exams Martian Life Intelligent life has finally been discovered on Mars Upon further study linguistic researchers have determined several rules to which the Martian language adheres 1 The Martian alphabet is composed of three symbols a b and c 2 Each word in the language is a concatenation of four of these symbols 3 Each command in the language is composed of three words a How many distinct commands can be created if words in a single command can be repeated and two commands are identical only if the three words AND the order in which the words appear are identical Thus the commands aaca baaa aaca and baaa aaca aaca are two DIFFERENT commands Total of 12 symbols in a command For each of these symbols we have 3 choices without any restrictions These choices are independent of one another so the total number of commands we have is 312 b How many distinct commands can be created if word position does not affect meaning and a given word may appear at most once in a single command Thus abca bbac abbb and bbac abbb abca should NOT count as different commands and aaca baaa aaca is an INVALID command Since we are not allowed to repeat words and word order doesn t matter we are essentially choosing three words out of the a possible number of words Thus we must first figure out the possible number of words There are three choices for each of four symbols using the multiplication principle as we did in part a we have 34 81 possible Martian words Of these we can choose three to make a valid command Thus the total number of possible commands here is 81C3 81 80 79 6 85320 Counting Numbers Consider six digit numbers with all distinct digits that do NOT start with 0 Answer the following questions about these numbers Leave the answer in factorial form a How many such numbers are there b How many of these numbers contain a 3 but not 6 c How many of these numbers contain either 3 or 6 or both a There are 9 choices for the first digit and then 9 choices for the second digit 0 has been added as a choice 8 for the third 7 for the fourth 6 for the fifth and 5 for the sixth Total 9 9 8 7 6 5 9 9 4 136080 b We need to separate the counting into two categories 1 3 is the first digit 2 3 is NOT the first digit For the first category we have one choice for the first digit followed by 8 choices for the second digit not 3 or 6 7 choices for the third digit 6 choices for the fourth digit 5 choices for the fifth digit and 4 choices for hte sixth digit Total 8 7 6 5 4 8 3 For the second category we have 7 choices for the first digit not 0 3 or 6 now we must guarantee that a 3 is picked There are five PLACES to place the 3 For the remaining 4 digits we have 7 choices 6 choices 5 choices and 4 choices respectively for each of these To see this imagine the 3 was placed 2nd Then for the third digit you could choose any number except for the first digit 3 and 6 Similarly no matter where the 3 is placed you always have 7 choices for the next placed digit then 6 etc Total 7 5 7 6 5 4 35 7 3 The total of both of these categories is 8 3 35 7 3 36120 c Count the number of numbers that contain neither There are 7 choices for the first digit not 0 3 or 6 7 choices for the second digit 6 choices for the third digit 5 choices for the fourth digit 4 choices for the fifth digit and 3 choices for the sixth digit Total 7 7 6 5 4 3 7 7 2 Now the answer to the question given is the value above subtracted from the answer in part a Thus this answer is 9 9 4 7 7 2 118440 Permutations a How many distinguishable ways are there to rearrange the letters in the word COMBINATORICS b How many distinguishable arrangements are possible with the restriction that all vowels A I O are always grouped together to form a contiguous block c How many distinguishable arrangements are possible with the restriction that all vowels are alphabetically ordered and all consonants are alphabetically ordered For example BACICINOONRST is one such arrangement a There are 13 letters in the word COMBINATORICS including three duplicates two C s two O s and two I s So the total number of arrangements is 13 2 3 b If all five vowels are consecutive they form a single block Then first we need to count permutations of the consonants and one block of vowels Given eight consonants with one duplicate two C s we have 9 2 But every arrangement of consonants and the block of vowels can be combined with any permutation of vowels inside the block For five vowels including two duplicates we have 5 2 2 possible permutations inside the block Then by the product rule we get the answer 9 5 2 3 c Any arrangement is completely defined by specifying which 5 of 13 positions should be occupied by vowels or equivalently which 8 out of 13 should be occupied by consonants So we just need to count the number of ways to select 8 positions out of 13 or equivalently 5 positions out of 13 that is 13 8 5 Given any such selection both consonants and vowels are distributed alphabetically into assigned slots More Permutations How many 6 letter words can be formed by ordering the letters ABCDEF if A appears before C and E appears before C Under given restrictions there are two possible arrangements for letters A C and E between themselves either A appears before E or E before A i e AEC or EAC so we have two choices for this task After that we can choose 3 slots to place letters A C and E out of 6 possible in a 6 letter word If the order of A C and E is fixed we count selections C 6 3 After we fill 3 slots with letters A C and E we can make 3 permutations of the letters B D and F using remaining 3 slots By the product rule the total number of ordering will be 2 C 6 3 3 2 6 5 4 240 Even More Permutations a How many permutations of the word FOUNDATION are there 10 2 2 since there are 10 letters total with 2Os and 2Ns b A valid password is 5 letters long and uses a selection of the letters in the word FOUNDATION Thus a password may have at most 2 N s at most 2 O s and at most 1 copy of each of the other letters A D …
View Full Document
Unlocking...