Detailed mathematical approach

Problem Summary

The solution counts admissible unlabelled coloured trees on \(n\) vertices and asks for \(g(10000)\) modulo

$10^9+7.$

The colour rules encoded by the implementations are:

red vertices may have degree at most \(4\), blue vertices degree at most \(3\), yellow vertices degree at most \(3\), and an edge joining two yellow vertices is forbidden. The first checkpoints are

$g(2)=5,\qquad g(3)=15,\qquad g(4)=57,\qquad g(10)=710249.$

A direct isomorphism test over all coloured trees of size \(10000\) is hopeless, so the program instead uses ordinary generating functions, cycle-index formulas for multisets, and the dissymmetry theorem for trees.

Mathematical Approach

The counting is done in three stages: first count planted trees, then count vertex-rooted trees, and finally recover the unrooted objects.

Step 1: Planted Trees and Colour Constraints

Let \(R(x)\), \(B(x)\), and \(Y(x)\) be the ordinary generating functions for planted trees whose distinguished root vertex is red, blue, or yellow. A planted tree has one distinguished parent edge above the root, so one incidence of the root is already used.

Define the aggregate series

$A(x)=R(x)+B(x)+Y(x),\qquad N(x)=R(x)+B(x).$

Here \(A(x)\) is the class of all planted trees, while \(N(x)\) is the class of planted trees whose root is not yellow. The second series is needed because a yellow root is not allowed to touch a yellow neighbour.

Since the parent edge already occupies one slot, the root of a planted tree can accept only

red: \(0,1,2,3\) children, blue: \(0,1,2\) children, yellow: \(0,1,2\) non-yellow children.

Step 2: Multisets via Cycle Indices

When the root receives an unordered collection of child subtrees, we must count multisets rather than ordered tuples. For ordinary generating functions, the cycle-index formulas for the symmetric groups give

$\Phi_1(F)=F(x),$

$\Phi_2(F)=\frac{F(x)^2+F(x^2)}{2},$

$\Phi_3(F)=\frac{F(x)^3+3F(x)F(x^2)+2F(x^3)}{6},$

$\Phi_4(F)=\frac{F(x)^4+6F(x)^2F(x^2)+3F(x^2)^2+8F(x)F(x^3)+6F(x^4)}{24}.$

These are exactly the multiset operators that appear in the program.

Therefore the planted-tree equations are

$R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$

$B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)\right),$

$Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)\right).$

The factor \(x\) accounts for the root itself, and the constant \(1\) means that the root may have no children.

Step 3: Vertex-Rooted Trees

To count trees rooted at a vertex rather than at a parent edge, the root regains its full degree budget. Let \(V_R(x)\), \(V_B(x)\), and \(V_Y(x)\) denote the generating functions for vertex-rooted admissible trees. Then

$V_R(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)+\Phi_4(A)\right),$

$V_B(x)=x\left(1+\Phi_1(A)+\Phi_2(A)+\Phi_3(A)\right),$

$V_Y(x)=x\left(1+\Phi_1(N)+\Phi_2(N)+\Phi_3(N)\right).$

Adding the three root colours gives the full vertex-rooted series

$V(x)=V_R(x)+V_B(x)+V_Y(x).$

This matches the second stage of the implementations.

Step 4: Edge-Rooted Trees and the Yellow-Yellow Exclusion

If we root a tree at a directed edge, the edge splits the tree into an ordered pair of planted trees. Without the colour restriction this would give \(A(x)^2\). The only forbidden case is when both exposed roots are yellow, so the directed edge-rooted series is

$E_{\mathrm{dir}}(x)=A(x)^2-Y(x)^2.$

For an undirected edge root, the two sides are an unordered pair. Burnside's lemma gives

$E_{\mathrm{und}}(x)=\frac{E_{\mathrm{dir}}(x)+A(x^2)-Y(x^2)}{2}.$

The extra terms \(A(x^2)\) and \(Y(x^2)\) represent the fixed points of swapping the two sides: both halves must be identical, and the yellow-yellow case is still excluded.

Step 5: Dissymmetry Theorem

For trees, the classical dissymmetry theorem says that

$\text{unrooted}=\text{vertex-rooted}+\text{edge-rooted}-\text{directed-edge-rooted}.$

Translated into generating functions,

$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x).$

The desired sequence is therefore

$g(n)=\left[x^n\right]G(x).$

This identity is exactly what the final correction stage computes.

Worked Example: Why \(g(3)=15\)

For \(n=3\), the only tree shape is a path of length \(2\). Up to isomorphism, the middle vertex determines the adjacency pattern.

If the middle vertex is red, the two leaves form an unordered multiset chosen from \(\{R,B,Y\}\). There are

$\binom{3+2-1}{2}=6$

such multisets.

If the middle vertex is blue, the same count applies, again giving \(6\).

If the middle vertex is yellow, each neighbour must be non-yellow, so the two leaves form an unordered multiset from \(\{R,B\}\). That gives

$\binom{2+2-1}{2}=3.$

Hence

$g(3)=6+6+3=15,$

which agrees with the validation values used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. First they build coefficient tables for the planted series up to size \(10000\). When constructing size \(n\), they read multiset contributions at size \(n-1\) because the root contributes one vertex.

During that first pass, the implementation incrementally maintains square convolutions of the aggregated planted series. Those precomputed quadratic terms are then reused to obtain the degree-\(2\) and degree-\(3\) multiset contributions efficiently.

In the second pass, the implementation constructs shifted copies corresponding to \(F(x^2)\), \(F(x^3)\), and \(F(x^4)\), together with the cubic and quartic convolution terms required by the cycle-index formulas. That produces the full vertex-rooted counts.

Finally it forms the directed edge-rooted and undirected edge-rooted series, applies

$G(x)=V(x)+E_{\mathrm{und}}(x)-E_{\mathrm{dir}}(x),$

and extracts the coefficient of \(x^{10000}\) modulo \(10^9+7\). The C++ implementation parallelizes some of the largest convolutions, but the mathematical formula is identical in all three languages.

Complexity Analysis

Let \(N=10000\). The dominant work comes from quadratic convolutions and from the incremental updates that build the square series. Both stages are \(O(N^2)\) time overall. Only a fixed number of coefficient arrays of length \(N+1\) are stored, so the memory usage is \(O(N)\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=677
2. Combinatorial species: Wikipedia - Combinatorial species
3. Cycle index: Wikipedia - Cycle index
4. Burnside's lemma: Wikipedia - Burnside's lemma
5. Dissymmetry theorem: Wikipedia - Dissymmetry theorem