A recent question illustrates well the different ways to solve problems in combinatorics. We’ll see an easy way, another easy way, and a … less suitable … way to solve a set of problems.
Alphabetical order, and beyond
It came from Joe, in mid-May:
Background: I’m a year 11 student doing extension 1 maths (Sydney) and I’m having trouble wrapping my head around some of these concepts.
In the question:
Consider the word MATHEMATICS, how many arrangements using all letters are there where all the vowels are in alphabetical order.
I understand this: I did 4!/2! = 12, Therefore 1/12 is in the correct orientation. 1/12 x 11! / 2! 2! 2! = 415800
What I don’t get is questions like:
How many arrangements are there if all M’s were to the left of all A’s.
Is this the same concept where I treat the letters like a ‘word’??
I’m also curious about how to do 16 e and f in the question attached. In the answers they went through every possible case, but is there a nice clean way to do it?
Thank you
We dealt with problems of this type in Arranging Letters with Duplicates, 6 years ago. The central formula, used here, is that the number of permutations of n items, \(n_1\) of one kind, \(n_2\) of another, and so on, is $$\frac{n!}{n_1!n_2!\cdots n_k!}$$ (Since \(1!=1\), we can ignore letters that occur only once.)
For example, the total number of ways to arrange the letters of GUMTREE (problem 16a), namely EEGMRTU, with 7 letters, 2 of which are E, is \(\frac{7!}{2!}=\frac{5040}{2}=2520\). In the old post, some questions added a condition involving consecutive copies of the same letter; this question has more interesting restrictions.
I answered, starting with the problem he had already solved:
Hi, Joe.
Consider the word MATHEMATICS, how many arrangements using all letters are there where all the vowels are in alphabetical order.
Your method is a nice one, and I get the same answer by a different method — one which, it turns out, can be applied easily to all the other three problems you ask about!
Joe’s method was to recognize that the four vowels AEAI can be arranged in \(\frac{4!}{2!}=\frac{24}{2}=12\) ways, so that if you were to list all of the \(\frac{11!}{2!2!2!}=\frac{39,916,800}{8}=4,989,600\) arrangements of all 11 of the letters in MATHEMATICS (AACEHIMMSTT), you would find sets of 12 with the vowels in the same places, only 1 of which has them in alphabetical order (AAEI). So dividing that total by 12 answers the question, \(4,989,600\div12=415,800\).
An alternative method
That’s a good solution, likely inspired by the way we derive the general formula.
Here is what I did for this one:
First, remove the vowels from MATHEMATICS, leaving CHMMSTT. This can be arranged in 7!/(2!2!) ways. For example, one is
S H M T M T C
Now choose 7 of the 11 positions in which to put these letters; this can be done in 11C7 = 11!/(7!4!) ways. One is
_ S H M _ T M _ _ T C
Now put the vowels in the remaining spaces, in the required order, AAEI:
A S H M A T M E I T C
This can be done in only one way. So the total number of ways to make an arrangement is
7!/(2!2!) * 11!/(7!4!) = 11!/(2!2!4!) = 415,800
So my procedure for making an arrangement was to first arrange the 7 consonants; then choose 7 of the 11 locations into which to place them, and then to place the 4 vowels in the one allowed order. This could be thought of in other orders, too, such as first choosing 7 places for consonants, e.g.
_ _ _ _ _ _ _ _ _ _ _ V C C C V C C V V C C
(leaving the rest for consonants) and then arranging each set of letters into its prechosen locations.
Inventing such a process for counting is a common first step; Joe’s process was one of division (grouping arrangements into sets of 12 and taking one) rather than of multiplication (making a series of arrangements of parts of the set). (For examples of creating a process, see Permutations and Combinations: Undercounts and Overcounts.)
So far, I’ve only shown an alternative for the correct work Joe had already done. But that turned out to be a good hint for all the question he had been unable to do!
Try doing something similar for the others:
How many arrangements are there if all M’s were to the left of all A’s?
Find how many arrangements there are of the letters of the word GUMTREE if …
(e) the M is somewhere to the left of both Es, and the U is somewhere between them.
(f) the G is somewhere to the left of the U, and the M is somewhere to the right of the U.
What answers did the source give for these? I’d like to see their method for comparison.
Solving the problems he didn’t ask about
While we wait for a response, let’s look at the other problems in the set too, to see if they’re interesting.
We already saw the answer to 16a. The next is
16b: … the Es are together.
Here, we can imagine gluing the E’s in GUMTR[EE] together so that we have only 6 letters, all of which are different; so there are \(6!=720\) arrangements.
16c: … the Es are separated by 1, 2, 3, 4, or 5 letters.
This can be done in many ways; to keep it similar to our central idea, we can first choose places for the E’s, and then place the remaining letters. I’ll just do the 1-letter version. If the E’s are separated by one letter, then we want to choose three consecutive places out of the 7. The first of them will be in position 1, 2, 3, 4, or 5:
_ _ _ _ _ _ _ 1 2 3 4 5
This will give us
E _ E _ _ _ _ _ E _ E _ _ _ _ _ E _ E _ _ _ _ _ E _ E _ _ _ _ _ E _ E
So there are 5 ways to place the E’s, and \(5!=120\) ways to fill the remaining 5 places, for a total of \(5\times120=600\) arrangements.
We can do the same for other gap sizes. (If there are 5 letters separating the E’s, then there is only one way to place them, namely the first and last places.)
16d: … the G is somewhere between the two Es.
This is a little different, but we can treat it much as we did the vowels:
_ E G _ E _ _
Wherever the E, G, E are placed, they must be in that order; so we just need to choose three places for these, place them in their unique order, and then place the remaining 4 letters:
_ _ _ _ _ _ _ X X X
$$_7\mathrm{C}_3\times4!=\frac{7!}{3!4!}\times4!=\frac{7!}{3!}=840$$
He solves the problems he did ask about
Joe replied:
Doctor Peterson, thank you so much!!!!! I’ve never been taught this method and I can’t believe it’s taken me so long to find it …
Here are my attempts at the remaining questions.
How many arrangements are there if all M’s were to the left of all A’s
–> I took out MMAA, so that I had THETICS remaining. My answer was 11C7 * 7!/2! = 831600
For the GUMTREE questions I did:
(e) I took out MEUE so that I had GTR left –> My answer was 7C3 * 3! = 210
(f) I took out GUM so that I had TREE left –> 7C4 x 4!/2 = 420
The first of these is very much like the vowels, as MMAA must be in that one order. One of the remaining letters is doubled, so we have $$_{11}\mathrm{C}_7\times\frac{7!}{2!}=\frac{11!}{7!4!}\times\frac{7!}{2!}=330\times2520=831,600$$
This could also be solved by his original method, dividing the total number of arrangements by the number of arrangements of MMAA: $$\frac{11!}{2!2!2!}\div\frac{4!}{2!2!}=4,989,600\div6=831,600$$
The other two are:
16 (e) the M is somewhere to the left of both Es, and the U is somewhere between them.
This looks like
_ M E _ U _ E
so we choose 4 places for those letters, and fill in the other 3, GTR: $$_{7}\mathrm{C}_4\times3!=\frac{7!}{4!3!}\times3!=35\times6=210$$
Using his method, we would have $$\frac{7!}{2!}\div\frac{4!}{2!}=2520\div12=210$$
16 (f) the G is somewhere to the left of the U, and the M is somewhere to the right of the U.
This looks like
_ _ G _ U _ M
so we choose 3 places for those letters, and fill in the other 4, TREE, with one letter doubled: $$_{7}\mathrm{C}_3\times\frac{4!}{2!}=\frac{7!}{3!4!}\times\frac{4!}{2!}=35\times12=420$$
Using his method, we would have $$\frac{7!}{2!}\div3!=2520\div6=420$$
(I hadn’t considered using his own method at the time, because he said the answers were complicated …)
I answered:
Very good.
How many arrangements are there if all M’s were to the left of all A’s
–> I took out MMAA, so that i had THETICS remaining. My answer was 11C7 * 7!/2! = 831600
I did the same thing, and simplified to 11!/(2!4!), giving the same result. (At first I thought you were wrong because I made a mistake in the calculation.)
For the GUMTREE questions i did:
(e) I took out MEUE so that i had GTR left –> My answer was 7C3 * 3! = 210
So did I.
(f) I took out GUM so that i had TREE left –> 7C4 x 4!/2 = 420
Again, correct.
You may notice that his work looks a little different from mine; I chose places for the specified letters, while he chose places for the additional letters. It amounts to the same thing, so there was no need to disagree!
The book’s solutions
Joe also supplied the book’s answers:
You can take a look at the very very long worked solutions that were in the textbook .
Also are there similar types of questions that need a different method that might trip me up in an exam? My school loves to give questions made to trick students.
Frankly, I am amazed. The method I showed, which is very natural, fits all these problems so well, I would have thought they were designed specifically to teach this method, or something similar. Instead, they have shown a largely brute-force approach using multiple cases. If they had room (such solutions at the end of a textbook typically are crammed into a small space), they could at least have shown their work in a more structured way, to make it easier to follow.
I tried to understand their method for 16(f), but was unable to make sense of their calculations. (This often happens when a student just shows their calculations without explanation.) I’ll do it as I would, if I chose to use these cases:
We must place G, U, and M in that order … G … U … M … .
- Case 1 (GUM): If GUM are all adjacent, then we are arranging 5 items, [GUM], T, R, E, E, two of which are identical, making $$\frac{5!}{2!}=60\text{ ways}.$$
- Case 2 (G_UM): If there is one extra letter inside GUM, then I might choose the number of blanks to go before [G_UM] (4 ways: 0, 1, 2, 3), and the location of the U inside G_UM (2 ways: U_, _U), and then arrange TREE in the four blanks (\(\frac{4!}{2!}\) ways), for a total of $$4\times2\times\frac{4!}{2!}=96\text{ ways}.$$
- Case 3 (G_U_M): If there are two extra letters inside GUM, then I might choose the number of blanks to go before [G_U_M] (3 ways: 0, 1, 2), and the location of the U inside G_U_M (3 ways: U_ _, _U_, _ _U), and then arrange TREE in the four blanks (\(\frac{4!}{2!}\) ways), for a total of $$3\times3\times\frac{4!}{2!}=108\text{ ways}.$$
- Case 4 (G_U_ _M): If there are 3 other letters between G and M, then I might choose the number of blanks to go before [G_U_ _M] (2 ways: 0, 1), and the location of the U inside G_U_ _M (4 ways: U_ _ _, _U_ _, _ _U_, _ _ _U), and then arrange TREE in the four blanks (\(\frac{4!}{2!}\) ways), for a total of $$2\times4\times\frac{4!}{2!}=96\text{ ways}.$$
- Case 5 (G_ _U_ _M): If everything is between G and M, then we just arrange UTREE, which we can do in $$_4\mathrm{C}_4\times\frac{5!}{2!}=60\text{ ways}.$$
But, as we know, all that is unnecessary.
I suspect the author expected students to use Joe’s method, since it is just an extension of the basic method for handling duplicate letters.
(I found a book online containing the problem, but with a different number, so it is presumably just a different edition; I can’t see the solution section, but the chapter is on “Counting with Identical Elements, and Cases“, and it’s possible that the author intended the problem as an exercise in the former, while whoever wrote up the solutions saw it as the latter!)
The most important lesson here, as always in combinatorics, is that there are many ways to solve a problem, and the best one is the one you happen to see. (After solving a problem, you should always look at it again to see if, with hindsight, you can see an easier way, which might be useful in the future!)
I replied:
Those are incredibly inefficient … but should reassure you that you don’t have to find the best method in order to get credit!
There are some problems for which this kind of thinking is necessary (or at least, is no harder than a more elegant method for small numbers). I’ve been looking into making a post on combinatorics, and saw one problem where our best combinatorist did just that.
I’m not sure what problem this was; but sometimes multiple cases, or even just listing possibilities, can be the fastest way to solve a problem.
As for similar questions,
I sometimes tell my students that their teachers are not so much trying to trick them, as trying to stretch them (and hoping they won’t be tricked). It can take some creativity and experience to find the nicest ways, but, again, there is often a good-enough way that you can find more easily.
The “trick” to this field is that there are many tricks you can use, so it can be hard to try to list them; each problem has its own twist (and usually multiple methods that can work). For various examples, you might look through
Most likely the textbook also covers many methods.