Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

The cleanest formulation is to treat every possible group composition as a type and then count how many copies of each type are used.

Encoding a grouping by multiplicities

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.

A bivariate generating function

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)\).

Turning coefficient extraction into dynamic programming

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\).

Why the in-place reverse sweep is correct

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.

Worked example: \(3\) black and \(1\) white

The small instance \(B=3\), \(W=1\) has exactly seven valid groupings. Written as multisets of group types, they are:

1. \(\{(3,1)\}\)
2. \(\{(3,0),(0,1)\}\)
3. \(\{(2,1),(1,0)\}\)
4. \(\{(2,0),(1,1)\}\)
5. \(\{(2,0),(1,0),(0,1)\}\)
6. \(\{(1,1),(1,0),(1,0)\}\)
7. \(\{(1,0),(1,0),(1,0),(0,1)\}\)

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.

How the Code Works

Enumerating every admissible group type

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.

Maintaining a single coefficient table

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}\).

Symmetry and small-instance verification

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.

Complexity Analysis

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.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=181
2. Generating function: Wikipedia - Generating function
3. Formal power series: Wikipedia - Formal power series
4. Partition in number theory: Wikipedia - Partition (number theory)
5. Dynamic programming: Wikipedia - Dynamic programming
6. Unbounded knapsack: Wikipedia - Unbounded knapsack problem
7. Multiset: Wikipedia - Multiset