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

Author

David Callan, Aug 03 2021

Keywords

• nonn

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.

Examples

			See Link.
		

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.

Crossrefs

Cf. A196545.

Programs

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}]

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)).