A346787 - OEIS

%I #19 Jan 10 2022 11:03:24

%S 1,0,1,1,2,3,6,10,19,35,68,128,253,489,981,1930,3899,7771,15858,31915,

%T 65503,133070,274631,561371,1164240,2393652,4983614,10299238,21511537,

%U 44637483,93552858,194809152,409270569,855199845,1800958182,3773297872,7963655481

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

%C 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.

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

%H Alois P. Heinz, <a href="/A346787/b346787.txt">Table of n, a(n) for n = 1..2948</a>

%H David Callan, <a href="/A346787/a346787.pdf">Trees of size up to 7 for A346787</a>

%H David Callan, <a href="https://arxiv.org/abs/2108.04969">A Combinatorial Interpretation for Sequence A345973 in OEIS</a>, arXiv:2108.04969 [math.CO], 2021.

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

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

%e See Link.

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p        b(n, i-1)+a(i)*b(n-i, min(n-i, i))))

%p     end:

%p a:= n-> b(n-1, n-2):

%p seq(a(n), n=1..40);  # _Alois P. Heinz_, Aug 05 2021

%t a[1] = 1; a[2] = 0;

%t a[n_] /; n >= 3 := a[n] = Apply[Plus, Map[Apply[Times, Map[a, #]] &, Rest[IntegerPartitions[n - 1]]]]

%t Table[a[n], {n, 20}]

%Y Cf. A196545.

%K nonn

%O 1,5

%A _David Callan_, Aug 03 2021