Example Counting Questions(All taken from past Foundation Exams)Martian LifeIntelligent life has finally been discovered on Mars! Uponfurther study, linguistic researchers have determined severalrules 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 thesesymbols.3) Each command in the language is composed of three words.a) How many distinct commands can be created if words in asingle command can be repeated and two commands areidentical only if the three words AND the order in which thewords appear are identical? (Thus, the commands "aaca baaaaaca" and "baaa aaca aaca" are two DIFFERENTcommands.)Total of 12 symbols in a command. For each of these symbols, wehave 3 choices without any restrictions. These choices areindependent of one another, so the total number of commandswe have is 312.b) How many distinct commands can be created if wordposition does not affect meaning and a given word may appearat most once in a single command? (Thus, "abca bbac abbb"and "bbac abbb abca" should NOT count as differentcommands, and "aaca baaa aaca" is an INVALID command.)Since we are not allowed to repeat words and word order doesn'tmatter, we are essentially choosing three words out of the apossible number of words. Thus, we must first figure out thepossible number of words. There are three choices for each offour symbols, using the multiplication principle as we did in parta, we have 34 = 81 possible Martian words. Of these, we canchoose three to make a valid command. Thus, the total numberof possible commands here is 81C3 = (81)(80)(79)/6 = 85320Counting NumbersConsider six-digit numbers with all distinct digits that do NOTstart with 0. Answer the following questions about thesenumbers. 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 forthe second digit (0 has been added as a choice), 8 for the third, 7for 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 digitFor the first category, we have one choice for the first digit,followed by 8 choices for the second digit (not 3 or 6), 7 choicesfor the third digit, 6 choices for the fourth digit, 5 choices for thefifth 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. Thereare five PLACES to place the 3. For the remaining 4 digits, wehave 7 choices, 6 choices, 5 choices and 4 choices, respectivelyfor each of these. (To see this, imagine the 3 was placed 2nd.Then for the third digit you could choose any number except forthe 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! = 36120c) Count the number of numbers that contain neither:There are 7 choices for the first digit(not 0,3 or 6), 7 choices forthe second digit, 6 choices for the third digit, 5 choices for thefourth digit, 4 choices for the fifth digit and 3 choices for thesixth digit. Total = (7)(7)(6)(5)(4)(3) = 7(7!)/2!Now, the answer to the question given is the value abovesubtracted from the answer in part a. Thus, this answer is9(9!)/4! - 7(7!)/2! = 118440.Permutationsa) How many distinguishable ways are there to rearrangethe letters in the word COMBINATORICS? b) How many distinguishable arrangements are possiblewith the restriction that all vowels (“A”, “I”, “O”) arealways 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. Thenfirst we need to count permutations of the consonants and one blockof vowels. Given eight consonants with one duplicate (two C’s), wehave 9!/2!. But every arrangement of consonants and the block ofvowels can be combined with any permutation of vowels inside theblock. For five vowels including two duplicates we have 5!/(2!)2possible permutations inside the block. Then by the product rule weget the answer: (9!5!)/(2!)3.c)Any arrangement is completely defined by specifyingwhich 5 of 13 positions should be occupied by vowels (orequivalently which 8 out of 13 should be occupied byconsonants). So we just need to count the number of waysto select 8 positions out of 13 (or equivalently 5 positionsout of 13), that is 13!/(8!5!). Given any such selection, bothconsonants and vowels are distributed alphabetically intoassigned slots. More PermutationsHow many 6-letter words can be formed by ordering the lettersABCDEF if A appears before C and E appears before C? Under given restrictions there are two possible arrangements forletters A, C and E between themselves: either A appears beforeE , or E before A, i.e. AEC or EAC, so we have two choices forthis task. After that we can choose 3 slots to place letters A, Cand E out of 6 possible in a 6-letter word. If the order of A, Cand E is fixed, we count selections C (6, 3). After we fill 3 slotswith letters A, C and E, we can make 3! permutations of theletters B, D and F using remaining 3 slots. By the product rulethe total number of ordering will be 2C(6, 3)3!=2654=240.Even More Permutationsa) How many permutations of the word FOUNDATION arethere?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 theletters in the word FOUNDATION. (Thus, a
View Full Document
Unlocking...