A000758: possible identification and relation to A136439

[Siddhartha Mahajan]

Dear Seqfan members,

I hope you are well! This is my first message on the group.

I was going through A000758 (https://oeis.org/A000758), which currently has only 10 terms and the description "Related to cumulative height of rooted plane trees." The entry does not have a formula or program, and the only reference is to a Cazals preprint which I have not been able to locate. The entry has not been touched since it was made in 2013.

I tried to understand what statistic could be producing the terms, and I think I have found a fairly natural interpretation.

If T runs over rooted plane trees with n edges, and h(T) is the height of T in edges, then all the published terms of A000758 are reproduced by

a(n) = sum_T (h(T) - 1).

I found this computationally by completely enumerating rooted plane trees and comparing the sequence against a collection of tree statistics. The important details seem to be that the trees are indexed by edges rather than nodes, and that we subtract 1 from the height of every tree.

This also gave rise to the following interesting connection:

A000758(n) = A136439(n) - A000108(n),

where A136439 (https://oeis.org/A136439) is the sum of the heights of Dyck excursions of length 2n, equivalently the total height of rooted plane trees with n edges, and A000108 is the Catalan numbers.

A136439:
1, 3, 10, 34, 118, 417, 1495, 5421, 19838, 73149, 271453, ...

A000108:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ...

and their difference is

0, 1, 5, 20, 76, 285, 1066, 3991, 14976, 56353, 212667, ...

which gives all 10 published terms of A000758 and also the next term.

Using the Dyck path interpretation I also get an exact formula. If D(n,h) is the number of Dyck paths of semilength n confined to 0 <= y <= h, then

D(n,h) = sum_{j in Z} [ binomial(2n, n+j(h+2)) - binomial(2n, n+1+j(h+2)) ]

and therefore

a(n) = sum_{h=1}^{n-1} (Catalan(n) - D(n,h)).

I checked this in a few independent ways: by brute force enumeration of all rooted plane trees for small n, by a DP for bounded-height Dyck paths, and by two forms of the binomial formula. All methods reproduce the 10 published terms.

For A000758 this means that:

a(11) = 212667
a(12) = 804860
a(13) = 3054328
a(14) = 11620078
a(15) = 44311883
a(16) = 169344658
a(17) = 648470768
a(18) = 2487770856
a(19) = 9560286588
a(20) = 36797405946.
.....

Since A136439 already has many more terms, I suppose once the identity is accepted A000758 can be extended much further than this as well. (I calculated it till 80 terms for now)

The one thing I am not sure about is the original Cazals reference. Since I could not find the preprint, I cannot confirm that this was exactly the statistic that was originally intended for A000758. It seems like a natural interpretation and the connection is nice but I thought it would be better to ask before proposing edits to the entry.

Does this interpretation/connection look correct to you? Also, does anyone happen to have the Cazals preprint or know what definition was originally intended here?

Thank you for your time and my apologies if I am missing something obvious.

Best Regards,
Siddhartha

[jpallouche.math]

Hi

F. Cazals is probably the colleague here:
https://team.inria.fr/abs/team-members/homepage-frederic-cazals/
so that you might consider asking him for that preprint.

best
jpa

Le 20/08/2026 à 20:24, Siddhartha Mahajan a écrit :
>
> Dear Seqfan members,
>
> I hope you are well! This is my first message on the group.
>
> I was going through A000758 (https://oeis.org/A000758), which
> currently has only 10 terms and the description "Related to cumulative
> height of rooted plane trees." The entry does not have a formula or
> program, and the only reference is to a Cazals preprint which I have
> not been able to locate. The entry has not been touched since it was
> made in 2013.
>

[...]

[Sean A. Irvine]

I did email Frederic Cazals about this sequence several years ago.

His response to me was that he no longer knew what A000758 was.

Sean.

--
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/495972b3-2855-4432-bf0c-3f87a5a617da%40gmail.com.

[jpallouche.math]

too bad

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

[Charles Greathouse]

I, for one, propose accepting Siddhartha’s interpretation.

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