Binary Pattern (2)

We will only count the sequences starting in zero; the answer is then found by doubling, because inverting the digits gives all valid sequences starting in one.

To describe a sequence, we only have to state whether digits are used once or twice in succession (in pairs).

First, there is 1 sequence without pairs: $0101010101$ .

Patterns with one pair must start and end in the same digit (zero); therefore the pair must consist of two ones. There are four possible positions for the pair, from $0110101010$ to $0101010110$ . Thus we have 4 sequences of this kind.

Patterns with two pairs are possible if the pairs have opposite values (a pair of zeroes and a pair of ones). There are four positions for the zeroes and four positions for the ones, e.g. $0010110101$ . This results in $4 \times 4$ or 16 sequences.

Patterns with three pairs require two double ones and one double zero, e.g. $0110110100$ . There are four positions for the double zero and three positions for the single one, giving a total of 12 sequences.

Patterns with four pairs require two of each, e.g. $0011011001$ . There are three positions for the single zero and three for the single one. That adds up to 9 possibilities.

There are no sequences with five pairs.

In total, we have $1 + 4 + 16 + 12 + 9 = 42$ sequences starting in zero; and $2 \times 42 = \boxed{84}$ in total.

---

Generalization :

Note that this calculation can be summarized as $2\cdot (1\cdot 1 + 1\cdot 4 + 4\cdot 4 + 4\cdot 3 + 3 \cdot 3 + 3 \cdot 0)$ $= 2\cdot\left[\left(\begin{array}{c} 5 \\ 0 \end{array}\right)\left(\begin{array}{c} 5 \\ 0 \end{array}\right) + \left(\begin{array}{c} 5 \\ 0 \end{array}\right)\left(\begin{array}{c} 4 \\ 1 \end{array}\right) + \left(\begin{array}{c} 4 \\ 1 \end{array}\right)\left(\begin{array}{c} 4 \\ 1 \end{array}\right) + \left(\begin{array}{c} 4 \\ 1 \end{array}\right)\left(\begin{array}{c} 3 \\ 2 \end{array}\right) + \left(\begin{array}{c} 3 \\ 2 \end{array}\right)\left(\begin{array}{c} 3 \\ 2 \end{array}\right) + \left(\begin{array}{c} 3 \\ 2 \end{array}\right)\left(\begin{array}{c} 2 \\ 3 \end{array}\right) \right]$ $= 2 \cdot \sum_{k=0}^5 \left(\begin{array}{c} 5 - \lfloor k/2\rfloor \\ \lfloor k/2\rfloor \end{array}\right) \cdot \left(\begin{array}{c} 5 - \lceil k/2 \rceil \\ \lceil k/2\rceil \end{array}\right),$ which generalizes for sequences of length $2n$ as $2 \cdot \sum_{k=0}^n \left(\begin{array}{c} n - \lfloor k/2\rfloor \\ \lfloor k/2\rfloor \end{array}\right) \cdot \left(\begin{array}{c} n - \lceil k/2 \rceil \\ \lceil k/2\rceil \end{array}\right).$

I was unable to come up with a "by hand" solution and had to retreat to brute force search with python. Set ndigits to whatever length bit string you'd like:

ints = list(range(2**ndigits))
strs = map(lambda x: format(x, '0%db'%ndigits), ints)
strs = filter(lambda x: x.count('0')==x.count('1'), strs)
strs = filter(lambda x: x.find('111')==-1 and x.find('000')==-1, strs)
print len(strs)

With ndigits=10, it prints 84, the answer.