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

Author

Andrew Szymczak, Mar 07 2015

Keywords

• nonn
• hard

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.