0
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Sep 7 '16 at 10:42
  • $\begingroup$ Using Principle of Inclusion-Exclusion. $\endgroup$
    – user202729
    Sep 7 '16 at 10:44
  • $\begingroup$ @Lovsovs they're different from each other. $\endgroup$
    – edohedo
    Sep 7 '16 at 10:45
  • $\begingroup$ What about the string lengths, or do you want the solution for an arbitrarily long string? $\endgroup$ Sep 7 '16 at 10:50
  • 1
    $\begingroup$ There are only $$\frac{7!}{2!2!} = 1260$$ distinguishable arrangements of the letters $AABDEFF$, so the given answer cannot be correct. $\endgroup$ Sep 7 '16 at 10:50
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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.. $\endgroup$
    – edohedo
    Sep 7 '16 at 12:00
  • $\begingroup$ 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. $\endgroup$ Sep 7 '16 at 12:56
0
$\begingroup$

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*}

$\endgroup$
0
$\begingroup$

$\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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.