A383894 Number of arborescent partitions with exactly n parts.

1, 1, 2, 4, 9, 19, 44, 96, 220, 489, 1115, 2483, 5646, 12571, 28343, 63152, 141621, 314330, 701327, 1552149, 3445128, 7599990, 16789039, 36908077

Offset: 1

Author

Ludovic Schwob, May 14 2025

Keywords

• nonn
• more

Comments

Equivalently, multisets of subtree sizes of rooted trees with n nodes.

The multiset of subtree sizes of a rooted tree T is the multiset containing the number of nodes of the subtrees rooted at each node of T. Integer partitions obtained this way are called arborescent partitions.

All arborescent partitions are spiny partitions (cf. A383895).

Examples

			The following rooted tree has its multiset of subtree sizes equal to {8, 7, 3, 2, 1, 1, 1, 1}:
              o
              |
              o
             /|\
            / | \
           o  o  o
          / \    |
         o   o   o
The 9 arborescent partitions corresponding to a(5) = 9 are:
  (51111),   (52111),   (52211),
  (53111),   (53211),   (54111),
  (54211),   (54311),   (54321).
The following two non-isomorphic trees have the same multiset of subtree sizes, which is {6, 3, 2, 1, 1, 1}:
           o                 o
          / \               /|\
         o   o             o o o
        / \   \            |
       o   o   o           o
                           |
                           o
		

Links

• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A000081 (number of rooted trees), A382440 (subtree sizes of binary trees), A383895 (spiny partitions).

Extensions

a(18)-a(24) from Sean A. Irvine, May 25 2025