Detailed mathematical approach

Problem Summary

The quantity computed here is a counting function \(F(n)\) for red-blue sequences of length \(2n\) with exactly \(n\) red entries and \(n\) blue entries. A sequence is not accepted just because it is balanced: while the colors are read from left to right, they also drive a second-order linear process, and only sequences whose final recurrence value is zero are counted.

So the problem has two intertwined constraints. One is combinatorial, namely the balance condition on the colors. The other is algebraic: each prefix carries a two-term state, and the update rule depends on whether the next color repeats the previous color or switches away from it. The challenge is therefore to count balanced color strings while tracking the exact linear state they induce.

Mathematical Approach

The implementations show that the problem is best written as a dynamic program on prefixes. The key is to identify the smallest amount of information a prefix must remember so that every valid continuation can be handled correctly.

A prefix determines a two-term linear state

After the first color is chosen, the linear process starts from the same seed values in both cases:

$x_1=2,\qquad x_0=-1.$

The color itself still matters, because future updates distinguish between repeat the current color and switch to the other color. If a prefix currently ends with color \(c\) and the stored pair is \((x_\ell,x_{\ell-1})\), then appending one more color produces a new pair \((x_{\ell+1},x_\ell)\).

The two update rules

There are only two algebraic transitions.

If the new color is the same as the previous one, then

$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$

If the new color is different from the previous one, then

$x_{\ell+1}=-2x_\ell.$

Equivalently, with column vectors,

$\begin{bmatrix}x_{\ell+1}\\ x_\ell\end{bmatrix} =\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix} \begin{bmatrix}x_\ell\\ x_{\ell-1}\end{bmatrix} \quad\text{for a repeat},$

and

$\begin{bmatrix}x_{\ell+1}\\ x_\ell\end{bmatrix} =\begin{bmatrix}-2&0\\ 1&0\end{bmatrix} \begin{bmatrix}x_\ell\\ x_{\ell-1}\end{bmatrix} \quad\text{for a switch}.$

This already explains why the state has to remember two consecutive recurrence values rather than just one: the repeat case explicitly uses both \(x_\ell\) and \(x_{\ell-1}\).

The correct compressed state space

For a prefix of length \(\ell\), let \(r\) be the number of red entries used so far, let \(c\in\{R,B\}\) be the last color, and let \((u,v)=(x_\ell,x_{\ell-1})\). Then define

$D_{\ell,r,c}(u,v)$

to be the number of prefixes having exactly that summary. This is the natural compressed state because every legal continuation depends only on:

$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$

No earlier detail of the prefix is needed once those quantities are known. Different color strings that land in the same state can therefore be merged safely.

Transition recurrence for the counting DP

The two initial states correspond to choosing the first color as red or blue:

$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$

Now suppose a state \(D_{\ell,r,c}(u,v)\) is known.

If another red entry may still be used, then appending \(R\) creates a new state at level \(\ell+1\). The new red count is \(r+1\), the new last color is \(R\), and the new first recurrence component is

$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$

So

$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$

Similarly, if another blue entry may still be used, then with blue count \(\ell-r\) we get

$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$

and therefore

$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$

This is the full recurrence used by the implementations. Every branch adds one color, updates the recurrence pair, and merges back into the hash table entry of the resulting compressed state.

The final counting formula

At total length \(2n\), only balanced sequences are admissible, so the red count must be \(n\). The algebraic acceptance condition is that the current recurrence value vanishes. Hence

$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$

The second component \(v\) is not constrained at the end; it is carried only because intermediate repeat steps need it.

Worked Example: why \(F(2)=4\)

The validation case \(n=2\) is small enough to inspect directly. Balanced strings have length 4 with two \(R\)'s and two \(B\)'s. Start from \((x_1,x_0)=(2,-1)\).

For the prefix \(RR\), the second symbol repeats the first, so

$ (2,-1)\to (0,2). $

Continuing with \(RRB\) switches color, hence

$ (0,2)\to (0,0), $

and one more blue repeat keeps the first component at zero. Therefore \(RRBB\) is valid.

For \(RBBR\), the steps are

$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $

so this sequence is valid as well. In contrast,

$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$

so its final first component is nonzero and it does not contribute. By symmetry under swapping red and blue, the four valid strings are

$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$

which gives

$F(2)=4.$

How the Code Works

The C++, Python, and Java implementations store one layer of the dynamic program at a time in a hash table keyed by the compressed state: current red count, last color, and the ordered pair of consecutive recurrence values. The current prefix length does not need to be stored inside the key because the outer loop already fixes the layer.

Each layer tries to append a red symbol and a blue symbol whenever the corresponding quota has not yet been exhausted. The update rule is exactly the mathematical recurrence above: a repeat uses the matrix \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\), while a switch uses \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\). Whenever two different prefixes reach the same compressed state, their multiplicities are added together immediately.

After the last layer, the implementation scans the remaining states and sums the multiplicities of those with balanced colors and zero first recurrence component. The small checks \(F(2)=4\) and \(F(8)=11892\) are included to confirm that the transition logic matches the intended mathematics before evaluating \(F(26)\).

Complexity Analysis

There are exactly \(2n-1\) transition layers, and each reachable state generates at most two outgoing transitions. If \(S_\ell\) denotes the number of distinct compressed states at prefix length \(\ell\), the running time is

$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$

up to hash-table overhead, and the memory usage is

$O\!\left(\max_\ell S_\ell\right),$

because only the current and next layers are kept. This is much smaller than brute force over all \(2^{2n}\) color strings, and even smaller than a direct scan of all balanced strings \(\binom{2n}{n}\), because many different prefixes collapse to the same compressed recurrence state.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=951
2. Dynamic programming: Wikipedia - Dynamic programming
3. Recurrence relation: Wikipedia - Recurrence relation
4. Matrix multiplication: Wikipedia - Matrix multiplication
5. Binomial coefficient: Wikipedia - Binomial coefficient