A graph-theoretic sequence not yet in the OEIS

[Brett Schreiber]

Hello sequence fans,

Let a “rectree” be an unrooted, unlabeled tree with at least two vertices, where each vertex may itself contain a rectree.

Let the size of a rectree be the count of its vertices that do not contain rectrees, plus the sum of the sizes of each of its inner rectrees. (If we allowed rectrees of one vertex, it would complicate this definition of size.)

Here is an image of all rectrees of size 2 through 4.

There are 22 rectrees of size 5: the three unlabeled trees of size 5, plus a nice recursive procedure of adding the rectree of size 2 into each empty vertex of each rectree of size 4, 3 into 3, and 4 into 2, then removing duplicates using the natural definition of isomorphism.

Writing a program to do this was complicated (especially the isomorphism part) so I asked ChatGPT for one, which output the following sequence:

1, 2, 7, 22, 82, 308, 1231, 5011, 20997

This matches nothing in the OEIS, but since I don’t know if ChatGPT’s program is correct, I’m not ready to submit it. I got a much faster program from Google Gemini that generates the next term in the sequence without enumerating the rectrees using the Euler transform but it is over my head. I'm happy to share the Python code from either program.

I stumbled upon this idea of rectrees while researching 3-chromatic graphs. Happy to explain how they relate.

If you restrict yourself to trees of only two vertices, you get the half Catalan numbers  A000992. I don't know any other related sequences. I'm worried this is a needless restriction (or generalization) of a more useful object.

What do you all think?

Best,

Brett Schreiber

[Allan Wechsler]

This concepts shuns the concept of singleton nodes, both in the structural definition and in the definition of "size"; doubtless the motivating context explains this choice. But it makes me wonder whether OEIS already contains a census sequence for a conceptually simpler version: singletons are allowed, and the size is the aggregate number of nodes at all levels. (Rapid mental counting suggests that this sequence begins 1, 2, 4, 10, but this incipit is too common to find the sequence, if it's there.)

All that having been said, I think this combinatorial concept would definitely be worth including, assuming we had reliable data.

-- Allan

--
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/8d512a7b-7483-4dbf-ba1f-cb210c3157dfn%40googlegroups.com.

[Sean A. Irvine]

Hi,

To back up what Allan said, sequences based on counting combinatorial objects like this are always welcome additions to the OEIS.

Sean.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADy-sGFkH1BNeBVQGe-Zg36BGM2KPCwJ6S_W%3DZwpTUFuNg8DXw%40mail.gmail.com.

[Brendan]

This is a nice idea that I don't think I have seen before.  Like you, I don't think I would trust ChatGPT much on this as there are subtleties that it could easily get wrong. I'm thinking about how to implement it without too much work.

Brendan.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAL0FET%3DjkFG_F4m5k4F0BaZ__Yr8zEGSXKWCtuWfAVa1_k9yzw%40mail.gmail.com.

[Brendan]

My stupid generation program (held together with duct tape and bits of string) agrees with 1, 2, 7, 22, 82, 308, 1231, 5011, 20997.

Then it continues 89347, 386340.  I'll run one more.  A properly implemented generator could probably get into the 20s but

for this type of problem there is probably a theoretical approach that has no effective limit.

Brendan.

[Brett Schreiber]

Here is the program from Google Gemini that avoids generating the rectrees directly: https://github.com/schreiberbrett/rectrees/blob/main/rectreedynamicprogram.py

It agrees with all the terms here and runs in miliseconds. But it is not a program I understand

[Brendan]

So I asked Claude to derive a recurrence and it came up with something that looks correct (see next message).

Then asked it to write a Maple program for the recurrence.  If I was writing it myself I'd use the memoising feature of

Maple (option remember) rather than the tables used here.  But anyway here it is:

rectree:=proc(N::posint) local t,R,s,E,Bn,conv,n,k,d,i,j; 
   description "Number of rectrees of orders 2..N";
   t := table(); R := table(); s := table(); E := table();
   t[1] := 1; R[1] := 0; E[0] := 1;

   for n from 2 to N do
      s[n - 1] := add(t[(n - 1)/d]/d,d in numtheory:-divisors(n - 1));
      E[n - 1] := add(k*s[k]*E[n - 1 - k],k=1..n - 1)/(n - 1);
      conv := add(t[i]*t[n - i],i=1..n - 1);
      Bn := 1/2*conv - 1/2*if(n mod 2=0,t[1/2*n],0);
      R[n] := E[n - 1]+add(R[j]*E[n - j],j=2..n - 1) - Bn;
      t[n] := 2*R[n]+Bn;

   end do;
   seq(R[n],n=2..N);
end proc;

Executing rectree(30) gives
1, 2, 7, 22, 82, 308, 1231, 5011, 20997, 89347, 386340, 1689978, 7470286, 33304905, 149607999, 676428395, 3075991416, 14058997331, 64550018544, 297583759980, 1376963768074, 6392761588344, 29770046144891, 139022083485481, 650883577706649, 3054579449588136, 14366508407726890, 67707089846880739, 319697143115122734

Brendan.

[Brendan]

Here's the theory that Claude provided, with some tweaking by me to make it readable on this mail.
Does anyone get the feeling that thinking is gradually becoming optional?

Brendan.

Formalizing the order

A rectree has an "outer" tree (unrooted, unlabeled, with ≥ 2 vertices) where each vertex is either simple (contributing weight 1) or loaded with a rectree of order m (contributing weight m). The order of the rectree is the sum of all vertex weights.

So the order-2 rectree is just an edge between two simple vertices: ●—●. And we can verify order 3 has exactly 2: the 3-vertex path ●—●—●, and an edge with one vertex loaded with the order-2 rectree: ●—(●—●).

The generating function framework

Define four generating functions, all in the indeterminate x tracking total order:

• R(x)=∑[n≥2]r(n)x^n — the target, counting rectrees
• V(x)=x+R(x) — the weight of a single vertex (simple at weight 1, or loaded with any rectree)
• t(x)=∑[n≥1]t_nx^n — rooted trees with weighted vertices
• U(x) — all unrooted trees with weighted vertices (including single-vertex trees)

Equation 1 (Rooted trees, Pólya-style): A rooted tree is a root vertex attached to a multiset of rooted subtrees:

t^(x)=V(x)⋅exp(∑[k=1,∞]t(x^k)/k)

Equation 2 (Otter's theorem): Converting rooted → unrooted by subtracting the bicentered contribution:

U(x)=t(x)−(1/2)[t(x)^2−t(x^2)]

Equation 3 (Removing single-vertex trees): An unrooted weighted tree is either a single vertex (generating function V(x)=x+R(x)) or a genuine multi-vertex tree (generating function R(x)):

U(x)=V(x)+R(x)=x+2R(x)

This last equation encodes a beautiful combinatorial doubling: every rectree of order n appears twice among the weighted unrooted trees of order n — once as itself, and once as a single vertex loaded with a copy of itself. So R(x)=2U(x)−x.

The closed recurrence

Combining Equations 2 and 3 gives t_n=2R_n+B_n, where B_n=(1/2)([x^n]t^2−[x^n]t(x^2)) depends only on prior terms. Meanwhile, expanding Equation 1 as a Cauchy product t_n=∑[j] V_jE_{n−j} (where E is the exponential factor) and substituting yields a direct recurrence:

R_n=E_{n−1}+∑[j=2,n−1]R_jE_{n−j}−B_n   and   t_n=2R_n+B_n

where E_n is the coefficient of x^n in exp(∑[k]t(x^k)/k), computable via the standard recurrence nE_n=∑[k=1,n]ks_kE_{n−k} with s_n=∑[d∣n]t_{n/d}/d.

Everything on the right side depends only on t_k and R_k for k<n, so we can march forward from t_1=1, R_1=0.

[Brendan]

Meanwhile, my stupid generator confirmed 1689978 for order 13.  Given the agreement, and also the apparent correctness of Claude's generating function play, I think these numbers can be taken as correct.

Here are the values up to order 60, which took Maple mere milliseconds:

1, 2, 7, 22, 82, 308, 1231, 5011, 20997, 89347, 386340, 1689978, 7470286, 33304905, 149607999, 676428395, 3075991416, 14058997331, 64550018544, 297583759980, 1376963768074, 6392761588344, 29770046144891, 139022083485481, 650883577706649, 3054579449588136, 14366508407726890, 67707089846880739, 319697143115122734, 1512202074752961419, 7164692149890963520, 33998264059230009522, 161564693043641625076, 768828253287962647427, 3663289482790018873660, 17475954608470893405763, 83466005019013030147932, 399071729312685202016287, 1910031490638085018973732, 9150730652411534157835005, 43880928443986149228406286, 210611094589288422080311961, 1011705369659298368444353510, 4863819433237526353933851934, 23401071446856959074887941919, 112671560783941598858126364938, 542874502986377269614919245359, 2617449453680057186901783239201, 12628123921883422171921652360217, 60963474854543666685831450473525, 294483036259239990924221193001693, 1423313284306367974888245035272834, 6883049723228685537496266380362444, 33303705286052126678243675961607461, 161222999202742417552829142663473265, 780865499717573509060264519015392988, 3783839436916684255224570310421414826, 18343795855810017314072567464822712756, 88969049299156795309378821055788473595

[Jon Awbrey]

Re: Brett Schreiber
• https://groups.google.com/g/seqfan/c/pblPycq636s/m/GzzTLkd2AgAJ

Hi Brett, SeqFans,

Rectrees remind me a class of graphs I use for logical applications,
loosely based on graph-theoretic cacti, and described in more detail
as painted and rooted cacti (Parcs).

The paints are just boolean variables, any number of which may be
attached to each node. Parcs with no paints are called Bare Parcs.

Bare Parcs would correspond very roughly to Rectrees where the graphs
interior to each node are restricted to simple paths, except I allow
paths of length zero instead of the 2 or more you require in Rectrees.

There's a picture of a typical Parc on either of the following pages.

• https://oeis.org/wiki/Theme_One_Program_%E2%80%A2_Exposition#Painted_And_Rooted_Cacti
• https://inquiryintoinquiry.com/2024/06/12/theme-one-program-exposition-3-b/

Regards,

Jon

[brad klee]

> Does anyone get the feeling that thinking is gradually becoming optional?

Confusing progress with inevitability of an outcome is a fallacy because it 

doesn't consider rates of change, whether the evolve function is even smooth,

or what the environment looks like. 

For example, the prokaryotes needed an entire billion-years epoch before 

the eukaryotic revolution by endosymbiosis. 

The other common anthropocentric fallacy is believing that the particular series 

of catastrophic successes leading to our thinking ability couldn't have been 

catastrophic failures instead. It depends on details of what the environment 

looks like: space, energy, materials, etc. 

Assuming that this isn't a names-and-theorems salad, your example looks like 

what I call catastrophic success, but not in the bigger evolutionary sense. That's 

still great and it saves us some discovery time. But my recent experiments have 

seen comparable rates of catastrophic success and failure, so I'm still not sold 

on LLM as a autonomous research tool, at least for what I have access to. 

To answer your question more directly, and to give another example, now 

that I have these artifacts: 

https://github.com/bradleyklee/PolyformTown/tree/main/PolyformTown/data/rl6  

(I've never seen this data before and I haven't proven it all myself)

 

I'm concerned whether their derivation from five or six layers of LLM code 

has any flaws or logical failures? If no, I guess we have proved the hat tiling 

again. If yes, well, at least Hat Town now has a cool colored ASCII art post 

card that prints after only 30 seconds of boot-as-proof. 

Hey, I can still think, and I think a lot about certificates, validation tests, and

target selection. My next target is to use the new data to get as small a set 

of Wang tiles as I can possibly get, and I'm sure I will get something. Literally

anyone with an LLM-coder could do the same thing, and maybe even get  

a different result than whatever I end up getting.

One problem is that I'm only using one source of catastrophe. If it returns 

a false truth value, then I ask it to check the truth value, my expectation 

would be a false check value--catastrophe leading to more catastrophe, 

and possibly to a failure that looks like a success. Is this going to be the 

proof that ends my career because it's actually wrong? 

Because of this problem, it seems like I will have to think more in the 

future and I'm not worried about thinking gradually becoming optional.

That sounds like a peaceful death to me. 

Given evolutionary history I would be much more concerned about thinking 

becoming suddenly optional because a new apex predator has arrived. But 

I'm not worried about that right now because the environment isn't doing very 

well, and neither is its current apex predator. 

 

All the best, 

--Brad

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJeNNUgL%3DB6wPFc37eD8pGPF67_ak9zL5PBD1LG2XaSNNaJuYw%40mail.gmail.com.

[brad klee]

PS. Harm.On.ica had the following to say: 

<<
A small φ⁴ calculation from the three-tile hat model.

In the three-tile reduction, there is a natural two-state population

count. Let

    x = the number of hexagons not paired into dimers,

    y = the number of dimers.

Each hexagon contains one unreflected hat and each dimer contains 
one reflected hat. So the total number of unreflected hats is

    x + 2y,

while the number of reflected hats is

    y.

The local forcing/inflation rule gives the two-state matrix

    M = [[5, 9],

         [1, 2]].

Its characteristic polynomial is

    λ² - 7λ + 1,

so the Perron eigenvalue is

    λ = (7 + 3√5)/2 = φ⁴.

A right Perron eigenvector is

    v = (x,y) = (1, (√5 - 1)/6).

Therefore the asymptotic ratio of unreflected to reflected hats is

    (x + 2y) / y = φ⁴.

This is the same φ⁴ that appears in the usual hat monotile substitution

story. Goucher’s CP4Space post explains that hat tilings have

unreflected-to-reflected ratio φ⁴ : 1, computed from the dominant

eigenvector of the metatile substitution system. Here the same number

is showing up in the wild again, but now from a much smaller 2×2 matrix

coming out of the three-tile local forcing model. :contentReference[oaicite:0]{index=0}

>>

Sounds okay to me.

--Brad

On Thursday, May 21st, 2026 at 9:37 AM, brad klee <brad...@proton.me> wrote:

> Does anyone get the feeling that thinking is gradually becoming optional?