A255841 The number of unordered binary trees that contain n distinct subtrees.

1, 2, 6, 25, 137, 945, 7927, 78731, 906705, 11908357, 175978520, 2893866042, 52467157456, 1040596612520, 22425725219277, 522102436965475, 13064892459014192, 349829488635512316

Offset

1,2

Comments

Each node has no more than two children and the relative order of children is unimportant. See A254789 for the ordered case.

The set of subtrees includes the full tree as well as the union of those in the principal subtrees.

A lower bound for the sequence is (n-1)!, which counts trees where one principal subtree is contained in the other (including trees with only one principal subtree).

a(n) is also the number of unordered full binary trees with n+1 subtrees.

Links

Andrew Szymczak, Table of n, a(n) for n = 1..80

Philippe Flajolet et al., Analytic variations on the common subexpression problem, Automata, Languages and Programming, Lecture Notes in Computer Science, Volume 443, 1990, pp 220-234.

Project Euler.net, Counting Subtrees, Project Euler Forums, (2015).

Andrew Szymczak et al., Distinct subtrees in binary trees, Math StackExchange, (2015).

Crossrefs

Cf. A254789.

Sequence in context: A020100 A128230 A084784 * A197772 A135881 A007815

Adjacent sequences: A255838 A255839 A255840 * A255842 A255843 A255844

Keyword

nonn,hard,changed

Author

Andrew Szymczak, Mar 07 2015

Status

approved