4
$\begingroup$

Given AACBBBDD. Find the number of ways to arrange these letters in a row such that all B are separated from each other and all D are separated from each other. Note: B and D can come together. But B should be separated from other B and D should be separated from other D.

The problem I'm facing:

If we solve it by GAP METHOD.

First of all arrange the letters on which there is no constraints. So arranging AAC = 3!/(2!*1!)

Now there are 4 gaps created. In these 4 gaps we need to fill 3 B and 2 D. Now there can be three ways to fill B,D.

If we first fill 3 B then after filling there will be total 7 gaps. 4(old)+(3 new gaps created by placing B). now in these 7 gaps we need to fill 2 D.

But if we fill 2 D first then after filling there will be total 6 gaps. 4(old)+(2 new gaps created by placing D). now in these 6 gaps we need to fill 3 B.

And if we consider filling all 3 B AND 2 D together then there are only 4 gaps so cant do this.

$\endgroup$
1
  • $\begingroup$ What did you try? $\endgroup$
    – Dominique
    Commented May 17 at 11:48

3 Answers 3

6
$\begingroup$

Successively apply the well known "gap" and "subtraction" methods.

Firstly, keep the $B's$ separate by placing them in the gaps of $-A-A-C-D-D-$ and permute the other letters, thus $\binom63\cdot\frac{5!}{2!2!} = 600$ ways.

Next, subtract arrangements with the $D's$ together treating them as a super $D,\;\;-A-A-C-\mathscr D-\;,\;$ so $\binom53\frac{4!}{2!}= 120$ ways

Thus valid number of arrangements = $600-120 = \boxed{480}$

$\endgroup$
5
$\begingroup$

In your thinking there is the problem, that in the way that you do you ommit some of possible arrangements. For example in your first way you do not count in strings that have $BDB$ somewhere inside since there are always other letters between two consecutive $B$ when you perform the procedure in that order.

The solution that I suggest goes as follows:

At first consider arrangement of letters $AACDD$ that satisfies the condition that no two $D$ are adjacent. There are $3 \times \binom{4}{2}$ ways to do so ($3$ for placing $AAC$ and $\binom{4}{2}$ for putting $D$ into gaps). Now you can put $B$ into gaps in $\binom{6}{3}$ ways, so you have in total: $$ 3 \times \binom{4}{2} \times \binom{6}{3} =360 $$ ways.

Now consider arrangement of the same letters but the one where $D$ are adjacent. If you have $5$ positions you can put $DD$ in $4$ ways and then arrange $AAC$ in $3$ ways. Now we know that one of $B$ must go in between those $DD$ and the other two can be arranged in $\binom{5}{2}$ ways (we have remaining $5$ gaps for two $B$). So it gives: $$ 4 \times 3 \times \binom{5}{2} = 120 $$ ways.

So in total we have: $$ 360 + 120 = \boxed{480} $$ ways.

$\endgroup$
3
$\begingroup$

None of your three methods will lead directly to the correct result because each time you are missing some possibilities.

Your third method does not allow B and D to be neighbours.

Your first method does not allow two Bs before the first A although this would be possible if a D is placed between those two Bs.

Similarly your second method does not allow two Ds before the first A although this would be possible if a B is placed between those two Ds.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .