Combinatorics – How many ways are there to arrange the string of letters AAAAAABBBBBB such that each A is next to at least one other A

combinatoricscombinatorics-on-words

I found a problem in my counting textbook, which is stated above. It gives the string AAAAAABBBBBB, and asks for how many arrangements (using all of the letters) there are such that every A is next to at least one other A.

I calculated and then looked into the back for the answer, and the answer appears to be $105$. My answer fell short of that by quite a bit. I broke down the string into various cases, and then used Stars and Bars to find how many possibilities there are for each. Now here's what I have got so far. First case would be all As are right next to each other, leaving $2$ spots for the $6$ Bs. That gives $\binom{7}{1}$ from Stars and Bars, $7$ possibilities. Second case was dividing the As into $2$ groups of 3 As. There would have to be $1$ B between the two, which leaves $5$ Bs that can be moved. Using Stars and Bars, there are $3$ possible places to place a B and $5$ Bs in total, so $\binom{6}{2}$, $15$ possibilities. Then there's a group of $4$ As and another group of $2$ As. $1$ B would be placed inbetween, and then the calculation would be the same as the second case, except it would have to be doubled to account that the groups of As can be swapped and it would be distinct. That gives $30$ possibilities. Then I found one final case of dividing the As into 3 groups of 2 As. 2 Bs would immediately be placed between the 3 groups, leaving 4 Bs to move between the 4 possible locations. I got $\binom{5}{3}$ for that, which adds $10$ possibilities. Summing it up, I only have $62$ possibilities, which is quite far from the $105$ answer. Any ideas where I might have miscalculated or missed a potential case? Additionally, are there any better ways to calculate this compared to this method of casework?

Best Answer

You missed the fact that there can be any number of Bs between the two groups of As. For the $3+3$ case,

If there's one B, number of cases is $6$.

If there's two Bs, number of cases is $5$.

If there's three Bs, number of cases is $4$. $$\cdots$$ If there's six Bs, number of cases is $1$.

In total, there are $6+5+4+3+2+1=21$ ways.

Similarly, there are $21\cdot2=42$ ways for the $4+2$ case.

Now, a similar mistake you did for the $2+2+2$ case. Can you get it now and complete your solution?

Hope this helps. Ask anything if not clear :)

Related Question