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.
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.
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)\).
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}\).
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.
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.
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.
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.$$
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)\).
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.
Berechnet wird eine Zaehlfunktion \(F(n)\) fuer Rot-Blau-Folgen der Laenge \(2n\), die genau \(n\) rote und \(n\) blaue Eintraege enthalten. Eine Folge ist aber nicht schon deshalb gueltig, weil sie farblich ausgeglichen ist: Beim schrittweisen Lesen der Farben wird zugleich ein linearer Prozess zweiter Ordnung fortgeschrieben, und gezaehlt werden nur die Folgen, deren letzter Rekurrenzwert null ist.
Damit besitzt das Problem zwei gekoppelte Bedingungen. Die erste ist kombinatorisch und betrifft die Farbhaeufigkeiten. Die zweite ist algebraisch: Zu jedem Praefix gehoert ein Zweierzustand, und dessen Update haengt davon ab, ob die neue Farbe die vorherige wiederholt oder zu der anderen Farbe wechselt. Gesucht ist also die Zahl balancierter Farbfolgen mit einer ganz bestimmten Endbedingung fuer diesen linearen Zustand.
Die Implementierungen zeigen, dass sich die Aufgabe am natuerlichsten als dynamische Programmierung ueber Praefixe formulieren laesst. Entscheidend ist, die minimale Information zu identifizieren, die ein Praefix speichern muss, damit jede Fortsetzung korrekt bewertet werden kann.
Nach der Wahl der ersten Farbe startet der lineare Prozess in beiden Faellen mit denselben Anfangswerten:
$$x_1=2,\qquad x_0=-1.$$
Die Farbe selbst bleibt dennoch relevant, weil spaetere Schritte zwischen gleiche Farbe erneut und Farbwechsel unterscheiden. Wenn ein Praefix aktuell mit Farbe \(c\) endet und das Paar \((x_\ell,x_{\ell-1})\) gespeichert ist, dann erzeugt das Anhaengen einer weiteren Farbe ein neues Paar \((x_{\ell+1},x_\ell)\).
Algebraisch gibt es nur zwei Moeglichkeiten.
Wird die bisherige Farbe wiederholt, dann gilt
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
Bei einem Farbwechsel gilt dagegen
$$x_{\ell+1}=-2x_\ell.$$
In Matrixschreibweise lautet das
$$\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{bei Wiederholung},$$
beziehungsweise
$$\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{beim Wechsel}.$$
Hier sieht man auch unmittelbar, warum ein einzelner Wert nicht genuegt: Im Wiederholungsfall werden sowohl \(x_\ell\) als auch \(x_{\ell-1}\) benoetigt.
Fuer ein Praefix der Laenge \(\ell\) sei \(r\) die Anzahl roter Eintraege, \(c\in\{R,B\}\) die letzte Farbe und \((u,v)=(x_\ell,x_{\ell-1})\). Dann bezeichne
$$D_{\ell,r,c}(u,v)$$
die Zahl aller Praefixe mit genau dieser Zusammenfassung. Dieser komprimierte Zustand ist optimal, weil jede zulaessige Fortsetzung nur von
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}$$
abhaengt. Alle frueheren Details des Praefixes sind danach irrelevant. Verschiedene Farbfolgen, die im selben Zustand landen, duerfen daher exakt zusammengelegt werden.
Die beiden Startzustaende entsprechen der Wahl der ersten Farbe:
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
Nun sei ein Zustand \(D_{\ell,r,c}(u,v)\) gegeben.
Falls noch ein roter Eintrag gesetzt werden darf, dann fuehrt das Anhaengen von \(R\) zu einem neuen Zustand der Ebene \(\ell+1\). Die neue Rotanzahl ist \(r+1\), die neue letzte Farbe ist \(R\), und die erste Rekurrenzkomponente lautet
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
Also gilt
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Analog gilt fuer das Anhaengen von \(B\), sofern noch ein blauer Eintrag verfuegbar ist und aktuell \(\ell-r\) blaue Eintraege benutzt wurden,
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
und damit
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Genau diese Rekurrenz wird in den Implementierungen ausgewertet. Jeder Zweig fuegt eine Farbe hinzu, aktualisiert das lineare Paar und akkumuliert anschliessend im Hash-Eintrag des resultierenden komprimierten Zustands.
Bei Gesamtlange \(2n\) sind nur ausgeglichene Folgen erlaubt, also muss die Rotanzahl gleich \(n\) sein. Zusaetzlich muss der aktuelle Rekurrenzwert verschwinden. Daher
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
Die zweite Komponente \(v\) wird am Ende nicht getestet; sie wird nur mitgefuehrt, weil sie bei Wiederholungsschritten in spaeteren Zwischenzustaenden benoetigt wird.
Der Validierungsfall \(n=2\) ist klein genug fuer eine direkte Analyse. Balancierte Folgen haben Laenge 4 und bestehen aus zwei \(R\) und zwei \(B\). Gestartet wird stets mit \((x_1,x_0)=(2,-1)\).
Beim Praefix \(RR\) wiederholt das zweite Symbol die erste Farbe, also
$$ (2,-1)\to (0,2). $$
Das Praefix \(RRB\) wechselt anschliessend die Farbe und liefert
$$ (0,2)\to (0,0), $$
und ein weiteres blaues Symbol laesst die erste Komponente bei null. Daher ist \(RRBB\) gueltig.
Fuer \(RBBR\) ergibt sich
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $$
also ebenfalls ein gueltiger Beitrag. Dagegen gilt
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
womit der Endwert ungleich null ist. Wegen der Symmetrie beim Vertauschen von Rot und Blau sind die vier gueltigen Folgen
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$$
und somit
$$F(2)=4.$$
Die C++-, Python- und Java-Implementierungen speichern immer nur eine Schicht der dynamischen Programmierung in einer Hashtabelle, deren Schluessel aus der aktuellen Rotanzahl, der letzten Farbe und dem geordneten Paar zweier aufeinanderfolgender Rekurrenzwerte besteht. Die aktuelle Praefixlaenge muss nicht im Schluessel stehen, weil die aeussere Schleife die Schicht bereits festlegt.
In jeder Schicht wird versucht, ein rotes und ein blaues Symbol anzuhaengen, sofern das jeweilige Kontingent noch nicht ausgeschoepft ist. Die numerische Aktualisierung ist exakt die oben hergeleitete Rekurrenz: Wiederholung verwendet die Matrix \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\), ein Wechsel die Matrix \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\). Treffen verschiedene Praefixe im selben komprimierten Zustand zusammen, werden ihre Vielfachheiten sofort addiert.
Nach der letzten Schicht werden alle verbleibenden Zustaende durchlaufen, und aufsummiert werden genau die Vielfachheiten mit balancierter Farbzahl und verschwindender erster Rekurrenzkomponente. Die kleinen Tests \(F(2)=4\) und \(F(8)=11892\) bestaetigen vor der Auswertung von \(F(26)\), dass die Uebergaenge der beabsichtigten Mathematik entsprechen.
Es gibt genau \(2n-1\) Uebergangsschichten, und jeder erreichbare Zustand erzeugt hoechstens zwei Nachfolger. Bezeichnet \(S_\ell\) die Anzahl verschiedener komprimierter Zustaende in Praefixlaenge \(\ell\), dann betraegt die Laufzeit
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
bis auf den ueblichen Overhead der Hashtabelle, waehrend der Speicherbedarf
$$O\!\left(\max_\ell S_\ell\right)$$
ist, weil nur aktuelle und naechste Schicht gehalten werden. Das ist erheblich kleiner als rohe Brute Force ueber alle \(2^{2n}\) Farbfolgen und auch kleiner als ein reines Durchmustern aller balancierten Folgen \(\binom{2n}{n}\), weil viele verschiedene Praefixe in denselben komprimierten Rekurrenzzustand zusammenfallen.
Burada hesaplanan nicelik, uzunluğu \(2n\) olan ve tam olarak \(n\) kırmızı ile \(n\) mavi içeren renk dizilerinin sayısı olan \(F(n)\)'dir. Fakat bir dizi sadece dengeli olduğu için kabul edilmez. Renkler soldan saga okunurken aynı anda ikinci dereceden lineer bir süreç de ilerler ve yalnızca son rekürans değeri sıfır olan diziler sayılır.
Dolayısıyla problem iki farklı kısıtı aynı anda taşır. Birincisi tamamen kombinatoriktir ve kırmızı-mavi dengesidir. İkincisi cebirseldir: her önek, iki bileşenli bir durum taşır ve bir sonraki güncelleme, yeni rengin önceki rengi tekrar etmesine mi yoksa öbür renge geçmesine mi bağlıdır. Asıl iş, bu lineer durumun son koşulunu korurken dengeli renk dizilerini saymaktır.
Uygulamalar, problemin en doğal biçimde önekler üzerinde tanımlanan bir dinamik programlama ile yazıldığını gösteriyor. Önemli nokta, bir öneğin gelecekteki bütün uzantıları doğru hesaplanabilsin diye hangi en küçük bilgiyi taşıması gerektiğini bulmaktır.
İlk renk seçildikten sonra lineer süreç her iki başlangıç durumunda da aynı tohum değerlerle başlar:
$$x_1=2,\qquad x_0=-1.$$
Bununla birlikte rengin kendisi yine de önemlidir; çünkü sonraki adımlar aynı rengi sürdürme ile renk değiştirme arasında ayrım yapar. Eğer mevcut önek \(c\) rengiyle bitiyorsa ve saklanan çift \((x_\ell,x_{\ell-1})\) ise, bir renk daha eklendiğinde yeni çift \((x_{\ell+1},x_\ell)\) olur.
Cebirsel olarak yalnızca iki olasılık vardır.
Yeni renk öncekiyle aynıysa
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
Yeni renk farklıysa
$$x_{\ell+1}=-2x_\ell.$$
Sütun vektörleriyle aynı kurallar
$$\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{aynı renk durumunda},$$
ve
$$\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{renk değişiminde}$$
şeklindedir. Buradan neden tek bir sayı saklamanın yetmediği de görülür: aynı renk kuralı hem \(x_\ell\) hem de \(x_{\ell-1}\) değerini kullanır.
Uzunluğu \(\ell\) olan bir önek için \(r\) şimdiye kadar kullanılan kırmızı sayısı, \(c\in\{R,B\}\) son renk ve \((u,v)=(x_\ell,x_{\ell-1})\) olsun. O zaman
$$D_{\ell,r,c}(u,v)$$
tam olarak bu özete sahip önek sayısını göstersin. Bu sıkıştırılmış durum doğrudur; çünkü her yasal devam yalnızca şu büyüklüklere bağlıdır:
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$$
Bunlar bilindiğinde öneğin daha eski ayrıntılarına artık ihtiyaç kalmaz. Aynı duruma düşen farklı renk dizileri bu yüzden güvenle birleştirilebilir.
İki başlangıç durumu, ilk rengin kırmızı veya mavi seçilmesine karşılık gelir:
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
Şimdi elimizde bir \(D_{\ell,r,c}(u,v)\) durumu olsun.
Eğer hâlâ bir kırmızı daha eklenebiliyorsa, \(R\) eklemek \(\ell+1\) katmanında yeni bir durum üretir. Yeni kırmızı sayısı \(r+1\), yeni son renk \(R\) olur ve yeni ilk rekürans bileşeni
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
olur. Dolayısıyla
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Benzer biçimde, kullanılabilir bir mavi daha varsa ve mevcut mavi sayısı \(\ell-r\) ise, \(B\) eklediğimizde
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
ve bu yüzden
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Uygulamaların kullandığı tam rekürans budur. Her dal bir renk ekler, lineer çifti günceller ve sonra oluşan sıkıştırılmış durumun hash tablosu girdisine eklenir.
Toplam uzunluk \(2n\) olduğunda ancak dengeli diziler kabul edilir; yani kırmızı sayısı \(n\) olmalıdır. Cebirsel kabul koşulu da güncel rekürans değerinin sıfır olmasıdır. Bu nedenle
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
İkinci bileşen \(v\) sonda ayrıca sınanmaz; yalnızca aradaki aynı-renk adımlarında gerektiği için taşınır.
Doğrulama örneği olan \(n=2\) doğrudan incelenebilir. Dengeli diziler uzunluğu 4 olan ve iki \(R\) ile iki \(B\) içeren dizilerdir. Başlangıç her zaman \((x_1,x_0)=(2,-1)\) durumudur.
\(RR\) öneğinde ikinci sembol ilkiyle aynı renktedir; bu yüzden
$$ (2,-1)\to (0,2). $$
Sonra \(RRB\) bir renk değişimi yapar ve
$$ (0,2)\to (0,0), $$
bir mavi daha eklemek de ilk bileşeni sıfırda bırakır. Yani \(RRBB\) geçerlidir.
\(RBBR\) için geçişler
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0) $$
şeklindedir; bu dizi de geçerlidir. Buna karşılık
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
dolayısıyla son ilk bileşen sıfır değildir ve katkı yapmaz. Kırmızı ile maviyi yer değiştirmenin simetrisinden dolayı dört geçerli dizi
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR$$
olur ve sonuç
$$F(2)=4$$
çıkar.
C++, Python ve Java uygulamaları dinamik programlamanın her an yalnızca tek bir katmanını saklar. Hash tablosunun anahtarı; mevcut kırmızı sayısı, son renk ve art arda gelen iki rekürans değerinden oluşan sıralı çifttir. Önek uzunluğunu ayrıca anahtarın içinde tutmaya gerek yoktur; çünkü dış döngü hangi katmanda bulunulduğunu zaten belirler.
Her katmanda, ilgili kotası henüz dolmamışsa bir kırmızı ve bir mavi eklenmesi denenir. Sayısal güncelleme yukarıdaki matematikle birebir aynıdır: aynı renk durumu \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\), renk değişimi ise \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\) matrisiyle temsil edilir. Farklı önekler aynı sıkıştırılmış duruma ulaştığında çoklukları hemen toplanır.
Son katmandan sonra kalan bütün durumlar taranır ve dengeli renk sayısına sahip olup ilk rekürans bileşeni sıfır olanların çoklukları toplanır. Küçük doğrulamalar olan \(F(2)=4\) ve \(F(8)=11892\), \(F(26)\) hesaplanmadan önce geçiş mantığının hedeflenen matematikle uyumlu olduğunu gösterir.
Toplam tam olarak \(2n-1\) geçiş katmanı vardır ve her ulaşılabilir durum en fazla iki yeni duruma dallanır. \(\ell\) uzunluğundaki farklı sıkıştırılmış durum sayısına \(S_\ell\) dersek çalışma süresi
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
olur; burada hash tablosu ek yükü sabit çarpanlara gömülüdür. Bellek kullanımı ise
$$O\!\left(\max_\ell S_\ell\right)$$
düzeyindedir; çünkü yalnızca mevcut ve sonraki katman tutulur. Bu, tüm \(2^{2n}\) ham renk dizilerini denemekten çok daha küçüktür; hatta tüm dengeli dizileri \(\binom{2n}{n}\) tek tek dolaşmaktan da küçüktür, çünkü birçok farklı önek aynı sıkıştırılmış rekürans durumunda birleşir.
La cantidad que se calcula aqui es una funcion de conteo \(F(n)\) para secuencias rojas y azules de longitud \(2n\) con exactamente \(n\) simbolos rojos y \(n\) simbolos azules. Pero no basta con que la secuencia este equilibrada. Mientras se leen los colores de izquierda a derecha, tambien evoluciona un proceso lineal de segundo orden, y solo se cuentan las secuencias cuyo valor final de esa recurrencia es cero.
Por tanto, el problema mezcla dos restricciones. La primera es combinatoria y exige equilibrio entre rojos y azules. La segunda es algebraica: cada prefijo transporta un estado de dos componentes, y la actualizacion depende de si el nuevo color repite el color anterior o cambia al otro color. El objetivo es contar todas las palabras balanceadas que ademas satisfacen esa condicion final lineal.
Las implementaciones muestran que la formulacion natural es una programacion dinamica sobre prefijos. El punto central consiste en identificar la menor cantidad de informacion que un prefijo debe conservar para que cualquier continuacion futura pueda evaluarse correctamente.
Despues de elegir el primer color, el proceso lineal arranca con las mismas semillas en ambos casos:
$$x_1=2,\qquad x_0=-1.$$
El color sigue importando, porque los pasos posteriores distinguen entre repetir el color actual y cambiar al otro color. Si un prefijo termina con color \(c\) y el par almacenado es \((x_\ell,x_{\ell-1})\), al anadir un nuevo simbolo el par pasa a ser \((x_{\ell+1},x_\ell)\).
Solo existen dos transiciones algebraicas posibles.
Si el nuevo color coincide con el anterior, entonces
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
Si el nuevo color es distinto, entonces
$$x_{\ell+1}=-2x_\ell.$$
En forma matricial,
$$\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{si se repite el color},$$
y
$$\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{si hay cambio de color}.$$
Esto explica por que hay que recordar dos valores consecutivos y no solo uno: en el caso de repeticion intervienen simultaneamente \(x_\ell\) y \(x_{\ell-1}\).
Para un prefijo de longitud \(\ell\), sea \(r\) el numero de simbolos rojos ya usados, sea \(c\in\{R,B\}\) el ultimo color, y sea \((u,v)=(x_\ell,x_{\ell-1})\). Definimos
$$D_{\ell,r,c}(u,v)$$
como el numero de prefijos que tienen exactamente ese resumen. Este es el estado comprimido natural, porque cualquier continuacion legal depende solo de
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$$
Una vez fijados esos datos, el detalle anterior del prefijo deja de importar. Por eso, dos cadenas distintas que llegan al mismo estado pueden fusionarse sin perdida de informacion.
Los dos estados iniciales corresponden a elegir rojo o azul como primer simbolo:
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
Ahora consideremos un estado \(D_{\ell,r,c}(u,v)\).
Si todavia se puede anadir un simbolo rojo, entonces al anadir \(R\) se crea un estado nuevo en la capa \(\ell+1\). El nuevo numero de rojos es \(r+1\), el nuevo ultimo color es \(R\), y la nueva primera componente vale
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
Asi,
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Del mismo modo, si aun queda algun simbolo azul disponible y actualmente se han usado \(\ell-r\) azules, entonces al anadir \(B\) obtenemos
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
y por tanto
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Esta es exactamente la recurrencia usada por las implementaciones. Cada rama anade un color, actualiza el par lineal y suma la multiplicidad en la entrada de hash correspondiente al estado comprimido resultante.
Cuando la longitud total alcanza \(2n\), solo cuentan las secuencias balanceadas, de modo que el numero de rojos debe ser \(n\). La condicion algebraica final es que el valor actual de la recurrencia sea cero. Por eso
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
La segunda componente \(v\) no se restringe al final; se conserva unicamente porque los pasos de repeticion la necesitan durante el proceso.
El caso de validacion \(n=2\) es lo bastante pequeno como para examinarlo a mano. Las cadenas balanceadas tienen longitud 4 y contienen dos \(R\) y dos \(B\). Siempre se empieza con \((x_1,x_0)=(2,-1)\).
Para el prefijo \(RR\), el segundo simbolo repite el primero, asi que
$$ (2,-1)\to (0,2). $$
Luego \(RRB\) cambia de color, y se obtiene
$$ (0,2)\to (0,0), $$
de modo que un azul adicional mantiene la primera componente en cero. Por tanto, \(RRBB\) es valido.
Para \(RBBR\), la evolucion es
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $$
asi que tambien contribuye. En cambio,
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
y la primera componente final no es cero. Por simetria al intercambiar rojo y azul, las cuatro cadenas validas son
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$$
con lo cual
$$F(2)=4.$$
Las implementaciones en C++, Python y Java mantienen una sola capa de la programacion dinamica cada vez, guardada en una tabla hash cuya clave es el estado comprimido: numero actual de rojos, ultimo color y el par ordenado de valores consecutivos de la recurrencia. La longitud del prefijo no necesita almacenarse dentro de la clave porque el bucle exterior ya fija la capa actual.
En cada capa se intenta anadir un simbolo rojo y un simbolo azul siempre que la cuota correspondiente no se haya agotado. La actualizacion numerica coincide exactamente con la derivacion matematica anterior: repetir color usa la matriz \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\), mientras que cambiar de color usa \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\). Cuando dos prefijos distintos alcanzan el mismo estado comprimido, sus multiplicidades se suman en ese mismo momento.
Despues de la ultima capa, la implementacion recorre los estados restantes y suma las multiplicidades de aquellos que tienen colores balanceados y primera componente de la recurrencia igual a cero. Las comprobaciones pequenas \(F(2)=4\) y \(F(8)=11892\) se usan para verificar la logica de transicion antes de evaluar \(F(26)\).
Hay exactamente \(2n-1\) capas de transicion y cada estado alcanzable genera como mucho dos transiciones salientes. Si \(S_\ell\) denota el numero de estados comprimidos distintos en la longitud de prefijo \(\ell\), el tiempo de ejecucion es
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
salvo el coste constante esperado de la tabla hash, y el uso de memoria es
$$O\!\left(\max_\ell S_\ell\right),$$
porque solo se conservan la capa actual y la siguiente. Esto es muy inferior a una fuerza bruta sobre las \(2^{2n}\) cadenas binarias, e incluso menor que recorrer directamente todas las cadenas balanceadas \(\binom{2n}{n}\), ya que muchos prefijos distintos colapsan en el mismo estado lineal comprimido.
这里要求计算的量可以写成一个计数函数 \(F(n)\)：统计长度为 \(2n\) 的红蓝序列，其中红色恰好出现 \(n\) 次，蓝色也恰好出现 \(n\) 次。可是“红蓝各半”还不是全部条件。颜色序列从左到右读取时，会同步驱动一个二阶线性过程，只有最终递推值等于零的序列才会被计入答案。
因此这道题同时包含两个层面。第一个层面是组合约束，也就是颜色数量必须平衡。第二个层面是代数约束：每个前缀都带着一个两分量状态，而下一步如何更新，取决于新颜色是延续前一个颜色，还是切换到另一种颜色。真正困难的地方，是在满足平衡条件的同时，把这个线性状态也精确地跟踪到底。
从实现可以看出，最自然的建模方式是对前缀做动态规划。关键不在于枚举整条长度 \(2n\) 的序列，而在于找出“一个前缀为了支持后续所有合法延伸，最少必须保留哪些信息”。
一旦第一种颜色被选定，线性过程的种子在两种起步方式下其实相同：
$$x_1=2,\qquad x_0=-1.$$
不过颜色本身仍然必须保留，因为后面的更新规则要区分两种情况：继续同一种颜色，或者切换颜色。如果当前前缀以颜色 \(c\) 结束，并且已经保存了有序对 \((x_\ell,x_{\ell-1})\)，那么再追加一个颜色之后，新的有序对就变成 \((x_{\ell+1},x_\ell)\)。
代数更新完全由“是否换色”决定。
如果新颜色与前一个颜色相同，那么
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
如果新颜色与前一个颜色不同，那么
$$x_{\ell+1}=-2x_\ell.$$
写成矩阵形式，就是
$$\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{对应“重复颜色”},$$
以及
$$\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{对应“切换颜色”}.$$
这一步也解释了为什么状态里必须保留两个相邻的递推值，而不能只保留一个。因为在“重复颜色”的更新中，\(x_\ell\) 和 \(x_{\ell-1}\) 两者都会被用到。
对一个长度为 \(\ell\) 的前缀，设已经使用了 \(r\) 个红色，最后一个颜色是 \(c\in\{R,B\}\)，当前保存的递推对是 \((u,v)=(x_\ell,x_{\ell-1})\)。定义
$$D_{\ell,r,c}(u,v)$$
表示满足这一整组摘要信息的前缀个数。这个压缩状态是恰到好处的，因为任何合法延伸只会依赖于
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$$
一旦这些量确定下来，更早之前的颜色排列细节就不再影响后续。因此，不同的前缀如果落在同一个压缩状态里，就可以安全地合并，它们的计数直接相加即可。
两个初始状态分别对应第一步选红色或选蓝色：
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
现在设我们已经有一个状态 \(D_{\ell,r,c}(u,v)\)。
如果红色还没有用满，那么追加一个 \(R\) 后会进入第 \(\ell+1\) 层的新状态。新的红色数是 \(r+1\)，新的末尾颜色是 \(R\)，而新的第一递推分量满足
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
因此有
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
同理，如果蓝色还可以继续使用，而当前已经用了 \(\ell-r\) 个蓝色，那么追加一个 \(B\) 时
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
于是
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
这就是实现中真正执行的完整递推。每一次扩展都只做三件事：加一个颜色、更新线性状态对、把路径数累加到目标压缩状态上。
当总长度达到 \(2n\) 时，只有红蓝平衡的序列才允许留下来，所以红色数量必须等于 \(n\)。与此同时，代数上的接受条件是当前递推值为零。因此
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
这里第二个分量 \(v\) 在终点处不需要再单独筛选；它之所以一直被保留，只是因为中间遇到“重复颜色”的步骤时必须使用它。
验证样例 \(n=2\) 足够小，可以直接手算。此时平衡序列长度为 4，包含两个 \(R\) 和两个 \(B\)。初始状态总是 \((x_1,x_0)=(2,-1)\)。
先看前缀 \(RR\)。第二个符号与第一个符号同色，所以
$$ (2,-1)\to (0,2). $$
接着 \(RRB\) 发生了一次换色，于是
$$ (0,2)\to (0,0), $$
再补一个蓝色后第一分量仍然保持为零，所以 \(RRBB\) 是有效序列。
再看 \(RBBR\)：
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $$
因此它也有效。相反，
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
最终第一分量不是零，所以不能计入答案。再利用红蓝互换的对称性，就得到全部四个有效序列
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$$
从而
$$F(2)=4.$$
C++、Python 和 Java 实现都只保留动态规划的当前层与下一层。哈希表的键就是压缩状态：当前已经用了多少个红色、最后一个颜色是什么，以及两个相邻递推值组成的有序对。前缀长度并不需要写进键里，因为外层循环本身已经说明当前处理的是哪一层。
在每一层里，只要某种颜色的配额还没有耗尽，就尝试追加该颜色。数值更新与上面的数学推导完全一致：重复颜色使用矩阵 \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\)，切换颜色使用矩阵 \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\)。如果两条不同的前缀路径落到同一个压缩状态，它们的计数会立即在该哈希条目中合并。
最后一层结束后，实现会扫描所有剩余状态，把那些颜色数恰好平衡且第一递推分量为零的状态计数加起来。小样例 \(F(2)=4\) 和 \(F(8)=11892\) 被用作校验，确保转移规则与数学模型一致，然后再求出 \(F(26)\)。
总共有恰好 \(2n-1\) 层转移，每个可达状态最多产生两条后继。若用 \(S_\ell\) 表示长度为 \(\ell\) 的前缀层中不同压缩状态的数量，那么运行时间是
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
加上哈希表的常数级开销；内存复杂度则是
$$O\!\left(\max_\ell S_\ell\right),$$
因为始终只保留两层。这个规模远小于对全部 \(2^{2n}\) 条原始红蓝串做暴力枚举，甚至也小于直接遍历所有平衡串 \(\binom{2n}{n}\)，因为大量不同前缀会在同一个压缩线性状态中汇合。
Здесь вычисляется функция подсчета \(F(n)\): число красно-синих последовательностей длины \(2n\), в которых ровно \(n\) красных и ровно \(n\) синих элементов. Однако одного цветового баланса недостаточно. Пока последовательность читается слева направо, она одновременно управляет линейным процессом второго порядка, и в ответ включаются только те последовательности, для которых конечное значение этой рекуррентной величины равно нулю.
Поэтому задача состоит из двух сцепленных частей. Первая часть комбинаторная: нужно соблюдать баланс цветов. Вторая часть алгебраическая: каждый префикс несет с собой двухкомпонентное состояние, а правило обновления зависит от того, повторяет ли следующий цвет предыдущий или меняет его. Нужно посчитать все сбалансированные цветовые строки, которые также удовлетворяют конечному линейному условию.
Из реализаций видно, что естественная формулировка здесь - динамическое программирование по префиксам. Главная идея состоит в том, чтобы выделить минимальный набор данных, который префикс обязан помнить для корректной обработки любого продолжения.
После выбора первого цвета линейный процесс стартует в обоих случаях с одинаковых начальных значений:
$$x_1=2,\qquad x_0=-1.$$
Но сам цвет все равно важен, потому что дальнейшие шаги различают два события: повторить текущий цвет или переключиться на другой. Если текущий префикс оканчивается цветом \(c\) и хранится пара \((x_\ell,x_{\ell-1})\), то после добавления еще одного символа новая пара становится \((x_{\ell+1},x_\ell)\).
Алгебраически возможны только два перехода.
Если новый цвет совпадает с предыдущим, то
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
Если новый цвет другой, то
$$x_{\ell+1}=-2x_\ell.$$
В матричной записи это
$$\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{при повторе цвета},$$
и
$$\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{при смене цвета}.$$
Отсюда сразу видно, почему необходимо хранить именно два соседних значения рекуррентной последовательности: в случае повтора используются и \(x_\ell\), и \(x_{\ell-1}\).
Для префикса длины \(\ell\) пусть \(r\) - число уже использованных красных символов, \(c\in\{R,B\}\) - последний цвет, а \((u,v)=(x_\ell,x_{\ell-1})\). Обозначим через
$$D_{\ell,r,c}(u,v)$$
количество префиксов с точно таким описанием. Это и есть естественное сжатое состояние, потому что любое допустимое продолжение зависит только от
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$$
Как только эти величины известны, более ранняя история префикса уже не нужна. Поэтому разные цветовые строки, попавшие в одно и то же состояние, можно без потерь объединять.
Два начальных состояния соответствуют выбору первого цвета:
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
Рассмотрим теперь состояние \(D_{\ell,r,c}(u,v)\).
Если красный цвет еще не исчерпан, то добавление \(R\) переводит нас на слой \(\ell+1\). Новое число красных равно \(r+1\), новый последний цвет - \(R\), а новая первая компонента равна
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
Следовательно,
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Аналогично, если синий цвет еще можно использовать и в префиксе уже стоит \(\ell-r\) синих символов, то при добавлении \(B\)
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
и потому
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
Это и есть полная рекурсия, используемая в реализациях. На каждом шаге добавляется цвет, обновляется линейная пара и затем число путей суммируется в записи хеш-таблицы для нового сжатого состояния.
Когда общая длина достигает \(2n\), остаются только сбалансированные последовательности, то есть число красных должно быть равно \(n\). Алгебраическое условие принятия состоит в том, что текущее значение рекурсии равно нулю. Поэтому
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
Вторая компонента \(v\) в конце никак не фильтруется; она нужна лишь потому, что промежуточные шаги с повтором цвета используют оба соседних значения.
Проверочный случай \(n=2\) достаточно мал для прямого анализа. Сбалансированные строки имеют длину 4 и содержат два \(R\) и два \(B\). Начальное состояние всегда равно \((x_1,x_0)=(2,-1)\).
Для префикса \(RR\) второй символ повторяет первый, поэтому
$$ (2,-1)\to (0,2). $$
Затем в \(RRB\) происходит смена цвета, и мы получаем
$$ (0,2)\to (0,0), $$
а еще один синий символ сохраняет первую компоненту нулевой. Значит, \(RRBB\) дает вклад.
Для \(RBBR\) имеем цепочку
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $$
поэтому эта последовательность тоже подходит. А вот
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
и конечная первая компонента уже не равна нулю. По симметрии при перестановке красного и синего четыре допустимые строки таковы:
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$$
откуда
$$F(2)=4.$$
Реализации на C++, Python и Java хранят только один слой динамики за раз. Ключом в хеш-таблице служит сжатое состояние: текущее число красных символов, последний цвет и упорядоченная пара из двух соседних значений рекуррентного процесса. Текущую длину префикса не нужно включать в ключ, потому что внешний цикл уже фиксирует номер слоя.
На каждом слое алгоритм пытается дописать красный и синий символ, если соответствующий лимит еще не достигнут. Числовое обновление в точности совпадает с математическим выводом выше: повтор цвета использует матрицу \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\), а смена цвета - матрицу \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\). Если два разных префикса приходят в одно и то же сжатое состояние, их кратности сразу складываются.
После последнего слоя код проходит по оставшимся состояниям и суммирует кратности тех из них, где цвета сбалансированы и первая рекуррентная компонента равна нулю. Малые проверки \(F(2)=4\) и \(F(8)=11892\) подтверждают правильность переходов перед вычислением \(F(26)\).
Всего имеется ровно \(2n-1\) переходных слоев, и каждое достижимое состояние порождает не более двух исходящих переходов. Если \(S_\ell\) обозначает число различных сжатых состояний на длине префикса \(\ell\), то время работы равно
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
с точностью до обычного хеш-оверхеда, а память составляет
$$O\!\left(\max_\ell S_\ell\right),$$
поскольку одновременно держатся только текущий и следующий слои. Это существенно меньше полного перебора всех \(2^{2n}\) цветовых строк и даже меньше прямого просмотра всех сбалансированных строк \(\binom{2n}{n}\), потому что множество разных префиксов сливается в одни и те же сжатые линейные состояния.
الكمية المحسوبة هنا هي دالة عد اسمها \(F(n)\) لعدد سلاسل الالوان الحمراء والزرقاء ذات الطول \(2n\)، بحيث تحتوي السلسلة على \(n\) رموز حمراء و\(n\) رموز زرقاء بالضبط. لكن التوازن اللوني وحده لا يكفي. فاثناء قراءة السلسلة من اليسار الى اليمين، توجد عملية خطية من الرتبة الثانية تتطور بالتوازي، ولا تدخل في الجواب الا السلاسل التي يكون فيها مقدار هذه العلاقة في النهاية مساويا للصفر.
لهذا تجمع المسألة بين قيدين مختلفين. الاول تركيبي ويتعلق بتوازن عدد الالوان. والثاني جبري: كل بادئة تحمل حالة مكونة من عنصرين، وتحديث هذه الحالة يعتمد على ما اذا كان اللون الجديد يكرر اللون السابق او ينتقل الى اللون الاخر. المطلوب هو عد جميع السلاسل المتوازنة التي تحقق كذلك شرط النهاية الخطي.
توضح التطبيقات ان الصياغة الطبيعية هنا هي برمجة ديناميكية على البوادئ. الفكرة الحاسمة هي تحديد اقل قدر من المعلومات الذي يجب على البادئة الاحتفاظ به لكي نستطيع معالجة اي امتداد لاحق بصورة صحيحة.
بعد اختيار اللون الاول تبدأ العملية الخطية من نفس القيم الابتدائية في الحالتين:
$$x_1=2,\qquad x_0=-1.$$
ومع ذلك يبقى لون النهاية مهما، لان الخطوات اللاحقة تميز بين حالتين: تكرار اللون الحالي والتحول الى اللون الاخر. اذا كانت البادئة الحالية تنتهي باللون \(c\) وكان الزوج المخزن هو \((x_\ell,x_{\ell-1})\)، فان اضافة رمز جديد تنتج الزوج الجديد \((x_{\ell+1},x_\ell)\).
يوجد انتقالان جبريان فقط.
اذا كان اللون الجديد مطابقا للون السابق، فلدينا
$$x_{\ell+1}=-(x_\ell+2x_{\ell-1}).$$
واذا كان اللون الجديد مختلفا، فلدينا
$$x_{\ell+1}=-2x_\ell.$$
وبصيغة المصفوفات يصبح ذلك
$$\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}.$$
وهذه هي صيغة حالة التكرار. وكذلك
$$\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}.$$
وهذه هي صيغة حالة التبديل.
ومن هنا يظهر سبب الحاجة الى تخزين قيمتين متتاليتين لا قيمة واحدة فقط، لان حالة التكرار تستخدم كلا من \(x_\ell\) و\(x_{\ell-1}\).
لبادئة طولها \(\ell\)، ولتكن \(r\) هي عدد الرموز الحمراء المستخدمة حتى الان، وليكن \(c\in\{R,B\}\) هو اللون الاخير، وليكن \((u,v)=(x_\ell,x_{\ell-1})\). نعرف
$$D_{\ell,r,c}(u,v)$$
على انه عدد البوادئ التي تملك هذا الوصف بالضبط. هذا هو الضغط الصحيح للحالة، لان اي امتداد قانوني يعتمد فقط على
$$\ell,\qquad r,\qquad c,\qquad x_\ell,\qquad x_{\ell-1}.$$
وبمجرد معرفة هذه الكميات، لا تعود التفاصيل الاقدم في البادئة مؤثرة. لذلك يمكن دمج سلاسل مختلفة تصل الى الحالة المضغوطة نفسها من دون فقدان للمعلومات.
الحالتان الابتدائيتان تمثلان اختيار اللون الاول احمر او ازرق:
$$D_{1,1,R}(2,-1)=1,\qquad D_{1,0,B}(2,-1)=1.$$
الان لنفترض ان لدينا الحالة \(D_{\ell,r,c}(u,v)\).
اذا كان لا يزال مسموحا اضافة رمز احمر، فان اضافة \(R\) تنشئ حالة جديدة في الطبقة \(\ell+1\). يصبح عدد الاحمر الجديد \(r+1\)، ويصبح اللون الاخير الجديد هو \(R\)، اما المركبة الاولى الجديدة فتساوي
$$u'=\begin{cases} -(u+2v), & c=R,\\ -2u, & c=B. \end{cases}$$
ومن ثم
$$D_{\ell+1,r+1,R}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
وبالصورة نفسها، اذا كان ما زال هناك رمز ازرق متاح، وكان عدد الرموز الزرقاء الحالية هو \(\ell-r\)، فعند اضافة \(B\) نحصل على
$$u'=\begin{cases} -(u+2v), & c=B,\\ -2u, & c=R, \end{cases}$$
وبالتالي
$$D_{\ell+1,r,B}(u',u)\;{+}{=}\;D_{\ell,r,c}(u,v).$$
هذه هي العلاقة الكاملة التي تنفذها التطبيقات فعليا. في كل فرع نضيف لونا واحدا، ونحدث الزوج الخطي، ثم ندمج عدد الطرق في مدخل جدول التجزئة الموافق للحالة المضغوطة الناتجة.
عندما يصل الطول الكلي الى \(2n\)، لا تبقى الا السلاسل المتوازنة، ولذلك يجب ان يكون عدد الرموز الحمراء مساويا لـ \(n\). وشرط القبول الجبري هو ان تكون قيمة العلاقة الحالية صفرا. لهذا نحصل على
$$F(n)=\sum_{c\in\{R,B\}}\sum_v D_{2n,n,c}(0,v).$$
المركبة الثانية \(v\) لا تخضع لاي شرط في النهاية؛ انما يتم الاحتفاظ بها فقط لان خطوات تكرار اللون تحتاج اليها اثناء المسار.
حالة التحقق \(n=2\) صغيرة بما يكفي للفحص المباشر. السلاسل المتوازنة هنا طولها 4 وتحتوي على رمزين \(R\) ورمزين \(B\). ونبدأ دائما من الحالة \((x_1,x_0)=(2,-1)\).
في البادئة \(RR\) يكون الرمز الثاني مكررا للون الاول، ولذلك
$$ (2,-1)\to (0,2). $$
ثم في \(RRB\) يحدث تبديل للون، فنحصل على
$$ (0,2)\to (0,0), $$
واضافة رمز ازرق اخر تبقي المركبة الاولى صفرا. اذن \(RRBB\) سلسلة صحيحة.
اما بالنسبة الى \(RBBR\) فالتطور هو
$$ (2,-1)\to(-4,2)\to(0,-4)\to(0,0), $$
ولذلك فهي ايضا صالحة. في المقابل،
$$RBRB:\quad (2,-1)\to(-4,2)\to(8,-4)\to(-16,8),$$
فتكون المركبة الاولى النهائية غير صفرية. وبفعل التناظر عند تبديل الاحمر بالازرق، تكون السلاسل الصحيحة الاربع هي
$$RRBB,\qquad RBBR,\qquad BRRB,\qquad BBRR,$$
ومن ثم
$$F(2)=4.$$
تحافظ تطبيقات C++ وPython وJava على طبقة واحدة فقط من البرمجة الديناميكية في كل لحظة. مفتاح جدول التجزئة هو الحالة المضغوطة: عدد الرموز الحمراء الحالية، واللون الاخير، والزوج المرتب من قيمتين متتاليتين من العملية العودية. ولا حاجة الى تخزين طول البادئة داخل المفتاح، لان الحلقة الخارجية تحدد الطبقة الحالية مسبقا.
في كل طبقة يحاول التنفيذ اضافة رمز احمر ورمز ازرق ما دام الحد المسموح لكل منهما لم يكتمل بعد. والتحديث العددي يطابق الاشتقاق الرياضي تماما: تكرار اللون يستخدم المصفوفة \(\begin{bmatrix}-1&-2\\ 1&0\end{bmatrix}\)، بينما تبديل اللون يستخدم \(\begin{bmatrix}-2&0\\ 1&0\end{bmatrix}\). وعندما تصل بادئتان مختلفتان الى الحالة المضغوطة نفسها، يتم جمع تعداديهما مباشرة.
بعد انتهاء الطبقة الاخيرة، يفحص التنفيذ جميع الحالات المتبقية ويجمع اعداد الطرق الخاصة بالحالات التي تحقق توازنا لونيا كاملا ومركبة اولى صفرية. كما تستخدم القيمتان \(F(2)=4\) و\(F(8)=11892\) كاختبارين صغيرين للتأكد من صحة منطق الانتقال قبل حساب \(F(26)\).
يوجد بالضبط \(2n-1\) طبقة انتقال، وكل حالة قابلة للوصول تولد على الاكثر انتقالين. اذا رمزنا بعدد الحالات المضغوطة المختلفة عند طول البادئة \(\ell\) بالرمز \(S_\ell\)، فان زمن التنفيذ يساوي
$$O\!\left(\sum_{\ell=1}^{2n-1} S_\ell\right)$$
مع اهمال الكلفة الثابتة المعتادة لجدول التجزئة، بينما يكون استهلاك الذاكرة
$$O\!\left(\max_\ell S_\ell\right),$$
لان التنفيذ يحتفظ فقط بالطبقة الحالية والطبقة التالية. وهذا اصغر بكثير من الفحص الشامل لجميع السلاسل الثنائية وعددها \(2^{2n}\)، بل واصغر ايضا من المرور المباشر على جميع السلاسل المتوازنة \(\binom{2n}{n}\)، لان كثيرا من البوادئ المختلفة ينهار في الحالة الخطية المضغوطة نفسها.