We have \(B\) black objects and \(W\) white objects. A single group is determined only by its colour composition \((b,w)\) with \(b,w \ge 0\) and \(b+w>0\). A complete grouping is therefore a multiset of such compositions whose total number of black objects is \(B\) and whose total number of white objects is \(W\). Reordering the groups does not create a new solution.
For Project Euler, the target instance is \(60\) black objects and \(40\) white objects, but the derivation used by the implementations works for general \(B\) and \(W\). The central question is not which object goes into which group, but how many times each possible colour composition occurs.
The cleanest formulation is to treat every possible group composition as a type and then count how many copies of each type are used.
Let
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
For each type \(t=(t_b,t_w)\in\mathcal{T}\), let \(k_t\) be the number of groups having exactly \(t_b\) black objects and \(t_w\) white objects. Then a valid grouping is exactly a nonnegative integer solution of
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
This already captures the “group order does not matter” rule: the data of a solution is the multiplicity vector \((k_t)_{t\in\mathcal{T}}\), not an ordered list of groups.
Each type \(t=(t_b,t_w)\) may be used \(0,1,2,\dots\) times, so it contributes the geometric series
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}.$$
Multiplying over all admissible types gives
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
The required answer is the coefficient
$$\left[x^B y^W\right]F(x,y).$$
So Problem 181 is a two-dimensional partition problem: we partition the target vector \((B,W)\) into an unordered multiset of nonzero vectors \((t_b,t_w)\).
Choose any fixed order on the types in \(\mathcal{T}\). After processing some prefix of that order, define
$$\mathrm{dp}[b][w]=\text{number of ways to obtain exactly }(b,w)\text{ using only processed types}.$$
Initially, only the empty multiset is available, so
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ for all other states.}$$
When the current type is \((t_b,t_w)\), every existing state \((b,w)\) can be extended by taking \(k\) copies of that type, where \(k\ge 1\) and the totals remain within bounds. Thus the transition is
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
The largest legal multiplicity from the base state \((b,w)\) is
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
That bound is exactly what the implementations compute before running the inner loop over \(k\).
The implementations update a single 2D table in place and sweep \(b\) and \(w\) downward. This matters. During the processing of one fixed type \((t_b,t_w)\), a newly written state must not be reused as another base state for the same type, because that would count the same multiplicity choice more than once.
Descending loops prevent that reuse. Every base state contributes directly to all states obtained by adding \(1,2,\dots,m_{\max}\) copies of the current type, and it does so exactly once. In other words, the explicit loop over \(k\) already accounts for all multiplicities of the current type, so the reverse traversal preserves the invariant that \(\mathrm{dp}[b][w]\) counts unordered multisets of processed types rather than ordered sequences.
The small instance \(B=3\), \(W=1\) has exactly seven valid groupings. Written as multisets of group types, they are:
Each item corresponds to one multiplicity assignment \((k_t)\). The dynamic program reproduces this count because it considers every admissible type \((t_b,t_w)\) once and chooses how many copies of that type are used. The larger Euler instance follows the same logic; only the state space is bigger.
The C++, Python, and Java implementations iterate over all pairs \((t_b,t_w)\) with \(0\le t_b\le B\), \(0\le t_w\le W\), except \((0,0)\). One implementation stores these pairs in a list first, while the others stream through the nested loops directly, but mathematically the effect is identical: every possible group composition is processed exactly once.
The table has size \((B+1)\times(W+1)\), and the entry at \((b,w)\) is the current coefficient of \(x^b y^w\) in the partial product over already processed group types. The seed value \(\mathrm{dp}[0][0]=1\) represents the empty grouping. For each type, the implementation reads the current entry, computes the maximum feasible repeat count \(m_{\max}\), and adds the same base count to all reachable states \((b+k t_b,\ w+k t_w)\).
The code does not need a second table because the reverse sweep over \(b\) and \(w\) guarantees that all transitions for the current type originate only from states that existed before this type started updating. That is the implementation form of the generating-function factor \((1-x^{t_b}y^{t_w})^{-1}\).
The recurrence is symmetric in black and white objects: swapping the two colours simply exchanges the two coordinates of every state and every type. That is why the same method works regardless of which colour is treated as the first array index. One implementation also validates the recurrence on tiny cases, including the \(3\)-black, \(1\)-white sample, by comparing the dynamic program with an exhaustive search over multiplicities.
There are
$$T=(B+1)(W+1)-1$$
group types and \((B+1)(W+1)\) DP states. For one fixed type and one fixed base state, the inner multiplicity loop runs at most \(\max(B,W)\) times, so a simple worst-case bound is
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
This bound is intentionally loose; in practice, large group types have only a few feasible repeats, so the runtime is much smaller than the worst case suggests for \(B=60\), \(W=40\). Memory usage is \(O(BW)\), because the implementations keep one in-place 2D table instead of a separate layer for each processed type.
Gegeben sind \(B\) schwarze und \(W\) weiße Objekte. Eine einzelne Gruppe wird nur durch ihre Farbzusammensetzung \((b,w)\) mit \(b,w \ge 0\) und \(b+w>0\) beschrieben. Eine vollständige Gruppierung ist also ein Multiset solcher Zusammensetzungen, dessen schwarze Gesamtzahl \(B\) und dessen weiße Gesamtzahl \(W\) ergibt. Eine andere Reihenfolge derselben Gruppen zählt nicht als neue Lösung.
Im Project-Euler-Fall sind \(B=60\) und \(W=40\), aber die Herleitung der Implementierungen funktioniert für beliebige \(B\) und \(W\). Entscheidend ist nicht, welches konkrete Objekt in welcher Gruppe liegt, sondern wie oft jede mögliche Farbzusammensetzung vorkommt.
Die natürlichste Beschreibung besteht darin, jede mögliche Gruppenzusammensetzung als Typ zu behandeln und dann ihre Vielfachheiten zu zählen.
Sei
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
Für jeden Typ \(t=(t_b,t_w)\in\mathcal{T}\) bezeichne \(k_t\) die Anzahl der Gruppen mit genau \(t_b\) schwarzen und \(t_w\) weißen Objekten. Dann ist eine gültige Gruppierung genau eine nichtnegative ganzzahlige Lösung von
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
Damit ist die Bedingung „die Reihenfolge der Gruppen ist egal“ bereits vollständig erfasst: Eine Lösung ist der Vielfachkeitsvektor \((k_t)_{t\in\mathcal{T}}\) und nicht eine geordnete Liste von Gruppen.
Jeder Typ \(t=(t_b,t_w)\) kann \(0,1,2,\dots\) Mal verwendet werden und trägt daher die geometrische Reihe
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}$$
bei. Über alle zulässigen Typen multipliziert erhält man
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
Gesucht ist also der Koeffizient
$$\left[x^B y^W\right]F(x,y).$$
Problem 181 ist damit ein zweidimensionales Partitionsproblem: Der Zielvektor \((B,W)\) wird in ein ungeordnetes Multiset nichtverschwindender Vektoren \((t_b,t_w)\) zerlegt.
Fixiere irgendeine feste Reihenfolge der Typen in \(\mathcal{T}\). Nach der Verarbeitung eines Präfixes dieser Reihenfolge sei
$$\mathrm{dp}[b][w]=\text{Anzahl der Möglichkeiten, genau }(b,w)\text{ nur mit den bereits verarbeiteten Typen zu erhalten}.$$
Zu Beginn steht nur das leere Multiset zur Verfügung, also
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ für alle anderen Zustände.}$$
Ist der aktuelle Typ \((t_b,t_w)\), dann kann jeder bestehende Zustand \((b,w)\) durch \(k\) Kopien dieses Typs erweitert werden, wobei \(k\ge 1\) und die Grenzen nicht überschritten werden. Der Übergang lautet daher
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
Die größte zulässige Vielfachheit vom Basiszustand \((b,w)\) aus ist
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
Genau diese Schranke berechnen die Implementierungen vor der inneren Schleife über \(k\).
Die Implementierungen verwenden nur eine einzige 2D-Tabelle und durchlaufen \(b\) und \(w\) absteigend. Das ist der entscheidende Invariant. Während ein fester Typ \((t_b,t_w)\) verarbeitet wird, darf ein neu geschriebener Zustand nicht noch einmal als Basiszustand desselben Typs dienen, denn sonst würde dieselbe Vielfachkeitswahl mehrfach gezählt.
Die absteigende Schleifenrichtung verhindert genau das. Jeder Basiszustand trägt direkt zu allen Zuständen bei, die durch \(1,2,\dots,m_{\max}\) Kopien des aktuellen Typs entstehen, und er tut das genau einmal. Damit repräsentiert die Tabelle weiterhin ungeordnete Multisets der bereits verarbeiteten Typen statt geordneter Folgen von Entscheidungen.
Für den kleinen Fall \(B=3\), \(W=1\) gibt es genau sieben gültige Gruppierungen. Als Multisets von Gruppentypen lauten sie:
Jeder Eintrag entspricht genau einer Vielfachkeitsbelegung \((k_t)\). Das dynamische Programm reproduziert diese Zahl, weil es jeden zulässigen Typ \((t_b,t_w)\) genau einmal behandelt und danach festlegt, wie viele Kopien dieses Typs benutzt werden. Beim großen Euler-Fall ist die Idee identisch; nur der Zustandsraum ist größer.
Die C++-, Python- und Java-Implementierungen iterieren über alle Paare \((t_b,t_w)\) mit \(0\le t_b\le B\) und \(0\le t_w\le W\), außer \((0,0)\). Eine Implementierung legt diese Paare zuerst in einer Liste ab, die anderen laufen direkt durch die verschachtelten Schleifen. Mathematisch ist das derselbe Schritt: Jede mögliche Farbzusammensetzung einer Gruppe wird genau einmal verarbeitet.
Die Tabelle hat Größe \((B+1)\times(W+1)\), und der Eintrag \((b,w)\) ist der aktuelle Koeffizient von \(x^b y^w\) im Teilprodukt über alle bereits verarbeiteten Typen. Der Startwert \(\mathrm{dp}[0][0]=1\) steht für die leere Gruppierung. Für jeden Typ liest die Implementierung den aktuellen Basiswert, berechnet die maximal mögliche Wiederholungszahl \(m_{\max}\) und addiert diesen Basiswert zu allen erreichbaren Zuständen \((b+k t_b,\ w+k t_w)\).
Eine zweite Tabelle ist nicht nötig, weil die absteigende Traversierung von \(b\) und \(w\) garantiert, dass alle Übergänge des aktuellen Typs nur von Zuständen ausgehen, die schon vor diesem Typ existierten. Genau so wird der Faktor \((1-x^{t_b}y^{t_w})^{-1}\) der erzeugenden Funktion in Code umgesetzt.
Die Rekurrenz ist symmetrisch in Schwarz und Weiß: Ein Vertauschen der beiden Farben vertauscht nur die beiden Koordinaten jedes Zustands und jedes Typs. Deshalb funktioniert dieselbe Methode unabhängig davon, welche Farbe als erste Array-Achse verwendet wird. Eine Implementierung überprüft die Rekurrenz zusätzlich auf sehr kleinen Fällen, darunter dem Beispiel mit \(3\) schwarzen und \(1\) weißen Objekt, durch Vergleich mit einer vollständigen Suche über alle Vielfachheiten.
Es gibt
$$T=(B+1)(W+1)-1$$
Gruppentypen und \((B+1)(W+1)\) Zustände in der DP-Tabelle. Für einen festen Typ und einen festen Basiszustand läuft die innere Schleife über die Vielfachheit höchstens \(\max(B,W)\) Mal. Damit ergibt sich als einfache Worst-Case-Schranke
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
Diese Schranke ist bewusst grob; in der Praxis erlauben große Gruppentypen nur sehr wenige Wiederholungen, sodass die tatsächliche Laufzeit für \(B=60\), \(W=40\) deutlich kleiner ist. Der Speicherverbrauch beträgt \(O(BW)\), weil die Implementierungen eine einzige In-Place-Tabelle statt einer separaten Ebene pro Typ verwenden.
Elimizde \(B\) siyah ve \(W\) beyaz nesne var. Tek bir grup yalnızca renk bileşimiyle, yani \(b,w \ge 0\) ve \(b+w>0\) koşulunu sağlayan \((b,w)\) çiftiyle tanımlanıyor. Tam bir gruplanma ise bu tür çiftlerden oluşan bir multiset olup toplam siyah sayısı \(B\), toplam beyaz sayısı \(W\) olmalıdır. Aynı grupları farklı sırada yazmak yeni bir çözüm oluşturmaz.
Project Euler örneğinde hedef \(60\) siyah ve \(40\) beyaz nesnedir; ancak uygulamaların kullandığı türetim genel \(B\) ve \(W\) için geçerlidir. Asıl mesele tek tek nesnelerin hangi gruba gittiği değil, her olası renk bileşiminin kaç kez kullanıldığıdır.
En doğal model, her olası grup bileşimini bir tür olarak görmek ve sonra bu türlerin çokluklarını saymaktır.
Şöyle tanımlayalım:
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
Her \(t=(t_b,t_w)\in\mathcal{T}\) türü için \(k_t\), tam olarak \(t_b\) siyah ve \(t_w\) beyaz nesne içeren grup sayısı olsun. O zaman geçerli bir gruplanma, aşağıdaki denklemlerin negatif olmayan tam sayı çözümüdür:
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
Böylece “grup sırası önemli değil” koşulu tam olarak yakalanır: çözüm, grupların sıralı listesi değil, \((k_t)_{t\in\mathcal{T}}\) çokluk vektörüdür.
Her \(t=(t_b,t_w)\) türü \(0,1,2,\dots\) kez kullanılabilir. Bu yüzden katkısı
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}$$
olur. Tüm geçerli türler üzerinden çarpınca
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}$$
elde edilir. Aranan cevap da
$$\left[x^B y^W\right]F(x,y)$$
katsayısıdır. Yani Problem 181, hedef vektör \((B,W)\)'yi sıfır olmayan \((t_b,t_w)\) vektörlerinin sırasız bir multiset'i olarak parçalama problemidir.
\(\mathcal{T}\) içindeki türler için sabit bir sıra seçelim. Bu sıranın bir öneki işlendiğinde
$$\mathrm{dp}[b][w]=\text{yalnızca işlenmiş türlerle tam }(b,w)\text{ toplamına ulaşma sayısı}$$
olsun. Başlangıçta yalnızca boş multiset vardır:
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ diğer tüm durumlar için.}$$
Mevcut tür \((t_b,t_w)\) ise, herhangi bir \((b,w)\) temel durumundan bu türün \(k\) kopyası eklenebilir; burada \(k\ge 1\) ve sınırlar aşılmamalıdır. O halde geçiş
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w]$$
şeklindedir. \((b,w)\) durumundan başlayarak izin verilen en büyük tekrar sayısı
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
Uygulamalar içteki \(k\) döngüsünden önce tam olarak bu üst sınırı hesaplar.
Uygulamalar tek bir 2D tabloyu yerinde güncelliyor ve \(b\) ile \(w\) değerlerini büyükten küçüğe tarıyor. Kritik fikir burada. Sabit bir \((t_b,t_w)\) türü işlenirken, yeni yazılmış bir durumun aynı tür için tekrar temel durum olarak kullanılmaması gerekir; aksi halde aynı çokluk seçimi birden fazla kez sayılır.
Azalan döngüler bunu engeller. Her temel durum, mevcut türün \(1,2,\dots,m_{\max}\) kopyası eklenerek ulaşılan tüm durumlara doğrudan ve yalnızca bir kez katkı verir. Böylece tablo, işlenmiş türlerin sıralı dizilerini değil, sırasız multiset'lerini sayma invariant'ını korur.
Küçük \(B=3\), \(W=1\) örneğinde tam olarak yedi geçerli gruplanma vardır. Grup türlerinin multiset'i olarak bunlar şöyledir:
Her satır bir \((k_t)\) çokluk atamasına karşılık gelir. Dinamik program bu sayıyı aynen üretir; çünkü her geçerli \((t_b,t_w)\) türünü tam bir kez işler ve ardından o türden kaç kopya alınacağını seçer. Büyük Euler örneği de aynı mantıkla çözülür; yalnızca durum uzayı daha geniştir.
C++, Python ve Java uygulamaları \((0,0)\) hariç olmak üzere \(0\le t_b\le B\) ve \(0\le t_w\le W\) koşullarını sağlayan tüm \((t_b,t_w)\) çiftleri üzerinden geçer. Bir uygulama bu çiftleri önce bir listede saklar, diğerleri ise iç içe döngüler içinde doğrudan işler. Matematiksel anlamda sonuç aynıdır: her olası grup bileşimi tam bir kez ele alınır.
Tablonun boyutu \((B+1)\times(W+1)\)'dir ve \((b,w)\) girişi, şimdiye kadar işlenen türler için kısmi çarpımdaki \(x^b y^w\) katsayısını tutar. Başlangıç değeri \(\mathrm{dp}[0][0]=1\) boş gruplanmayı temsil eder. Her tür için uygulama mevcut taban değeri okur, izin verilen en büyük tekrar sayısı \(m_{\max}\)'ı hesaplar ve aynı taban değeri tüm erişilebilir \((b+k t_b,\ w+k t_w)\) durumlarına ekler.
İkinci bir tablo gerekmez; çünkü \(b\) ve \(w\) değerlerinin ters yönde taranması, mevcut türün tüm geçişlerinin yalnızca bu tür işlenmeden önce var olan durumlardan çıkmasını garanti eder. Bu, üreteç fonksiyondaki \((1-x^{t_b}y^{t_w})^{-1}\) çarpanının doğrudan kod karşılığıdır.
Rekürans siyah ve beyaz arasında simetriktir: renkleri yer değiştirmek, sadece her durumun ve her türün iki koordinatını yer değiştirir. Bu nedenle hangi rengin dizinin ilk ekseni olduğu sonucu değiştirmez. Uygulamalardan biri ayrıca bu reküransı küçük örneklerde, özellikle \(3\) siyah ve \(1\) beyaz örneğinde, çokluklar üzerinde tam arama ile karşılaştırarak doğrular.
Toplam
$$T=(B+1)(W+1)-1$$
adet grup türü ve \((B+1)(W+1)\) adet DP durumu vardır. Sabit bir tür ve sabit bir temel durum için içteki çokluk döngüsü en fazla \(\max(B,W)\) kez çalışır. Bu yüzden basit bir üst sınır
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr)$$
şeklindedir. Bu sınır bilerek gevşek tutulmuştur; pratikte büyük grup türlerinin tekrar sayısı çok az olduğu için \(B=60\), \(W=40\) için gerçek çalışma süresi bundan belirgin biçimde küçüktür. Bellek kullanımı \(O(BW)\)'dir; çünkü uygulamalar her tür için ayrı katman yerine yerinde güncellenen tek bir 2D tablo tutar.
Tenemos \(B\) objetos negros y \(W\) objetos blancos. Un grupo individual queda determinado solo por su composición de colores \((b,w)\), con \(b,w \ge 0\) y \(b+w>0\). Por tanto, una agrupación completa es un multiconjunto de esas composiciones cuya suma total de objetos negros es \(B\) y cuya suma total de objetos blancos es \(W\). Reordenar los grupos no produce una solución nueva.
En el problema de Project Euler se pide el caso \(B=60\), \(W=40\), pero la derivación usada por las implementaciones vale para cualquier \(B\) y \(W\). La cuestión central no es qué objeto concreto entra en qué grupo, sino cuántas veces aparece cada composición posible.
La formulación más limpia consiste en considerar cada composición posible de grupo como un tipo y contar cuántas copias de cada tipo se usan.
Definimos
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
Para cada tipo \(t=(t_b,t_w)\in\mathcal{T}\), sea \(k_t\) el número de grupos que contienen exactamente \(t_b\) objetos negros y \(t_w\) objetos blancos. Entonces una agrupación válida es exactamente una solución entera no negativa del sistema
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
Esta descripción incorpora de forma natural la condición de que el orden de los grupos no importa: la solución es el vector de multiplicidades \((k_t)_{t\in\mathcal{T}}\), no una lista ordenada de grupos.
Cada tipo \(t=(t_b,t_w)\) puede usarse \(0,1,2,\dots\) veces, así que aporta la serie geométrica
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}.$$
Multiplicando sobre todos los tipos admisibles obtenemos
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
La respuesta buscada es el coeficiente
$$\left[x^B y^W\right]F(x,y).$$
Así, el Problema 181 se convierte en un problema de partición bidimensional: descomponer el vector objetivo \((B,W)\) como un multiconjunto no ordenado de vectores no nulos \((t_b,t_w)\).
Tomemos cualquier orden fijo de los tipos de \(\mathcal{T}\). Tras procesar un prefijo de ese orden, definimos
$$\mathrm{dp}[b][w]=\text{número de formas de obtener exactamente }(b,w)\text{ usando solo los tipos ya procesados}.$$
Al principio solo existe el multiconjunto vacío, de modo que
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ en todos los demás estados.}$$
Si el tipo actual es \((t_b,t_w)\), cualquier estado base \((b,w)\) puede ampliarse tomando \(k\) copias de ese tipo, con \(k\ge 1\) y sin superar los límites. El paso de transición es
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
La mayor multiplicidad posible desde el estado base \((b,w)\) es
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
Esa es exactamente la cota que calculan las implementaciones antes del bucle interno sobre \(k\).
Las implementaciones actualizan una única tabla 2D en el lugar y recorren \(b\) y \(w\) en orden descendente. Ese detalle es esencial. Mientras se procesa un tipo fijo \((t_b,t_w)\), un estado recién escrito no debe reutilizarse como nuevo estado base para el mismo tipo, porque eso contaría varias veces la misma elección de multiplicidad.
El recorrido descendente evita esa reutilización. Cada estado base contribuye directamente a todos los estados alcanzables añadiendo \(1,2,\dots,m_{\max}\) copias del tipo actual, y lo hace exactamente una vez. Así, la tabla sigue contando multiconjuntos no ordenados de tipos procesados, no secuencias ordenadas de decisiones.
En el caso pequeño \(B=3\), \(W=1\), hay exactamente siete agrupaciones válidas. Escritas como multiconjuntos de tipos de grupo, son:
Cada línea corresponde a una asignación de multiplicidades \((k_t)\). El programa dinámico reproduce exactamente este conteo porque procesa cada tipo admisible \((t_b,t_w)\) una sola vez y decide cuántas copias usar de ese tipo. El caso grande de Euler sigue la misma lógica; únicamente crece el espacio de estados.
Las implementaciones en C++, Python y Java recorren todos los pares \((t_b,t_w)\) con \(0\le t_b\le B\) y \(0\le t_w\le W\), salvo \((0,0)\). Una implementación guarda primero esos pares en una lista, mientras que las otras avanzan directamente por los bucles anidados. Matemáticamente no hay diferencia: toda composición posible de grupo se procesa exactamente una vez.
La tabla tiene tamaño \((B+1)\times(W+1)\), y la entrada \((b,w)\) es el coeficiente actual de \(x^b y^w\) en el producto parcial de todos los tipos ya procesados. El valor inicial \(\mathrm{dp}[0][0]=1\) representa la agrupación vacía. Para cada tipo, la implementación lee el conteo base actual, calcula el número máximo de repeticiones \(m_{\max}\) y suma ese mismo conteo a todos los estados accesibles \((b+k t_b,\ w+k t_w)\).
No hace falta una segunda tabla, porque el barrido descendente de \(b\) y \(w\) garantiza que todas las transiciones del tipo actual parten solo de estados que ya existían antes de empezar a actualizar ese tipo. Esa es la traducción directa, a nivel de código, del factor \((1-x^{t_b}y^{t_w})^{-1}\) de la función generadora.
La recurrencia es simétrica en los objetos negros y blancos: intercambiar los colores solo intercambia las dos coordenadas de cada estado y de cada tipo. Por eso el mismo método funciona aunque una implementación tome primero una dimensión y otra implementación invierta ese orden. Además, una de las implementaciones comprueba la recurrencia en instancias diminutas, incluido el ejemplo de \(3\) negros y \(1\) blanco, comparando la DP con una búsqueda exhaustiva sobre multiplicidades.
Hay
$$T=(B+1)(W+1)-1$$
tipos de grupo y \((B+1)(W+1)\) estados en la tabla DP. Para un tipo fijo y un estado base fijo, el bucle interior sobre la multiplicidad se ejecuta como mucho \(\max(B,W)\) veces. Por tanto, una cota superior sencilla es
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
Es una cota deliberadamente holgada; en la práctica, los tipos grandes solo admiten unas pocas repeticiones, así que el tiempo real para \(B=60\), \(W=40\) es bastante menor. El uso de memoria es \(O(BW)\), porque las implementaciones mantienen una sola tabla 2D in-place en lugar de una capa separada por cada tipo procesado.
设有 \(B\) 个黑色物体和 \(W\) 个白色物体。单个分组只由它的颜色构成 \((b,w)\) 决定，其中 \(b,w \ge 0\) 且 \(b+w>0\)。因此，一个完整的分组方案就是若干种这类构成的多重集合，其黑色物体总数为 \(B\)，白色物体总数为 \(W\)。同样的一批组即使交换顺序，也不算新的方案。
Project Euler 的目标实例是 \(60\) 个黑色物体和 \(40\) 个白色物体，但实现所用的推导对任意 \(B\) 与 \(W\) 都成立。真正需要计数的不是“某个具体物体被放进了哪个组”，而是“每一种颜色构成的组一共出现了多少次”。
最自然的做法，是把每一种可能的组构成都看成一个类型，然后统计每种类型用了多少个。
定义
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
对每个类型 \(t=(t_b,t_w)\in\mathcal{T}\)，记 \(k_t\) 为恰好包含 \(t_b\) 个黑色物体和 \(t_w\) 个白色物体的组的个数。于是，一个合法方案恰好就是下面方程组的非负整数解：
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
这已经把“组的顺序无关”完整地表达出来了：一个方案由重数向量 \((k_t)_{t\in\mathcal{T}}\) 决定，而不是由某个有序的组列表决定。
每种类型 \(t=(t_b,t_w)\) 都可以使用 \(0,1,2,\dots\) 次，所以它对应的贡献是几何级数
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}.$$
对所有允许的类型相乘，得到
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
题目答案就是系数
$$\left[x^B y^W\right]F(x,y).$$
因此，Problem 181 本质上是一个二维拆分问题：把目标向量 \((B,W)\) 表示成若干个非零向量 \((t_b,t_w)\) 的无序多重集合之和。
给 \(\mathcal{T}\) 中的类型任意规定一个固定顺序。处理到这个顺序的某个前缀后，定义
$$\mathrm{dp}[b][w]=\text{只使用已经处理过的类型，恰好组成 }(b,w)\text{ 的方案数}.$$
初始时只有空多重集合可用，因此
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ 对其余所有状态成立。}$$
若当前处理的类型是 \((t_b,t_w)\)，那么任意已有状态 \((b,w)\) 都可以再加入 \(k\) 个这种类型，其中 \(k\ge 1\) 且新总数不能越界。于是转移为
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
从基态 \((b,w)\) 出发，允许的最大重复次数是
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
实现中的内层 \(k\) 循环，正是先计算出这个上界以后再执行的。
实现只维护一张二维表，并且对 \(b\) 与 \(w\) 都采用从大到小的扫描顺序。这一点非常关键。处理某个固定类型 \((t_b,t_w)\) 时，新写入的状态不能再次作为同一类型的基态，否则同一种重复次数选择会被重复统计。
逆序扫描正好阻止了这种重复使用。每个基态都会直接向加入当前类型 \(1,2,\dots,m_{\max}\) 份后能达到的状态贡献一次，而且只贡献一次。换句话说，显式的 \(k\) 循环已经完整枚举了当前类型的所有重数，因此表中始终统计的是“已处理类型的无序多重集合”，而不是“决策步骤的有序序列”。
小例子 \(B=3\)、\(W=1\) 一共有恰好七种合法分组。把它们写成组类型的多重集合，就是：
每一项都对应一组重数赋值 \((k_t)\)。动态规划之所以能得到同样的答案，是因为它对每个允许的 \((t_b,t_w)\) 类型只处理一次，然后统一决定该类型取多少份。更大的 Euler 实例与此完全同构，只是状态空间更大。
C++、Python 和 Java 实现都会枚举所有满足 \(0\le t_b\le B\)、\(0\le t_w\le W\) 的 \((t_b,t_w)\)，唯一排除的是 \((0,0)\)。其中一个实现先把这些类型存入列表，其余实现直接在双重循环里处理，但数学含义完全相同：每一种可能的组构成都被准确处理一次。
表的大小是 \((B+1)\times(W+1)\)，位置 \((b,w)\) 存放的是当前部分乘积中 \(x^b y^w\) 的系数。初值 \(\mathrm{dp}[0][0]=1\) 代表空分组方案。处理某个类型时，实现读取当前基态计数，计算最大可重复次数 \(m_{\max}\)，然后把同一个基态计数加到所有可达的 \((b+k t_b,\ w+k t_w)\) 上。
之所以不需要第二张表，是因为 \(b\) 和 \(w\) 的逆序遍历保证：当前类型的所有转移都只从“在处理当前类型之前就已经存在的状态”出发。这正是生成函数因子 \((1-x^{t_b}y^{t_w})^{-1}\) 的代码化形式。
这个递推对黑色和白色完全对称：交换两种颜色，只是把每个状态和每个类型的两个坐标互换。因此，不同实现即使把两种颜色放在数组的不同维度上，最终答案也不会改变。其中一个实现还会在很小的输入上额外校验递推，包括 \(3\) 个黑色、\(1\) 个白色的示例，并把动态规划结果与对重数的穷举搜索进行比较。
共有
$$T=(B+1)(W+1)-1$$
种组类型，以及 \((B+1)(W+1)\) 个 DP 状态。对固定的类型和固定的基态来说，最内层的重数循环最多执行 \(\max(B,W)\) 次，因此一个简单的最坏情况上界是
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
这个上界是故意取得比较宽松的；在实际运行中，较大的组类型往往只能重复很少次，所以当 \(B=60\)、\(W=40\) 时，实际耗时比这个最坏界要小得多。空间复杂度是 \(O(BW)\)，因为实现只保留一张原地更新的二维表，而不是为每一种类型再开一层。
Дано \(B\) черных и \(W\) белых объектов. Одна группа определяется только своей цветовой композицией \((b,w)\), где \(b,w \ge 0\) и \(b+w>0\). Полная группировка поэтому является мультимножеством таких композиций, у которого суммарно используется ровно \(B\) черных и \(W\) белых объектов. Перестановка групп не создает нового решения.
В задаче Project Euler нужен случай \(B=60\), \(W=40\), но вывод, на котором основаны реализации, работает для произвольных \(B\) и \(W\). Нужно считать не то, какой именно объект попал в какую группу, а сколько раз встречается каждая возможная цветовая структура группы.
Самая естественная модель состоит в том, чтобы считать каждый допустимый состав группы отдельным типом и затем подсчитывать кратности этих типов.
Положим
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
Для каждого типа \(t=(t_b,t_w)\in\mathcal{T}\) обозначим через \(k_t\) число групп, содержащих ровно \(t_b\) черных и \(t_w\) белых объектов. Тогда допустимая группировка эквивалентна неотрицательному целочисленному решению системы
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
Здесь уже полностью учтено условие, что порядок групп не важен: решение задается вектором кратностей \((k_t)_{t\in\mathcal{T}}\), а не упорядоченным списком групп.
Каждый тип \(t=(t_b,t_w)\) можно использовать \(0,1,2,\dots\) раз, поэтому он дает геометрический ряд
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}.$$
Перемножая такие множители по всем допустимым типам, получаем
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
Искомый ответ есть коэффициент
$$\left[x^B y^W\right]F(x,y).$$
Значит, Problem 181 превращается в двумерную задачу о разбиении: нужно представить вектор \((B,W)\) как сумму неупорядоченного мультимножества ненулевых векторов \((t_b,t_w)\).
Выберем любой фиксированный порядок типов в \(\mathcal{T}\). После обработки некоторого префикса этого порядка определим
$$\mathrm{dp}[b][w]=\text{число способов получить ровно }(b,w)\text{, используя только уже обработанные типы}.$$
В начале доступно только пустое мультимножество, поэтому
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\text{ для всех остальных состояний.}$$
Если текущий тип равен \((t_b,t_w)\), то из любого базового состояния \((b,w)\) можно добавить \(k\) копий этого типа, где \(k\ge 1\) и итоговые суммы не выходят за границы. Получаем переход
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
Максимально допустимая кратность из состояния \((b,w)\) равна
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
Именно эту величину реализации вычисляют перед внутренним циклом по \(k\).
Реализации используют одну общую двумерную таблицу и обходят \(b\) и \(w\) в обратном порядке. Это принципиально важно. Во время обработки фиксированного типа \((t_b,t_w)\) состояние, записанное только что, не должно снова использоваться как базовое состояние для того же типа, иначе один и тот же выбор кратности будет посчитан несколько раз.
Обратный порядок обхода ровно это и предотвращает. Каждое базовое состояние сразу добавляет вклад во все состояния, достижимые добавлением \(1,2,\dots,m_{\max}\) копий текущего типа, и делает это ровно один раз. Поэтому таблица продолжает считать неупорядоченные мультимножества обработанных типов, а не упорядоченные последовательности шагов.
Для малого случая \(B=3\), \(W=1\) существует ровно семь допустимых группировок. В виде мультимножеств типов групп они таковы:
Каждый пункт соответствует одной конфигурации кратностей \((k_t)\). Динамическая программа воспроизводит это число, потому что каждый допустимый тип \((t_b,t_w)\) обрабатывается ровно один раз, после чего выбирается, сколько копий этого типа использовать. Большой случай Euler устроен точно так же; увеличивается только размер пространства состояний.
Реализации на C++, Python и Java перебирают все пары \((t_b,t_w)\) с условиями \(0\le t_b\le B\) и \(0\le t_w\le W\), кроме \((0,0)\). Одна реализация сначала сохраняет эти пары в список, остальные проходят по вложенным циклам напрямую. С математической точки зрения это один и тот же шаг: каждая возможная цветовая структура группы обрабатывается ровно один раз.
Размер таблицы равен \((B+1)\times(W+1)\), а в ячейке \((b,w)\) хранится текущий коэффициент при \(x^b y^w\) в частичном произведении по уже обработанным типам. Начальное значение \(\mathrm{dp}[0][0]=1\) соответствует пустой группировке. Для каждого типа реализация считывает базовое количество способов, вычисляет максимальное число повторов \(m_{\max}\) и прибавляет это базовое значение ко всем достижимым состояниям \((b+k t_b,\ w+k t_w)\).
Вторая таблица не нужна, потому что обратный обход по \(b\) и \(w\) гарантирует: все переходы для текущего типа исходят только из состояний, которые существовали еще до начала обработки этого типа. Это и есть прямая программная реализация множителя \((1-x^{t_b}y^{t_w})^{-1}\).
Рекуррентное соотношение симметрично по черным и белым объектам: если поменять цвета местами, то просто меняются местами координаты каждого состояния и каждого типа. Поэтому метод работает независимо от того, какой цвет расположен по первой оси массива. Одна из реализаций также проверяет корректность на маленьких примерах, включая случай \(3\) черных и \(1\) белый, сравнивая DP с полным перебором по кратностям.
Существует
$$T=(B+1)(W+1)-1$$
типов групп и \((B+1)(W+1)\) состояний DP. Для фиксированного типа и фиксированного базового состояния внутренний цикл по кратности выполняется не более \(\max(B,W)\) раз, поэтому простая верхняя оценка имеет вид
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
Это заведомо грубая оценка; на практике крупные типы групп допускают лишь несколько повторов, поэтому реальное время работы для \(B=60\), \(W=40\) заметно меньше. Память составляет \(O(BW)\), поскольку реализации хранят одну обновляемую на месте двумерную таблицу, а не отдельный слой на каждый обработанный тип.
لدينا \(B\) عنصرًا أسود و\(W\) عنصرًا أبيض. كل مجموعة مفردة تُوصَف فقط بتركيبها اللوني \((b,w)\) حيث \(b,w \ge 0\) و\(b+w>0\). لذلك فإن التجميع الكامل هو متعدد مجموعات من هذه التركيبات بحيث يكون مجموع العناصر السوداء \(B\) ومجموع العناصر البيضاء \(W\). تبديل ترتيب المجموعات لا يعطي حلاً جديدًا.
في مسألة Project Euler الحالة المطلوبة هي \(B=60\) و\(W=40\)، لكن الاشتقاق الذي تعتمد عليه التطبيقات صالح لأي قيمتين عامتين \(B\) و\(W\). الفكرة الأساسية ليست تتبع كل عنصر بعينه، بل معرفة عدد المرات التي يظهر فيها كل نوع ممكن من المجموعات.
أفضل صياغة هنا هي اعتبار كل تركيب ممكن للمجموعة نوعًا مستقلاً، ثم عدّ عدد النسخ المأخوذة من كل نوع.
لنعرّف
$$\mathcal{T}=\{(t_b,t_w)\mid 0 \le t_b \le B,\ 0 \le t_w \le W,\ (t_b,t_w)\ne(0,0)\}.$$
ولكل نوع \(t=(t_b,t_w)\in\mathcal{T}\)، ليكن \(k_t\) هو عدد المجموعات التي تحتوي بالضبط على \(t_b\) عناصر سوداء و\(t_w\) عناصر بيضاء. عندئذٍ يكون أي تجميع صحيح مكافئًا تمامًا لحل صحيح غير سالب للنظام
$$\sum_{t\in\mathcal{T}} k_t\,t_b = B,\qquad \sum_{t\in\mathcal{T}} k_t\,t_w = W.$$
هذه الصياغة تدمج مباشرة شرط أن ترتيب المجموعات غير مهم: الحل هو متجه المضاعفات \((k_t)_{t\in\mathcal{T}}\)، وليس قائمة مرتبة من المجموعات.
كل نوع \(t=(t_b,t_w)\) يمكن استعماله \(0,1,2,\dots\) مرة، ولذلك يساهم بالمتسلسلة الهندسية
$$1+x^{t_b}y^{t_w}+x^{2t_b}y^{2t_w}+\cdots=\frac{1}{1-x^{t_b}y^{t_w}}.$$
وبضرب جميع الأنواع المسموح بها نحصل على
$$F(x,y)=\prod_{(t_b,t_w)\in\mathcal{T}}\frac{1}{1-x^{t_b}y^{t_w}}.$$
والجواب المطلوب هو المعامل
$$\left[x^B y^W\right]F(x,y).$$
إذن مسألة 181 تتحول إلى مسألة تقسيم ثنائية الأبعاد: تمثيل المتجه \((B,W)\) على أنه مجموع متعدد مجموعات غير مرتب من المتجهات غير الصفرية \((t_b,t_w)\).
نختار ترتيبًا ثابتًا كيفيًا للأنواع في \(\mathcal{T}\). بعد معالجة بادئة من هذا الترتيب، نعرّف
\(\mathrm{dp}[b][w]\) هو عدد الطرق للحصول على المجموع الدقيق \((b,w)\) باستعمال الأنواع التي تمت معالجتها فقط.
في البداية لا يوجد إلا متعدد المجموعات الفارغ، ولذلك
وفي البداية تكون
$$\mathrm{dp}[0][0]=1,\qquad \mathrm{dp}[b][w]=0\quad\text{otherwise.}$$
إذا كان النوع الحالي هو \((t_b,t_w)\)، فإن أي حالة أساس \((b,w)\) يمكن توسيعها بإضافة \(k\) نسخ من هذا النوع، حيث \(k\ge 1\) مع البقاء داخل الحدود. ومن ثم يكون الانتقال
$$\mathrm{dp}[b+k t_b][w+k t_w]\mathrel{+}= \mathrm{dp}[b][w].$$
وأكبر عدد مسموح من التكرارات انطلاقًا من الحالة \((b,w)\) هو
$$m_{\max}=\begin{cases} \left\lfloor\dfrac{W-w}{t_w}\right\rfloor, & t_b=0,\\[6pt] \left\lfloor\dfrac{B-b}{t_b}\right\rfloor, & t_w=0,\\[6pt] \min\!\left(\left\lfloor\dfrac{B-b}{t_b}\right\rfloor,\left\lfloor\dfrac{W-w}{t_w}\right\rfloor\right), & t_b,t_w>0. \end{cases}$$
وهذا هو بالضبط الحد الذي تحسبه التطبيقات قبل تشغيل الحلقة الداخلية على \(k\).
التطبيقات تحدّث جدولًا ثنائي الأبعاد واحدًا في مكانه، وتدور على \(b\) و\(w\) من القيم الأكبر إلى الأصغر. هذه النقطة أساسية جدًا. أثناء معالجة نوع ثابت \((t_b,t_w)\)، لا يجوز استعمال حالة كُتبت لتوّها كحالة أساس جديدة لنفس النوع، لأن ذلك سيؤدي إلى عدّ اختيار التكرار نفسه أكثر من مرة.
المسح التنازلي يمنع هذا تمامًا. فكل حالة أساس تضيف مساهمتها مباشرة إلى جميع الحالات التي يمكن الوصول إليها بإضافة \(1,2,\dots,m_{\max}\) نسخة من النوع الحالي، وتفعل ذلك مرة واحدة فقط. لذلك يبقى معنى الجدول هو عدّ متعددات المجموعات غير المرتبة للأنواع التي تمت معالجتها، لا عدّ السلاسل المرتبة من القرارات.
في الحالة الصغيرة \(B=3\) و\(W=1\) توجد بالضبط سبع طرق صحيحة للتجميع. وإذا كتبناها على شكل متعدد مجموعات من أنواع المجموعات، نحصل على:
كل سطر يقابل إسنادًا واحدًا للمضاعفات \((k_t)\). والبرمجة الديناميكية تعيد هذا العدد بدقة لأنها تعالج كل نوع مسموح \((t_b,t_w)\) مرة واحدة فقط، ثم تختار عدد النسخ المأخوذة من ذلك النوع. والحالة الكبيرة في Euler تعتمد الفكرة نفسها تمامًا، لكن على فضاء حالات أكبر.
تقوم تطبيقات C++ وPython وJava بالمرور على جميع الأزواج \((t_b,t_w)\) التي تحقق \(0\le t_b\le B\) و\(0\le t_w\le W\)، مع استبعاد \((0,0)\) فقط. أحد التطبيقات يبني قائمة بهذه الأزواج أولًا، بينما يعالجها التطبيقان الآخران مباشرة داخل الحلقات المتداخلة. رياضيًا لا يوجد فرق: كل تركيب لوني ممكن للمجموعة يُعالَج مرة واحدة لا أكثر.
حجم الجدول هو \((B+1)\times(W+1)\)، والخانة \((b,w)\) تمثل المعامل الحالي لـ \(x^b y^w\) في الجداء الجزئي للأنواع التي عولجت حتى تلك اللحظة. القيمة الابتدائية \(\mathrm{dp}[0][0]=1\) تمثل التجميع الفارغ. لكل نوع، يقرأ التنفيذ عدد الطرق الأساسي، ثم يحسب الحد الأقصى للتكرار \(m_{\max}\)، وبعد ذلك يضيف هذا العدد نفسه إلى كل حالة ممكنة من الشكل \((b+k t_b,\ w+k t_w)\).
ولا حاجة إلى جدول ثانٍ، لأن المسح العكسي على \(b\) و\(w\) يضمن أن انتقالات النوع الحالي تنطلق فقط من حالات كانت موجودة قبل بدء تحديث هذا النوع. وهذا هو التجسيد البرمجي المباشر للعامل \((1-x^{t_b}y^{t_w})^{-1}\) في الدالة المولدة.
العلاقة العودية متناظرة تمامًا بين اللونين الأسود والأبيض: تبديل اللونين لا يفعل سوى تبديل الإحداثيين في كل حالة وكل نوع. لذلك تعمل الطريقة نفسها مهما كان اللون الذي يُوضَع على المحور الأول في المصفوفة. كما أن أحد التطبيقات يختبر صحة العودية على حالات صغيرة جدًا، ومنها المثال \(3\) سود و\(1\) أبيض، بمقارنة نتيجة البرمجة الديناميكية مع بحث شامل على المضاعفات.
يوجد
$$T=(B+1)(W+1)-1$$
نوعًا من المجموعات، و\((B+1)(W+1)\) حالة في جدول البرمجة الديناميكية. بالنسبة إلى نوع ثابت وحالة أساس ثابتة، فإن الحلقة الداخلية على عدد التكرارات تعمل في أسوأ الأحوال حتى \(\max(B,W)\) مرة، ولذلك نحصل على حد علوي بسيط هو
$$O\!\bigl(T\cdot B\cdot W\cdot \max(B,W)\bigr)=O\!\bigl(B^2W^2\max(B,W)\bigr).$$
وهذا الحد متحفظ عمدًا؛ ففي التطبيق العملي، الأنواع الكبيرة لا تسمح إلا بعدد قليل من التكرارات، لذلك يكون الزمن الفعلي عند \(B=60\) و\(W=40\) أصغر بكثير مما توحي به صيغة أسوأ حالة. أما الذاكرة فهي \(O(BW)\)، لأن التنفيذ يحتفظ بجدول ثنائي الأبعاد واحد يُحدَّث في مكانه بدلًا من تخزين طبقة منفصلة لكل نوع.