Binary Pattern (3)

In Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int k = 7;
int N = 0, maxpat = 1 << (2*k);
for (int pat = 0; pat < maxpat; pat++) {
    int b = 0, nb = 0, sb = 0, snb = 0, x = pat;
    for (int i = 0; i < 2*k; i++, x >>= 1) {
        if ((x & 1) == 1) {
            b++; if (b > k) break;
            snb = 0; sb++;
            if (sb >= 3) break;
        } else {
            nb++; if (nb > k) break;
            sb = 0; snb++;
            if (snb >= 3) break;
        }
    }

    if (sb < 3 && snb < 3 && b == nb) N++;
}

System.out.println(N);

Output:

1

518

Clarification of this somewhat dense code:

• Each pattern may be represented as a $2k$ -bit number, i.e. positive integer less than maxpat $=\ 2^{2k}$ . The loop variable pat loops through all such patterns.

• In the inner loop, i indexes the bits in the pattern, from right to left. In each step, the pattern (in variable x ) is shifted one to the right. We study the bits one by one by looking at x&1 .

• The variables b and nb ("bit" and "no bit") count the numbers of ones and zeroes. After the loop, we check that they are equal. If either of them exceeds half of the pattern length ( b > k ) the pattern is invalid, and we break out of the inner loop.

• The variables sb and snb ("sequence of bits") count how many ones or zeroes were counted in a row. If the opposite value is read, they are reset to zero. If any of them becomes three or more (too much!), the break statement gets us out.

An alternative solution, "by hand", is doable using the generalization I presented in this problem . We have

$2\cdot\left[\left(\begin{array}{c} 7 \\ 0 \end{array}\right)\left(\begin{array}{c} 7 \\ 0 \end{array}\right) + \left(\begin{array}{c} 7 \\ 0 \end{array}\right)\left(\begin{array}{c} 6 \\ 1 \end{array}\right) + \left(\begin{array}{c} 6 \\ 1 \end{array}\right)\left(\begin{array}{c} 6 \\ 1 \end{array}\right) + \left(\begin{array}{c} 6 \\ 1 \end{array}\right)\left(\begin{array}{c} 5 \\ 2 \end{array}\right) + \left(\begin{array}{c} 5 \\ 2 \end{array}\right)\left(\begin{array}{c} 5 \\ 2 \end{array}\right) + \left(\begin{array}{c} 5 \\ 2 \end{array}\right)\left(\begin{array}{c} 4 \\ 3 \end{array}\right) + \left(\begin{array}{c} 4 \\ 3 \end{array}\right)\left(\begin{array}{c} 4 \\ 3 \end{array}\right) \right] \\ = 2\cdot\left[1^2 + 1\cdot 6 + 6^2 + 6\cdot 10 + 10^2 + 10\cdot 4 + 4^2\right] \\ = 2\cdot\left[1 + 6 + 36 + 60 + 100 + 40 + 16\right] = 2\cdot 259 = \boxed{518}.$