login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A346787 Ordered lone-child-avoiding trees where vertices have decreasing subtree sizes. 1
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 (list; graph; refs; listen; history; text; internal format)
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
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
KEYWORD
nonn
AUTHOR
David Callan, Aug 03 2021
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 08:18 EDT 2024. Contains 373697 sequences. (Running on oeis4.)