Here is a recent discussion with a frequent user of our service, Kurisada, about combinatorics. He is new to the subject, so this involved several introductions to new ideas. Show Arranging 8 letters, 2 identical
He is using the unformatted notation “nPr” to mean \(_nP_r = \frac{n!}{(n-r)!}\), which represents “the number of permutations of n items taken r at a time”. The result happens to be the same as \(_8P_6 = \frac{8!}{(8-6)!}\), but there is no direct connection. As an aside, it does seem odd that the number of ways to arrange 8 letters, two of which are the same, should be the same as the number of ways to choose and arrange only 6 of 8 letters (that are all different)! Until you realize that the latter does not mean arranging only the 6 letters other than the U’s, it can seem impossible. Consider a smaller example. Suppose we want to count the ways to arrange the three letters ABB, two of which are the same. The ways are ABB, BAB, and BBA. There are the same number of ways to choose only one of the three letters ABC and “arrange” it: A, B, C. But there is no connection here at all. Once we see where the formula comes from below, you’ll see that we just happen to be doing the same things for different reasons. Doctor Rick answered, primarily providing a link to the Ask Dr. Math archives because this is a standard type of problem:
Permutations with duplicates and restrictionsHere is the question from that page, from Kevin in 1999: Arrangements of Letters A problem has arisen in my review of combinatorics and discrete math. Any aid you can provide would be helpful. a. In how many ways can the letters in UNUNSUAL be arranged? (This is simply 8!, correct?) b. For the arrangements in part (a), how many have all three U's together? c. How many of the arrangements in part (a) have no consecutive U's? Once again, I thank you very much for your time.Part (a) is essentially our question, except that both U and N are repeated. (“Ununsual” is an unusual word, isn’t it?) Doctor Mitteldorf replied: Dear Kevin, All these problems require some thought. They can't be done by plugging numbers into a formula. Even the part about arranging the letters of UNUNSUAL (should that be UNUSUAL?) requires thought, because the 8! assumes that all the letters are different. In other words, suppose you have 8 letters ABCDEFGH and you ask how many ways they can be arranged. 8! is certainly the right answer. But suppose now that the A and the B are identical - say they're both A's. Then, I would think, you've double counted the entire number of permutations. How do I know? Because each time you've come up with A in some slot and B in a later slot, you've also counted a permutation that had B where the A was and A where the B was. So the answer to this new problem is not 8! but half of 8! . Now suppose you had 3 letters that were the same, as in AAADEFGH. How many different permutations are there of these letters? I say that if your answer is 8! you've overcounted by a factor of 6. Why 6? Well, say one of the permutations in your list is A...B...C. There's another one that looks like B...A...C, and there are four more that look like A...C...B, C...B...A, C...A...B, and B...C...A. This 6 is actually the number of permutations of the 3 identical things - that's how much you overcounted by. So the answer for AAADEFGH is 8!/3! . To get the right answer in a statistics problem, you almost always have to do this kind of detailed thinking. Without it, you can never be confident in your answer. For part b: How many ways have all 3 U's together? Well, let's start with 3 U's followed by 4 different letters. The 4 different letters can be arranged in 4! different ways. Now suppose the 3 U's are all at the end. That's 4! more. Two more possibilities are X-UUU-XXX and XXX-UUU-X, where the X's stand for the letters NSAL. It looks as if the 4 extra letters can be ordered in 4! different ways, and the U's can be placed in and around them in 5 different ways, for a total of 5*4! (which is just 5!) possibilities. Try understanding these thoroughly, and doing some problems like them, before you move on to the other questions, which are harder yet. For example, let's take UNUNSUAL, the 8-letter word as you've written it. There are 3 U's and 2 N's in this version. How many different permutations of these 8 letters are there?The first example here, AACDEFGH, is just like ours, with only one letter repeated twice. In general, you can see that with n letters, r of which are identical (that is, one letter repeated r times), the number of permutations is \(\frac{n!}{r!}\), which happens to be the same as \(_nP_r\). And for UNUNSUAL, we would divide 8! by both 3! for the U’s and 2! for the N’s, giving an answer of \(\frac{8!}{3!2!} = 3360\). Three years later, a reader wrote in to point out a quick alternative solution to part (b): In looking at the answer to part (b), it occurs to me that it is possible to consider 'UUU' as a single letter, and then the problem turns into "How many different ways are there of ordering 5 different letters?", which gives you 5! directly.This is a standard technique, so I suspect Doctor Mitteldorf was familiar with it; it was a valuable addition to what he wrote. It’s also yet another good demonstration of the value of multiple perspectives on a problem. More problemsAfter reading this, Kurisada wrote back with new questions very similar to the last two parts of Kevin’s:
For clarity, I will follow each of these three problems separately, untangling them from the ensuing discussion. Three A’s, no two togetherFirst, we’ll look at problem 1(a), about AAADEFG, as Doctor Rick replied:
We’ll look at the subtractive solution after we’ve worked out the two things to be subtracted below. The answer to Doctor Rick’s question will be (number of ways to arrange DEFG)*(number of ways to put A in 3 of 5 blanks). Kurisada replied:
This is close. Doctor Rick answered:
Finishing this, the correct answer is $$_4P_4\cdot {5\choose 3} = 4!\cdot\frac{5!}{3!2!} = 24\cdot 10 = 240.$$ The notation \({n\choose r}\), also written as \(_nC_r\), means the number of combinations (unordered) of n items taken r at a time, for which the formula is \({n\choose r} = \frac{n!}{r!(n-r)!}\). Three A’s, two togetherNow let’s move on to problem 1(b), which requires two consecutive A’s. Kurisada had already given his answer:
This is based on the final suggestion in the archived page we saw above. But having more than two A’s available makes this one a little trickier. Doctor Rick answered:
Kurisada answered:
Doctor Rick confirmed the solution to 1(b):
And on the rework of 1(a):
This is the subtractive method, (total arrangements) – (arrangements with all three together) – (arrangements with exactly two together), and gives the same result, 240, that we got before. Three A’s and two D’sFinally, Doctor Rick’s response to problem 2, on AAADDFG:
Kurisada got it right:
Doctor Rick explained further:
The general formula for permutations of \(n\) items, \(n_1\) of one kind, \(n_2\), and so on, is $$\frac{n!}{n_1!n_2!\cdots n_k!}$$ This is called a multinomial coefficient, which I have seen notated as [Wikipedia] $${n\choose{n_1,n_2,\dots n_k}},$$ or as [MathWorld] $$\left(n_1,n_2,\dots, n_k\right)!$$
All settled. |