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
Keywords
Examples
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).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..200
Programs
-
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]
Comments