# Trouble in finding number of permutations

I am currently taking a course on Discrete Mathematics. In that while solving this problem am bit confused with the method of solving the following problem.

Problem: How many arrangements are there of the letters TALLAHASSEE which have no adjacent A's?

I can find the total number of permutations. But How to find the total no of permutations of adjacent A's?

so that, my answer will be..

Answer = total number of all permutations - total number of permutations of adjacent A's

-
Find the total permutations, then subtract from it the number of permutations with adjacent As. – Thomas Andrews Oct 18 '11 at 13:18

There are total 11 characters, 3 "A", 2 "L", 2 "S", 2 "E", and one "T" and one "H". The total number of unrestricted permutations $n_0$ would be $n_0 =\binom{11}{3,2,2,2,1,1}=\frac{11!}{3! (2!)^3} = 831600$.

Now, replace a pair of "A" characters with a double $\tilde{A}$. Number of permutations here $n_1 =\binom{10}{1,1,2,2,2,1,1} = 453600$.

Replacing a triple of "A" with a single character gets $n_2 = \binom{9}{1,2,2,2,1,1} = 45360$.

The number of permutations with no adjacent "A"s is obtained by inclusion-exclusion principle $n = n_0 - n_1 + n_2 = 423360$.

Here is Mathematica explicit counting:

In[3]:= Length@
DeleteCases[
Permutations[Characters["TALLAHASSEE"]], {___, "A", "A", ___}]

Out[3]= 423360

-

We can bypass Inclusion/Exclusion by using a minor modification of Stars and Bars.

First arrange the $8$ non-A's. The number of arrangements is the multinomial coefficient $$\binom{8}{2,2,2,1,1}.$$ Alternately, put a sticker on one of the two L, one of the two S, and one of the two E, to distinguish them. The $8$ distinct letters can be arranged in $8!$ ways. Remove the stickers, one at a time. Each time we remove a sticker, $2!$ arrangements collapse into $1$. So the number of arrangements of the $8$ letters is $$\frac{8!}{2!2!2!}.$$

The $8$ letters determine $9$ "holes," one at the left end, one at the right end, and seven inter-letter holes. We need to choose $3$ of these holes to put the A's into. This can be done in $\binom{9}{3}$ ways.

It follows that the number of words with no two A's adjacent is $$\binom{8}{2,2,2,1,1}\binom{9}{3} \qquad\text{or equivalently}\qquad\frac{8!}{2!2!2!}\binom{9}{3} .$$

Compute. We get $(5040)(84)$, which is $423360$.

Comment: In the same way, we can get a simple expression for the answer if there are many more letters, including many more A's. Inclusion/Exclusion also generalizes, but gets gradually more unpleasant.

-
+1 for adding and removing "sticker"! and +100 for the rest! Superb approach! :) – Quixotic Oct 18 '11 at 14:53

To find the number in which the As are adjacent, put them together and treat it like a unit!

If two As are together, you are finding permutations of the letters T, L, L, H, S, S, a letter called AA, and a letter called A. You have to be careful, though, since you will be counting instances in which A goes first and AA goes immediately after as different from those in which AA goes first and A goes immediately after, whereas they are the same. So you need to "take out" from the count those permutations in which all three As are together. How to count them?

Treat the three like a unit! Now you want to count the number of permutations of the letters T, L, L, H, S, S, and a letter called AAA.

(Total number) - (count with a letter AA and a letter A) + (count with a letter AAA).