A382440 Number of rooted full binary trees with n internal nodes, up to their multiset of subtree sizes.

1, 1, 2, 3, 6, 11, 23, 45, 95, 194, 414, 863, 1850, 3910, 8413, 17887, 38517, 82249, 177133, 378871, 815265, 1745006, 3750385, 8024725, 17219142, 36817113

Offset: 1

Author

Ludovic Schwob, Mar 25 2025

Keywords

• nonn
• more

Comments

The multiset of subtree sizes of a binary tree T is the multiset containing the number of internal nodes of the subtrees rooted at each internal node of T.

Isomorphic binary trees have the same multiset of subtree sizes. More precisely, binary trees giving rectangle tilings with the same shapes (cf. A247139) have the same multiset of subtree sizes.

Examples

			The following binary tree has its multiset of subtree sizes equal to {4, 3, 1, 1}:
            o
           / \
          o   \
         / \   \
        /   \   \
       /     \   \
      o       o   \
     / \     / \   \
    o   o   o   o   o
The 6 multisets of subtree sizes corresponding to a(5) = 6 are:
  {5, 3, 1, 1, 1},   {5, 2, 2, 1, 1},   {5, 3, 2, 1, 1},
  {5, 4, 2, 1, 1},   {5, 4, 3, 1, 1},   {5, 4, 3, 2, 1}.
		

Crossrefs

Cf. A000108, A001190, A247139.