A383447 Number of "peerless" trees on n nodes.

1, 0, 1, 1, 2, 3, 6, 9, 19, 33, 67, 130, 270, 547, 1165, 2456, 5314, 11521, 25357, 56022, 125067, 280471, 633490, 1437340, 3278912, 7510503, 17277697, 39890262, 92427559, 214835923, 500879602, 1171013350, 2744946654, 6450077870

Offset: 1

Author

N. J. A. Sloane, May 01 2025, based on postings to the SeqFan Mailing List in April and May 2025 by Victor S. Miller, Allan C. Wechsler, Brendan McKay, and others

Keywords

• nonn
• more

Comments

A "peerless" tree is an unlabeled, unrooted tree (as in A000055) with the property that if two nodes are joined by an edge then these nodes have different degrees.

Victor S. Miller reports that this sequence was first proposed on Project Euler.

Comment from Brendan McKay, May 01 2025 (Start)

The enumeration could be extended by the following argument.

If the tree has a unique centroid (not center!) then removing the centroid gives rooted subtrees of size less than n/2. If there are two centroids, they are adjacent and removing that edge gives two rooted subtrees with exactly n/2 vertices.

Start by making all rooted trees up to n/2 vertices which have no adjacent vertices of the same degree, not counting adjacencies of the root. Then classify them according to which degrees the root can be increased to without violating this condition for edges adjacent to the root.

With this information the counts for n vertices can be reconstructed. In this way getting up past 60 vertices should be possible. (End)

This sequence forms the left-most column of A383448.

Links

• Victor Miller and others, Peerless trees, Seqfan, 2025.
• Project Euler, Problem 936: Peerless Trees.

Crossrefs

Cf. A000055, A383448.

Extensions

a(1)-a(8) were computed by Allan C. Wechsler, Apr 30 2025, and a(9)-a(34) by Brendan McKay, May 02 2025.