Peerless trees

[Victor Miller]

On the Euler Project they have a problem concerning what they call "peerless trees". In their definition a peerless tree is a finite tree in which two vertices can be adjacent only if they have distinct degrees. They then ask for the number (up to isomorphism) of peerless trees with n vertices. Besides brute force computation, it would be an interesting problem to come up with a formula for the generating function and/or asymptotics. Does anyone want to bite?

[Allan Wechsler]

These are ordinary, unlabeled, unrooted trees?

If so, unreliable hand-counting gives me 1,0,1,1,2,3,6,9 to start with. It's a little bit spooky that all three matches to this on OEIS relate to counting trees.

On Wed, Apr 30, 2025 at 11:55 AM Victor Miller <victor...@gmail.com> wrote:

On the Euler Project they have a problem concerning what they call "peerless trees". In their definition a peerless tree is a finite tree in which two vertices can be adjacent only if they have distinct degrees. They then ask for the number (up to isomorphism) of peerless trees with n vertices. Besides brute force computation, it would be an interesting problem to come up with a formula for the generating function and/or asymptotics. Does anyone want to bite?

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAEe1e0xy5zQiOUQaCp3ERQTLe_JgR7S1bQ4y1nXM6aqCc4NN%2BA%40mail.gmail.com.

[Victor Miller]

Yes, that's what I take it to mean. In a related sequence, since a connected undirected tree with n > 1 vertices has n-1 edges, the sum of the degrees of a n-node tree is 2n-2. So one can look at partitions of 2n-2 into n parts and ask how many of them are feasible: i.e. there exists a tree with those degrees. Clearly it is necessary that there be at least two parts that are 1, but that's not sufficient. So the sequence which gives the number of feasible partitions would be an interesting one for oeis.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGFaEL79BMV1d8bJTHYh2Qs-F86GwNQTCDc4bUHMT98xkA%40mail.gmail.com.

[Neil Sloane]

Changing one letter gives a more arboreal name: Pearless Trees!

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAEe1e0wBYqX6gZhZPC_fwck4bf-aHCB1wV%3Dch7LCHpjetqbjiw%40mail.gmail.com.

[Victor Miller]

No partridges involved ? :-).

It looks like, not surprisingly, someone considered my second problem. I just found it, so can't vouch for it: https://math.stackexchange.com/questions/1932853/degree-sequence-of-trees

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAOnSgThpvjyquK2qmYuq_go9L%3D3t%2BVJcAf2hfZdPwW7QL%2B3NQ%40mail.gmail.com.

[Victor Miller]

And I see that this is already touched on in A344122

[M F Hasler]

On Wed, Apr 30, 2025 at 2:28 PM Neil Sloane <njas...@gmail.com> wrote:

Changing one letter gives a more arboreal name: Pearless Trees!

Theorem (Hasler, 2025): almost all trees are pearless.

 

Best regards

Maximilian

[Brendan]

It is certainly not true that almost all trees are pearless.  Allen Schwenk proved long ago

that for any rooted tree R almost all trees contain R as a limb. Take any R that isn't

pearless.  So in fact almost no trees are pearless.  For 30 vertices, about one in

every 69 trees is pearless.

The following is by testing all trees, which is an atrocious method but all I have time for.

It took about 12 minutes on one cpu and I'll let it run for a few hours more.

 3: 1
 4: 1
 5: 2
 6: 3
 7: 6
 8: 9
 9: 19
10: 33
11: 67
12: 130
13: 270
14: 547
15: 1165
16: 2456
17: 5314
18: 11521
19: 25357
20: 56022
21: 125067
22: 280471
23: 633490
24: 1437340
25: 3278912
26: 7510503
27: 17277697
28: 39890262
29: 92427559
30: 214835923

Brendan.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFqvfd-YnfiXfS_0pYWRjvxux439cbuFS1jkd7AFj2VVrH7rjA%40mail.gmail.com.

[Pierre Abbat]

On Wednesday, April 30, 2025 3:23:46 PM EDT M F Hasler wrote:
> On Wed, Apr 30, 2025 at 2:28 PM Neil Sloane <njas...@gmail.com> wrote:
> > Changing one letter gives a more arboreal name: Pearless Trees!
>
> Theorem (Hasler, 2025): almost all trees are pearless.

Can you prove this with Maple?

I was just looking at a picture I took of a maple tree that's near a Bradford
pear tree at church.

Pierre

--
When a barnacle settles down, its brain disintegrates.
Já não percebe nada, já não percebe nada.

[Brendan]

It continues

31: 500879602
32: 1171013350
33: 2744946654

and I'll get one more overnight.

A way to go much further is this:  If the tree has a unique centroid (not centre!) 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.  I won't be doing this (too many other projects) but getting up past 60 vertices should be possible.

Of course a theoretical enumeration will blow any computation out of the water.

Brendan.

[Neil Sloane]

II will create an OEIS entry for this - it will be A383447

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJeNNUhD5OhQ8P9SD8%3D3PH1WXf5kmXGXtTHc%2B3bAGOBx57K2%2Bg%40mail.gmail.com.

[M F Hasler]

On Thu, May 1, 2025, 00:12 Brendan <brend...@gmail.com> wrote:

It is certainly not true that almost all trees are pearless. 

I think you chose peerless and pearless.

I do have a proof that the number of trees that grow pears is finite.

It uses a well established conservation law.

-Maximilian

Allen Schwenk proved long ago

that for any rooted tree R almost all trees contain R as a limb. Take any R that isn't

pearless. 

Peerless !

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJeNNUjW8PUuNtnBPqjDvtqhepbwB%2BK6k9JMReb86KLPQQjDYg%40mail.gmail.com.

[M F Hasler]

Sorry, my phone introduced an error I have to correct, but I will not flood this group with further disgressions about fruit.

Maybe just to say that a pear and a peer are so much different that one should really not consider both in the same context.

---------- corrected message ---------

On Thu, May 1, 2025, 00:12 Brendan <brend...@gmail.com> wrote:

It is certainly not true that almost all trees are pearless. 

I think you confuse peerless and pearless.