# Number of arrangements in a line where there are 2 or more groups that have 2 or more members that cannot be adjacent to each other

Consider the following pattern of characters:

$$ABFDEFA$$

I am tasked to find the number of arrangements where repeating characters in the pattern's permutation cannot sit next to each other.

My Solution:

I've only tried arranging a line where there are spaces between the repeating characters like so:

$$\_A\_A\_F\_F\_$$

Edit: forgot to say the repeating characters are distinguishable.

Then from that, find all the possible permutations of the repeating characters multiplied by $^5P_3$ since we can only choose 3 spaces from 5 available ones:

$$\frac{4!5!}{(5-3)!}$$

But this only gets me 1440 which is really too far away from the given answer which is 2640. What's the best solution for my problem here?

• I assume you mean combinations, not permutations, e.g., the two $A$s are indistinguishable, right? And the string you give is seven long, yet your string with the _s is nine long? Sep 7 '16 at 10:42
• Using Principle of Inclusion-Exclusion. Sep 7 '16 at 10:44
• @Lovsovs they're different from each other. Sep 7 '16 at 10:45
• What about the string lengths, or do you want the solution for an arbitrarily long string? Sep 7 '16 at 10:50
• There are only $$\frac{7!}{2!2!} = 1260$$ distinguishable arrangements of the letters $AABDEFF$, so the given answer cannot be correct. Sep 7 '16 at 10:50

Since it is stipulated that the repeated letters are distinguishable, we wish to find the number of permutations of $A\mathcal{A}BDEF\mathcal{F}$ in which $A$ is not adjacent to $\mathcal{A}$ and $F$ is not adjacent to $\mathcal{F}$.

If there were no restrictions, the seven letters could be arranged in $7!$ ways. From these, we exclude those arrangements in which one or more of the restrictions is violated.

If $A$ and $\mathcal{A}$ are adjacent, we place them in an amber colored box. We then have six objects to arrange, the box and the other five letters. They can be arranged in $6!$ ways. The letters $A$ and $\mathcal{A}$ can be arranged in $2!$ ways within the box. Hence, there are $6!2!$ arrangements in which $A$ is adjacent to $A$.

By similar argument, there are $6!2!$ arrangements in which $F$ is adjacent to $\mathcal{F}$.

However, if we subtract $2 \cdot 6!2!$ from $7!$, we will have subtracted those in which $A$ is adjacent to $\mathcal{A}$ and $F$ is adjacent to $\mathcal{F}$ twice, once when we subtracted those arrangements in which $A$ is adjacent to $\mathcal{A}$ and once when we subtracted those arrangements in which $F$ is adjacent to $\mathcal{F}$. Therefore, we need to add the number of arrangements in which $A$ is adjacent to $\mathcal{A}$ and $F$ is adjacent to $\mathcal{F}$.

If we place $A$ and $\mathcal{A}$ in an amber colored box and place $F$ and $\mathcal{F}$ in a fuchsia colored box, we have five objects to arrange. They can be arranged in $5!$ ways. The object in each box can be arranged in $2!$ ways. Hence, the number of arrangements in which $A$ is adjacent to $\mathcal{A}$ and $F$ is adjacent to $\mathcal{F}$ is $5!2!2!$.

By the Inclusion-Exclusion Principle, the number of valid arrangements is $$7! - 2 \cdot 6!2! + 5!2!2! = 2640$$

• Can you explain how taking away the two same letters from the 7 ones can give us 6! ? Pretty new to discrete mathematics as you can see.. Sep 7 '16 at 12:00
• If we place $A$ and $\mathcal{A}$ in an amber colored box, we have six objects to arrange, the box and the other five letters. They can be arranged in $6!$ ways. Sep 7 '16 at 12:56

First let us count the number of arrangements in which $A_1A_2$ and $F_1F_2$ are together. This is $4 \times 120 = 480$ ways - since considering these as blocks, we need to arrange 5 positions and within their blocks there are 2 ways each of them to be together. Next count ways in which $A_1A_2$ are together but $F_1, F_2$ are not. This is arrange $(A_1A_2), B, D, E$ in $4! \times 2$ ways and in the 5 gaps between these, choose 2 to arrange $F_1, F_2$.Thus there are $4! \times 2 \times 5 \times 4 = 960$. Similarly there are 960 ways in which $F_1, F_2$ are together while $A_1, A_2$ are not. Thus the number of ways is \begin{align*} 7! - 960 - 960 - 480 = 2640 \end{align*}

$\underline{Another\;\; way}$

We can apply the "gap method" followed by the "subtraction method".

Initially, we take letters of the same kind to be indistinguishable, as is customary.

Firstly, we shall keep the $F's$ separate by placing them in the gaps of $-A-A-B-D-E-$ and permute the other letters, thus $\binom62\cdot\frac{5!}{2!} = 900$ ways.

We shall now subtract arrangements with the $A's$ together treating them as a super $A$,
$-\mathscr A - B-D-E- \;,$ thus $\binom52\cdot4! = 240$

The ans with repeated letters indistinguishable is thus $900 -240 = 660$

but since you say they are distinguishable, multiply by $2!2!$ to get $\boxed{2640}$