Arranging Letters with Duplicates

(A new question of the week)

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.

Arranging 8 letters, 2 identical

There are 8 letters : A, B, H, N, O, S, U, U

I was asked to find how many ways to arrange all the letters

The answer is 8!/2! (I’m sure it’s from 8P6, or am I wrong?)

Why isn’t it 8P8?

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:

I would not obtain this result as a permutation of 6 out of 8 elements.

It would be 8P8, or 8!, if all eight letters were different. However, since two of the letters are identical, swapping those two letters does not produce a different arrangement.

That’s the basic idea behind the division by 2!. For more, see:

Arrangements of Letters

Of course, if you have questions about what you read there, we’ll be happy to discuss this further!

Permutations with duplicates and restrictions

Here 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 problems

After reading this, Kurisada wrote back with new questions very similar to the last two parts of Kevin’s:

But I have 2 questions:

1. For AAADEFG, how many ways are there to arrange them:

a) without any A besides any other A

b) with 2 consecutive A (I think I know how to do this. I tried this as written below)

2. For AAADDFG, how many ways are there to arrange them?

For clarity, I will follow each of these three problems separately, untangling them from the ensuing discussion.

Three A’s, no two together

First, we’ll look at problem 1(a), about AAADEFG, as Doctor Rick replied:

I believe you mean “without any A beside any other A”, that is, “with no two A’s consecutive” — with no A followed immediately by another A. Part (c) of the question asked by Kevin, in the link I sent you, is this sort of problem, but it isn’t answered there.

The first thing I think of is to use the subtractive principle, as you did for (1b) below. But we don’t have just these two possibilities: (a) no A’s consecutive, (b) all three A’s consecutive. We have a third possibility, (c) two A’s consecutive but the third A not consecutive with them. Possibility (c) is part (1b) … maybe; I’ll have something to say about that below.

We could go ahead and use the subtractive principle even though it’s a bit more complicated, but let’s try another approach. Consider this: First we arrange the letters other than A, that is, permute DEFG. Then we place the three A’s; each can go in any of the blanks below (where I’m showing one of the permutations of DEFG as a specific example):

_ D _ E _ F _ G _

As long as we don’t place two in the same blank, no two A’s will be consecutive. So, how many ways are there to do this?

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:

For 1A

I think the solution is 4! x 5!/3! = 480

4! is the arrangements of DEFG

5! is the arrangements of A

3! is because all the A is the same

This is close. Doctor Rick answered:

You’re correct about the number of arrangements of DEFG. When we think about the A’s, you can think as you are doing, but you will need to remember that not only are the three A’s identical … the two blanks where we put nothing are identical, also! This makes it like your number 2. Do you see what more is needed?

There is a somewhat simpler way to think about placing 3 A’s in the five blanks. All you need to do is to choose 3 of the 5 blanks, in which to put the A’s — a combination problem, since the order in which we pick them doesn’t matter.

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 together

Now let’s move on to problem 1(b), which requires two consecutive A’s. Kurisada had already given his answer:

For no. 1b, I make AA as a new letter, that is X: XADEFG. Then I calculate the ways possible: 6!

Because the number of arrangements where there are 3 consecutive A is = 5!, the number of arrangements where there are 2 consecutive A is 6! – 5! .

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:

Here’s my uncertainty about the meaning of the question. Does it mean that at least two A’s are consecutive, so that both AADEFAG and DEAAAFG will be counted? Or does it mean exactly two A’s are consecutive, so that my second example does not count (since three A’s are consecutive, not two)? This sort of ambiguity comes up a lot in combinatorics problems; perhaps your textbook or other source tells you which meaning to assume by default. If so, which is it?

I see from your work that you are interpreting the problem to mean “exactly two A’s consecutive”; that’s why you subtract the number of arrangements with 3 consecutive A’s.

Your work has one problem: it double-counts the cases in which A is adjacent to X. Both AXDEFG and XADEFG, for example, are equivalent to AAADEFG. There is a simple fix for this, though. What do you see?

Another way to do this, seeing that we have already found the number of arrangements with no consecutive A’s and you’ve found the number of arrangements with 3 consecutive A’s, is to use the subtractive principle: every arrangement will have either no, exactly 2, or 3 consecutive A’s.

Kurisada answered:

For 1B:

I think I need to subtract my result before with 5!

That is 6! – 5! – 5!

The reason is because there is 5 conditions where X is adjacent to A

XADEFG, DXAEFG, and so on

While DEFG can be arranged in 4! ways

So 5 x 4! = 5!

Then after having this 1b result, I tried 1a with subtraction way

And I think it will be 7!/3! – 5! – (6! – 5! – 5!) = 240 (I think I’m wrong here because it’s different from above)

7!/3! is the total arrangements possible

5! is for three consecutive A

6! – 5! – 5! is for two consecutive A (not including three consecutive A)

Doctor Rick confirmed the solution to 1(b):

This is indeed what I had in mind as a correction to your method for 1b, though your explanation confused me at first. You’re saying, I think, that you already subtracted the 5! arrangements containing AX, and you also need to subtract the 5! arrangements containing XA. Thus the total number of arrangements with exactly two A’s together is 6! – 2*5! = 480.

And on the rework of 1(a):

Good work! This is correct; it is your other approach for 1a that was incorrect, as I said above.

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’s

Finally, Doctor Rick’s response to problem 2, on AAADDFG:

What do you think? If you understand the idea behind the solution for AAADEFG, then you can extend that idea to cover cases like this where more than one letter is repeated. (That’s what Doctor Mitteldorf challenged Kevin to do at the end of his answer in the link I gave you.)

Kurisada got it right:

For number 2:

Is it 7! / (3! 2!) ?

Doctor Rick explained further:

That’s correct! We divide the number of permutations of 7 distinct elements, by the number of permutations of 3 A’s and by the number of permutations of 2 D’s.

This is what you also need to do to correct your first approach on 1a.

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)!$$

Wow that’s complicated but very interesting!

Now I understand this well

Thank You very much Doctor!

And I got 240 to my 1a after dividing the previous result by 2!

All settled.