A346787 Ordered lone-child-avoiding trees where vertices have decreasing subtree sizes.

1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 68, 128, 253, 489, 981, 1930, 3899, 7771, 15858, 31915, 65503, 133070, 274631, 561371, 1164240, 2393652, 4983614, 10299238, 21511537, 44637483, 93552858, 194809152, 409270569, 855199845, 1800958182, 3773297872, 7963655481

Offset

1,5

Comments

a(n) is the number of size-n, rooted, ordered, lone-child-avoiding trees in which the subtrees of each non-leaf vertex, taken left to right, have weakly decreasing sizes, where size is measured by number of vertices.

The analogous trees when size is measured by number of leaves are counted by A196545.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..2948

David Callan, Trees of size up to 7 for A346787

David Callan, A Combinatorial Interpretation for Sequence A345973 in OEIS, arXiv:2108.04969 [math.CO], 2021.

Formula

Counting by sizes of subtrees of the root, a(n) is the sum, over all non-singleton partitions i_1,i_2,...,i_k of n-1, of the product a(i_1)a(i_2) ... a(i_k).

G.f. satisfies A(x)=x/((1+x)*Product_{n>=1} (1 - a(n)*x^n)).

Example

See Link.

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> b(n-1, n-2):
seq(a(n), n=1..40);  # Alois P. Heinz, Aug 05 2021

Mathematica

a[1] = 1; a[2] = 0;
a[n_] /; n >= 3 := a[n] = Apply[Plus, Map[Apply[Times, Map[a, #]] &, Rest[IntegerPartitions[n - 1]]]]
Table[a[n], {n, 20}]

Crossrefs

Cf. A196545.

Sequence in context: A005833 A247162 A001678 * A113292 A342012 A050291

Adjacent sequences: A346784 A346785 A346786 * A346788 A346789 A346790

Keyword

nonn

Author

David Callan, Aug 03 2021

Status

approved