Detailed mathematical approach

Problem Summary

The configuration is a chain of \(a+b\) colored units. Exactly \(a\) of them are type A and \(b\) are type B. Adjacent units share an ordered boundary pair of vertices, and every edge in the unit graph imposes the usual coloring rule that its endpoints must have different colors. For Project Euler 194 the parameters are \(a=25\), \(b=75\), and \(c=1984\), and the final answer is required modulo \(10^8\).

A direct count of whole-chain colorings would mix together 100 units and an enormous number of color assignments. The implementations avoid that by isolating one local counting problem: how many valid extensions does a single unit have when the two colors on its incoming boundary are already fixed and distinct?

Mathematical Approach

Fix an ordered incoming boundary pair \((x,y)\) with \(x \ne y\). A unit contributes five unfixed vertices: two outgoing boundary vertices and three internal vertices. Because the constraints only say that adjacent vertices must have different colors, the actual names of \(x\) and \(y\) never matter; only the fact that they are distinct matters.

The Boundary-Pair Invariant

Both unit types start from a distinct ordered pair \((x,y)\) and end at another distinct ordered pair. The outgoing top boundary color must differ from the incoming top one, and the outgoing bottom boundary color must differ from the outgoing top one. The rest of the unit only sees the incoming pair through adjacency constraints.

This is the invariant that makes the chain multiplicative. When one unit is glued to the next, its right boundary becomes the next unit's left boundary, and that shared boundary is again just a distinct ordered pair. So every unit can be counted independently once the local extension count is known.

Local Extension Counts for Type A and Type B

Let \(A(c)\) be the number of valid colorings of one type-A unit when the incoming boundary colors are fixed and distinct, and let \(B(c)\) be the analogous number for one type-B unit.

The two unit graphs differ in exactly one place. In type A, the outgoing lower boundary vertex is also adjacent to the incoming lower boundary vertex, so it is forbidden to reuse that color. Type B omits that edge, which is why \(B(c)\) is larger.

Since a unit has five unfixed vertices, these local counts are degree-5 coloring polynomials in \(c\). The implementations determine them exactly by brute force for \(c=2,3,4,5,6,7\):

$\bigl(A(2),A(3),A(4),A(5),A(6),A(7)\bigr)=(0,4,62,372,1396,3980),$

$\bigl(B(2),B(3),B(4),B(5),B(6),B(7)\bigr)=(0,6,88,486,1728,4750).$

Six exact values are enough to recover a degree-5 polynomial uniquely, so Newton forward interpolation gives the closed formulas used implicitly by the implementations:

$A(c)=c^5-9c^4+34c^3-69c^2+77c-38,$

$B(c)=c^5-8c^4+27c^3-50c^2+52c-24=(c-2)^3(c^2-2c+3).$

A Worked Example: The Case \(c=3\)

Take three colors \(\{x,y,z\}\) and fix the incoming boundary as \((x,y)\). A complete enumeration of one unit gives

$A(3)=4,\qquad B(3)=6.$

The difference is already visible at this smallest nontrivial palette size. Type B has two extra extensions because its outgoing lower boundary is allowed to reuse the color \(y\); type A forbids exactly those colorings through its extra lower edge. This tiny example captures the only structural distinction between the two building blocks.

Assembling the Whole Configuration

Once the local counts are known, the full answer factorizes. First choose which of the \(a+b\) positions are occupied by type-A units. That contributes

$\binom{a+b}{a}.$

Then choose the ordered color pair on the very first boundary. Because the two colors must be distinct, this contributes

$c(c-1).$

Every type-A unit contributes a factor \(A(c)\), every type-B unit contributes a factor \(B(c)\), and the location of the unit does not matter because every interface is just a distinct ordered pair and the color names are symmetric. Therefore

$\boxed{N(a,b,c)=\binom{a+b}{a}\,c(c-1)\,A(c)^a B(c)^b.}$

For the Euler instance \((a,b,c)=(25,75,1984)\), that exact integer is finally reduced modulo \(10^8\).

How the Code Works

Exact Enumeration of One Unit

The C++, Python, and Java implementations begin by fixing two distinct incoming boundary colors and brute-forcing the five remaining vertices for \(c=2,\dots,7\). That produces the six exact values of \(A(c)\) and \(B(c)\) listed above. The C++ implementation also checks the interpolated values against fresh brute-force counts for a few additional small palette sizes.

Forward-Difference Evaluation at the Target \(c\)

Instead of hard-coding symbolic algebra, the implementations evaluate the degree-5 polynomials through Newton forward differences. If \(n=c-2\), then

$A(c)=\sum_{k=0}^{5}\Delta^kA(2)\binom{n}{k},\qquad B(c)=\sum_{k=0}^{5}\Delta^kB(2)\binom{n}{k}.$

For these two unit counts, the first entries of the forward-difference tables are

$A:\ (0,4,54,198,264,120),\qquad B:\ (0,6,76,240,288,120).$

Because the underlying functions really are degree-5 polynomials, this interpolation is exact rather than approximate.

Final Modular Product

After obtaining \(A(c)\) and \(B(c)\), the implementations compute \(\binom{a+b}{a}\), multiply by \(c(c-1)\), and raise the two local counts to the powers \(a\) and \(b\) with fast modular exponentiation. The final stage runs modulo \(10^8\), while the small checkpoint calculations may use exact integer arithmetic first and reduce only at the end.

Complexity Analysis

The local brute-force phase is constant-sized: it evaluates only six palette sizes, and each unit has only five unfixed vertices. Building the forward-difference table and evaluating the resulting polynomial are therefore \(O(1)\).

For parameterized inputs, forming \(\binom{a+b}{a}\) by multiplicative accumulation costs \(O(\min(a,b))\) arithmetic steps, and the two modular powers cost \(O(\log a+\log b)\). Extra memory usage is \(O(1)\) beyond a few fixed tables of sample values and differences.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=194
2. Graph coloring: Wikipedia - Graph coloring
3. Chromatic polynomial: Wikipedia - Chromatic polynomial
4. Newton polynomial: Wikipedia - Newton polynomial
5. Finite difference: Wikipedia - Finite difference
6. Binomial coefficient: Wikipedia - Binomial coefficient
7. Modular exponentiation: Wikipedia - Modular exponentiation