1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Commented Nov 7, 2021 at 13:08
  • $\begingroup$ Yes, that interpretation is correct. $\endgroup$ Commented Nov 7, 2021 at 13:11
  • $\begingroup$ 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 $\endgroup$ Commented Nov 7, 2021 at 13:14
  • $\begingroup$ 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 $\endgroup$ Commented Nov 7, 2021 at 13:24
  • $\begingroup$ And [3] Recursion, as detailed in the answer of Aby Coathin. $\endgroup$ Commented Nov 7, 2021 at 13:24

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Commented Nov 7, 2021 at 14:03
  • $\begingroup$ i think there should have been one extra recurrence terms such as $F(n-4)$ $\endgroup$ Commented Nov 7, 2021 at 14:44
  • $\begingroup$ @Bulbasaur There can be at most three consecutive identical letters, which is why there is no $F(n - 4)$ term. $\endgroup$ Commented Nov 7, 2021 at 15:32
  • $\begingroup$ @N.F.Taussig yeah , realize it now. thanks.. $\endgroup$ Commented Nov 7, 2021 at 15:47
  • $\begingroup$ @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)$. $\endgroup$ Commented Nov 8, 2021 at 1:14

You must log in to answer this question.

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