Monotonic trees (fwd)

[Emeric Deutsch]

I have failed to cc this to seqfan
Emeric

---------- Forwarded message ----------
Date: Wed, 18 Oct 2006 19:26:59 -0400 (EDT)
From: Emeric Deutsch <deutsch at duke.poly.edu>
To: franktaw at netscape.net
Subject: Re: Monotonic trees

Hi,

I believe I can do something about the ordered monotonic
trees. So far, mainly theoretically.

For verification, I will use the straightforward counting
of these trees up to 5 edges, according to their root degrees:

1| 1
2| 1  1
3| 1  2  1
4| 1  5  3  1
5| 1 10  9  4  1

Denote by Fk the g.f. of the monotone trees having root degree k.
We have F0=1.

We have F1=z(F0+F1) because at the end of the edge emanating from
the root (marked by z) we can have either a tree with root degree 0
or with root degree 1. This equation yields F1=z/(1-z).

We have F2=z^2(F0+F1+F2)^2 with a reasoning similar to the above one.
Using Maple I get

F2 := 1/2/z^2*(2*z^2+z-1+sqrt(4*z^3-3*z^2-2*z+1))/(-1+z)

Series is

z^2 + 2z^3 + 5z^4 + 10z^5 + 22z^6 + 46z^7 + 101z^8 + 220z^9 +...

Next equation is

  F3=z^3(F0+F1+F2+F3)^3.

I have to refresh my memory how to get with Maple the series
expansion of F3 without solving the equation.

However, with the usual solve command, I have obtained three
awful-looking solutions. The series expansion of one them, using
"floating" evaluation, does give z^3 + 3z^4 + 9z^5 + 25z^6 + 69z^7 +
186z^8 + ... .

Remark. The equations for the F[k]=Fk functions can be written as

            F[k]={(F[k-1])^(1/(k-1)) + zF[k]}^k

For better visibility: F4={(F3)^(1/3) + zF4}^4.

I hope you will be able to do much more.
Best,
Emeric


On Wed, 18 Oct 2006 franktaw at netscape.net wrote:

> Define a rooted tree is monotonic if the out-degree (number of children)
> of every node is greater than or equal to the out-degree of any of its
> children.  How many monotonic trees are there with n nodes?
> 
> Assuming unordered trees, I believe the sequence starts:
> 
> 1,1,2,3,6,10,21;
> 
> and for ordered trees:
> 
> 1,1,2,4,10,25,68.
> 
> I don't believe that either of these is in the OEIS, although this isn't
> enough terms to tell for certain.
> 
> Can somebody extend either or both of these?
> 
> (One could make similar definition with out-degree increasing from the
> root, but you have to exclude leaf nodes from consideration.  This is
> much cleaner.)
> 
> Franklin T. Adams-Watters
> 
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading 
> spam and email virus protection.
> 
>