Solutions for Challenging Counting Problems

Solutions for Challenging Counting Problems Counting can seem like an easy task to perform. As we go deeper into the area of mathematics known as combinatorics, we realize that we come across some large numbers. Since the factorial shows up so often, and a number such as 10! is greater than three million, counting problems can get complicated very quickly if we attempt to list out all of the possibilities. Sometimes when we consider all of the possibilities that our counting problems can take on, its easier to think through the underlying principles of the problem. This strategy can take much less time than trying brute force to list out a number of combinations or permutations. The question How many ways can something be done? is a different question entirely from What are the ways that something can be done? We will see this idea at work in the following set of challenging counting problems. The following set of questions involves the word TRIANGLE. Note that there are a total of eight letters. Let it be understood that the vowels of the word TRIANGLE are AEI, and the consonants of the word TRIANGLE are LGNRT. For a real challenge, before reading further check out a version of these problems without solutions. The Problems How many ways can the letters of the word TRIANGLE be arranged?Solution: Here there are a total of eight choices for the first letter, seven for the second, six for the third, and so on. By the multiplication principle we multiply for a total of 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 8! 40,320 different ways.How many ways can the letters of the word TRIANGLE be arranged if the first three letters must be RAN (in that exact order)?Solution: The first three letters have been chosen for us, leaving us five letters. After RAN we have five choices for the next letter followed by four, then three, then two then one. By the multiplication principle, there are 5 x 4 x 3 x 2 x 1 5! 120 ways to arrange the letters in a specified way.How many ways can the letters of the word TRIANGLE be arranged if the first three letters must be RAN (in any order)?Solution: Look at this as two independent tasks: the first arranging the letters RAN, and the second arranging the other five letters. There are 3! 6 wa ys to arrange RAN and 5! Ways to arrange the other five letters. So there are a total of 3! x 5! 720 ways to arrange the letters of TRIANGLE as specified. How many ways can the letters of the word TRIANGLE be arranged if the first three letters must be RAN (in any order) and the last letter must be a vowel?Solution: Look at this as three tasks: the first arranging the letters RAN, the second choosing one vowel out of I and E, and the third arranging the other four letters. There are 3! 6 ways to arrange RAN, 2 ways to choose a vowel from the remaining letters and 4! Ways to arrange the other four letters. So there are a total of 3! X 2 x 4! 288 ways to arrange the letters of TRIANGLE as specified.How many ways can the letters of the word TRIANGLE be arranged if the first three letters must be RAN (in any order) and the next three letters must be TRI (in any order)?Solution: Again we have three tasks: the first arranging the letters RAN, the second arranging the letters TRI, and the third arranging the other two letters. There are 3! 6 ways to arrange RAN, 3! ways to arrange TRI and two ways to arrange the other letters. So there are a total of 3! x 3! X 2 72 ways to arrange the letters of TRIANGLE as indicated. How many different ways can the letters of the word TRIANGLE be arranged if the order and the placement of the vowels IAE cannot be changed?Solution: The three vowels must be kept in the same order. Now there are a total of five consonants to arrange. This can be done in 5! 120 ways.How many different ways can the letters of the word TRIANGLE be arranged if the order of the vowels IAE cannot be changed, though their placement may (IAETRNGL and TRIANGEL are acceptable but EIATRNGL and TRIENGLA are not)?Solution: This is best thought of in two steps. Step one is to choose the places that the vowels go. Here we are picking three places out of eight, and the order that we do this is not important. This is a combination and there are a total of C(8,3) 56 ways to perform this step. The remaining five letters may be arranged in 5! 120 ways. This gives a total of 56 x 120 6720 arrangements.How many different ways can the letters of the word TRIANGLE be arranged if the order of the vowels IAE can be changed, though their placement may not?Solution: This is really the same thing as #4 above, but with different letters. We arrange three letters in 3! 6 ways and the other five letters in 5! 120 ways. The total number of ways for this arrangement is 6 x 120 720. How many different ways can six letters of the word TRIANGLE be arranged?Solution: Since we are talking about an arrangement, this is a permutation and there are a total of P( 8, 6) 8!/2! 20,160 ways.How many different ways can six letters of the word TRIANGLE be arranged if there must be an equal number of vowels and consonants?Solution: There is only one way to select the vowels we are going to place. Choosing the consonants can be done in C(5, 3) 10 ways. There are then 6! ways to arrange the six letters. Multiply these numbers together for the result of 7200.How many different ways can six letters of the word TRIANGLE be arranged if there must be at least one consonant?Solution: Every arrangement of six letters satisfies the conditions, so there are P(8, 6) 20,160 ways.How many different ways can six letters of the word TRIANGLE be arranged if the vowels must alternate with consonants?Solution: There are two possibilities, the first letter is a vowel or the first letter is a consonant. If the first letter is a vowel we have three choices, followed by five for a consonant, two for a second vowel, four for a second consonant, one for the last vowel and three for the last consonant. We multiply this to obtain 3 x 5 x 2 x 4 x 1 x 3 360. By symmetry arguments, there are the same number of arrangements that start with a consonant. This gives a total of 720 arrangements. How many different sets of four letters can be formed from the word TRIANGLE?Solution: Since we are talking about a set of four letters from a total of eight, the order is not important. We need to calculate the combination C(8, 4) 70.How many different sets of four letters can be formed from the word TRIANGLE that has two vowels and two consonants?Solution: Here we are forming our set in two steps. There are C(3, 2) 3 ways to choose two vowels from a total of 3. There are C(5, 2) 10 ways to choose to consonants from the five available. This gives a total of 3x10 30 sets possible.How many different sets of four letters can be formed from the word TRIANGLE if we want at least one vowel?Solution: This can be calculated as follows: The number of sets of four with one vowel is C(3, 1) x C( 5, 3) 30.The number of sets of four with two vowels is C(3, 2) x C( 5, 2) 30.The number of sets of four with three vowels is C(3, 3) x C( 5, 1) 5. This gives a total of 65 different sets. Alternately we could calculate that there are 70 ways to form a set of any four letters, and subtract the C(5, 4) 5 ways of obtaining a set with no vowels.