A383895 Number of spiny partitions with exactly n parts.

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,3

Comments

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.

Links

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

Example

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

Prog

(Python)
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]

Crossrefs

Cf. A382440, A383894.

Sequence in context: A130802 A022543 A307557 * A036618 A349014 A003018

Adjacent sequences: A383892 A383893 A383894 * A383896 A383897 A383898

Keyword

nonn

Author

Ludovic Schwob, May 14 2025

Status

approved