# There are ten letters consisting of A's and B's. In how many ways can these letters be arranged without 4 consecutive letters?

I have tried thinking of one letter as a separator and the other as elements to distribute.

For example if there are 2 A's and 8 B's, We should distribute 8 elements into 3 containers with each container containing a maximum of 3 elements. Since we don't want to count situations with 4 consecutive elements:

_A_A_

However, the restriction on containers makes this problem a lot more complex than it's supposed to be. I wonder if there's a simpler solution to this simple-looking problem. The answer is 548 by the way, thanks in advance.

• The first step is to clarify the problem. Please explain whether the following interpretation of the problem is correct: There are $r$ A's and $s$ B's, where $r,s \in \Bbb{Z_{\geq 0}}$, and where $r + s = 10$. For each value of $r \in \{0,1,2, \cdots, 10\}$, let $f(r)$ denote the number of ways (if any) such that the $r$ A's and $s$ B's can be lined up in a row, where there is no occurrence in that row of either $4$ consecutive A's or $4$ consecutive B's. Then, the desired enumeration is $$\sum_{r=0}^{10} f(r).$$ Is this interpretation of the problem correct? Commented Nov 7, 2021 at 13:08
• Yes, that interpretation is correct. Commented Nov 7, 2021 at 13:11
• In accordance with this article on mathSE protocol, I am not permitted to provide a complete answer. Before that is done, you would have to edit your question to provide the missing information, as per that article. However, I am permitted to provide Comment/Hints. ...see next comment Commented Nov 7, 2021 at 13:14
• The first thing to notice is that by symmetry, $f(0) = f(10), f(1) = f(9), \cdots, f(4) = f(6)$. The next thing to notice is that $0 = f(0) = f(1)$. So, the problem reduces to enumerating $f(2), f(3), f(4),$ and $f(5)$. In general, for problems of this type, there are $3$ distinct approaches: [1] The direct approach, where you attempt to manually enumerate the number of satisfying sequences. [2] Inclusion-Exclusion, where you deduct the number of sequences that violate the constraint. ...see next comment Commented Nov 7, 2021 at 13:24
• And [3] Recursion, as detailed in the answer of Aby Coathin. Commented Nov 7, 2021 at 13:24

Instead of thinking of letters as separators, you can think of the transitioning from one type of letter to the other as a separator. The problem can then be transformed as follows: There are ten slots in a row, in how many ways can you place separators between consecutive slots such that all remaining segments are of length $$\leq 3$$? Note that for each way of segmenting the slots, there are exactly two ways of arranging letters corresponding to it: either start with A or start with B, and switch letter type whenever moving past a separator.
This is a standard recursion problem. Let $$F(n)$$ denote the number of ways of placing separators between $$n$$ slots, we have $$F(n)=F(n-1)+F(n-2)+F(n-3).$$ Initializing $$F(0)=1,F(1)=1,F(2)=2$$, you can arrive at $$F(10)=274$$. And hence the answer to your question is twice this number, which is 548.
• Thanks for your answer. I'm having trouble understanding how recursion is relevant to this problem, probably because I'm unfamiliar with this kind of problem. Is the length restriction of $\le3$ the reason you've summed the last three elements? Could you explain the reasoning or link some resources on this? Commented Nov 7, 2021 at 14:03
• i think there should have been one extra recurrence terms such as $F(n-4)$ Commented Nov 7, 2021 at 14:44
• @Bulbasaur There can be at most three consecutive identical letters, which is why there is no $F(n - 4)$ term. Commented Nov 7, 2021 at 15:32
• @Arda Özcan Yes, by considering all possible positions of the rightmost separator you can reduce $F(n)$ to three smaller problems, which are $F(n-1),F(n-2),F(n-3)$. Commented Nov 8, 2021 at 1:14