Detailed mathematical approach

Problem Summary

Let \(U(n)\) denote the number of unlabeled unrooted trees with \(n\) vertices such that every edge joins vertices of different degrees. These are the peerless trees. The required answer is

$\sum_{n=3}^{50} U(n).$

The first values produced by the recurrence are \(U(3)=1\), \(U(4)=1\), \(U(5)=2\), and \(U(7)=6\), and one useful checkpoint is

$\sum_{n=3}^{10} U(n)=74.$

The difficulty is that these are free, unlabeled trees, so the children of a vertex form an unordered collection. The solution therefore counts isomorphism types by multisets of rooted subtrees instead of trying to generate adjacency structures directly.

Mathematical Approach

The implementations first count rooted versions of the objects and only at the end recover the free trees. The key invariant is local: if an edge connects a vertex of degree \(d\), then the subtree attached across that edge must have root degree different from \(d\).

Planted Trees and the Boundary Degree

Let \(P_d(n)\) be the number of planted peerless trees with \(n\) vertices whose root has degree \(d\). “Planted” means that the root is viewed as having a distinguished parent edge above it. That reserved edge already contributes 1 to the root degree, so inside the subtree the root has exactly \(d-1\) children.

Also define the total number of planted trees of size \(n\) by

$T(n)=\sum_{e\ge 1} P_e(n).$

If the parent vertex has degree \(d\), then among planted trees of size \(s\) only those whose root degree is not \(d\) may be attached. Hence the number of admissible child types of size \(s\) is

$A_d(s)=T(s)-P_d(s).$

This is the whole degree constraint at the attachment point: every internal edge inside the child subtree was already peerless before the attachment, so only the new parent-child edge has to be checked.

Unordered Children Lead to a Multiset Recurrence

Fix \(d\) and \(n\). To build an object counted by \(P_d(n)\), choose an unordered multiset of \(d-1\) admissible child trees whose total size is \(n-1\). If \(q_s\) children have size \(s\), then the constraints are

$\sum_{s\ge 1} q_s=d-1,\qquad \sum_{s\ge 1} s q_s=n-1.$

For a fixed size \(s\), there are \(A_d(s)\) available isomorphism types, and choosing \(q_s\) children from those types with repetition allowed gives the stars-and-bars factor

$\binom{A_d(s)+q_s-1}{q_s}.$

Therefore

$P_d(n)=\sum_{\substack{q_1,q_2,\dots\ge 0\\ \sum q_s=d-1\\ \sum s q_s=n-1}} \prod_{s\ge 1}\binom{A_d(s)+q_s-1}{q_s}.$

An equivalent generating-function form is

$P_d(n)=[x^{n-1}y^{d-1}] \prod_{s\ge 1}(1-yx^s)^{-A_d(s)}.$

The implementations do not expand that product symbolically; they extract the coefficient directly by dynamic programming over the pair “number of chosen children” and “total size used”.

Vertex-Rooted Trees Reuse the Same Counter

Now root the tree at an actual vertex instead of a planted edge. If the root degree is \(d\), then the root has \(d\) children, not \(d-1\). Once the admissible counts \(A_d(s)\) are known, the same multiset mechanism applies:

$V(n)=\sum_{d\ge 1}[x^{n-1}y^d]\prod_{s\ge 1}(1-yx^s)^{-A_d(s)},$

where \(V(n)\) counts peerless trees on \(n\) vertices with a distinguished root vertex.

Directed-Edge Roots and a Clean Convolution

Next root the tree at an oriented edge. Removing that directed edge splits the tree into an ordered pair of planted trees of sizes \(\ell\) and \(n-\ell\). If we temporarily ignore the degree condition on the marked edge, this gives

$\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell).$

When the two halves are glued back together, their roots become adjacent, so equal root degrees are forbidden. The bad pairs are exactly

$\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$

Thus the number of directed-edge-rooted peerless trees is

$D(n)=\sum_{\ell=1}^{n-1} T(\ell)\,T(n-\ell)-\sum_{d\ge 1}\sum_{\ell=1}^{n-1} P_d(\ell)\,P_d(n-\ell).$

Dissymmetry Recovers the Free Trees

Let \(E(n)\) be the number of peerless trees rooted at an undirected edge. For trees, the standard dissymmetry identity gives

$U(n)=V(n)+E(n)-D(n).$

In a peerless tree the endpoints of a marked edge always have different degrees, so the two orientations of that edge are genuinely distinct. Therefore every edge-rooted object corresponds to exactly two directed-edge-rooted objects, which means

$D(n)=2E(n).$

Substituting into the dissymmetry identity yields the formula used by the implementations:

$\boxed{U(n)=V(n)-\frac{D(n)}{2}.}$

Worked Example: Why \(U(5)=2\)

The recurrence gives \(V(5)=6\) and \(D(5)=8\), so

$U(5)=6-\frac{8}{2}=2.$

Those two trees are the 4-star and the unique tree with degree sequence \(3,2,1,1,1\). The 5-vertex path is excluded because its middle edge joins two degree-2 vertices. This small case shows why the method counts rooted versions first and then corrects the overcount caused by marked edges.

How the Code Works

Bottom-Up Construction of the Planted Table

The C++, Python, and Java implementations fill the planted counts in increasing order of \(n\). When size \(n\) is processed, every value \(P_d(s)\) and \(T(s)\) with \(s<n\) is already known, so the admissible counts \(A_d(s)=T(s)-P_d(s)\) are available immediately.

Coefficient Extraction by Dynamic Programming

For each requested root degree, the implementation runs a two-dimensional DP whose state records how many children have been chosen and what total subtree size they contribute. Processing the child sizes one by one reproduces the product of binomial factors \(\binom{A_d(s)+q_s-1}{q_s}\) without enumerating any trees explicitly.

Rooted Counts, Edge Counts, and the Final Sum

After the planted table is complete, the same DP is reused for the vertex-rooted counts \(V(n)\). The directed-edge counts \(D(n)\) are then computed from the convolution formula above, followed by the subtraction of same-degree pairs. Finally the implementation applies \(U(n)=V(n)-D(n)/2\) for each \(n\) and adds \(U(3)+U(4)+\cdots+U(50)\). All arithmetic is exact integer arithmetic.

Complexity Analysis

Let \(N=50\). The stored tables \(P_d(n)\), \(T(n)\), \(V(n)\), and \(U(n)\) require \(O(N^2)\) memory overall, and each individual multiset DP uses another \(O(N^2)\) working table.

The dominant cost is the repeated coefficient-extraction DP for the planted and vertex-rooted states. A safe coarse upper bound for the full program is \(O(N^6)\) time; the directed-edge correction is only \(O(N^3)\) and is smaller. Because \(N\) is just 50 and many impossible states are skipped immediately, the exact computation is entirely practical.

Footnotes and References

1. Problem page: Project Euler 936 - Peerless Trees
2. Trees in graph theory: Wikipedia - Tree (graph theory)
3. Rooted trees: Wikipedia - Rooted tree
4. Multisets and repeated choices: Wikipedia - Multiset and Wikipedia - Stars and bars
5. Species and tree dissymmetry: Wikipedia - Combinatorial species