Monotonic trees

[Christian G. Bower]

> 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;

1 1 2 3 6 10 21 38 78 153 314 632 1313 2700 5646
11786 24831 52348 111027 235834 502986 1074739
2303146 4944507 10639201 22930493 49511948 107065966
231874164 502834328 1091842824 2373565195 5165713137
11254029616
> and for ordered trees:

> 1,1,2,4,10,25,68.

1 1 2 4 10 25 68 187 530 1523 4447 13121 39107 117490
355507 1082234 3312255 10185125 31450633 97480337
303157086 945671951 2958113722 9276528602 29158191215
91845796986 289874628176 916536727561 2902830539661
9208203464265 29252562316846 93056669529623
296406936716800 945262807252333

Also for mobiles (cycle rooted trees):

1 1 2 3 6 10 24 47 113 258 624 1492 3694 9090 22753
57111 144541 367243 938449 2406720 6198045 16013447
41507254 107887092 281170859 734518306 1923119062
5045423169 13262334340 34923020733 92113656841
243337161229 643759586561 1705417962538

> I don't believe that either of these is in the OEIS, although this 
> isn't
> enough terms to tell for certain.

Not in EIS at the moment.

The algorithm is difficult to describe, but not that difficult
to implement.

The idea is that an MRT (monotone rooted tree) whose root has
n children is a root attached to a set of exactly n MRTs
whose root has at most n children.

In species notation we have

A_0 = X
A_n = X E_n(A_0+A_1+...+A_n)
A = A_0 + A_1 + ...

The ordered version replace E with L (or "set" with "linear order")

You may be able to do this with Maple's combstruct.
Haven't used it myself, but I know it has the "SET" operation and
"SEQ" for linear orders.

The ordered version can be written as a g.f. as 

A_0(x) = x
A_n(x) = x*(A_0(x)+A_1(x)+...+A_n(x))^n
A(x) = A_0(x) + A_1(x) + ...

I can submit these.
It won't happen until tomorrow at least.

> 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