A382440 -id:A382440 - cp's OEIS frontend

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

Ludovic Schwob, May 14 2025

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).

			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

Sean A. Irvine, Java program (github)

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

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

A383895 Number of spiny partitions with exactly n parts.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 47, 111, 267, 646, 1582, 3892, 9636, 23961, 59871, 150128, 377738, 953029, 2410626, 6111055, 15524013, 39508683, 100719223, 257150952, 657454544, 1683042629, 4313582090, 11067748352, 28426813910, 73082880708, 188059428289, 484330230117, 1248338233493

Offset: 0

Ludovic Schwob, May 14 2025

nonn

An integer partition is said to be spiny if for all parts k having multiplicity m the number of parts <= k is >= m*k.

Arborescent partitions (cf. A383894) are spiny partitions.

			The 20 spiny partitions corresponding to a(5) = 20 are:
  (11111),  (21111),  (22111),  (31111),  (32111),
  (32211),  (41111),  (42111),  (42211),  (43111),
  (43211),  (51111),  (52111),  (52211),  (53111),
  (53211),  (54111),  (54211),  (54311),  (54321).
The partition (42221) is not spiny because the part 2 has multiplicity 3 but the number of parts <=2 is 4 < 3*2.
The only spiny partition of length 5 which does not correspond to an arborescent partition is (42211), i.e. there is no tree whose multiset of subtree sizes is {6, 4, 2, 2, 1, 1} (cf. A383894).

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A382440, A383894.

def A383895(n): #generator of terms a(0) to a(n)
    L = [[1]]
    for k in range(1,n+2):
        l = [0]
        for i in range(1,k+1):
            l.append(sum(L[a][b] for a in range(k-(k//i),k) for b in range(i)))
        L.append(l)
        yield l[-1]

cp's OEIS Frontend

A383894 Number of arborescent partitions with exactly n parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions