A320176 Number of series-reduced rooted trees whose leaves are strict integer partitions whose multiset union is a strict integer partition of n.

1, 1, 3, 3, 5, 13, 15, 23, 33, 99, 109, 183, 251, 383, 1071, 1261, 2007, 2875, 4291, 5829, 16297, 18563, 30313, 42243, 63707, 85351, 125465, 297843, 356657, 556729, 783637, 1151803, 1564173, 2249885, 2988729, 6803577, 8026109, 12465665, 17124495, 25272841, 33657209

Offset

1,3

Comments

Also the number of orderless tree-factorizations of Heinz numbers of strict integer partitions of n.

Also the number of phylogenetic trees on a set of distinct labels summing to n.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{k>0} A008289(n, k)*A005804(k). - Andrew Howroyd, Oct 26 2018

Example

The a(1) = 1 through a(7) = 15 rooted trees:
  (1)  (2)  (3)       (4)       (5)       (6)            (7)
            (21)      (31)      (32)      (42)           (43)
            ((1)(2))  ((1)(3))  (41)      (51)           (52)
                                ((1)(4))  (321)          (61)
                                ((2)(3))  ((1)(5))       (421)
                                          ((2)(4))       ((1)(6))
                                          ((1)(23))      ((2)(5))
                                          ((2)(13))      ((3)(4))
                                          ((3)(12))      ((1)(24))
                                          ((1)(2)(3))    ((2)(14))
                                          ((1)((2)(3)))  ((4)(12))
                                          ((2)((1)(3)))  ((1)(2)(4))
                                          ((3)((1)(2)))  ((1)((2)(4)))
                                                         ((2)((1)(4)))
                                                         ((4)((1)(2)))

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
got[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[got/@p]], {p, Select[sps[m], Length[#]>1&]}], m];
Table[Length[Join@@Table[got[m], {m, Select[IntegerPartitions[n], UnsameQ@@#&]}]], {n, 20}]

Prog

(PARI) \\ here S(n) is first n terms of A005804.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n, k)={my(v=vector(n)); for(n=1, n, v[n]=binomial(n+k-1, n) + EulerT(v[1..n])[n]); v}
S(n)={my(M=Mat(vectorv(n, k, b(n, k)))); vector(n, k, sum(i=1, k, binomial(k, i)*(-1)^(k-i)*M[i, k]))}
seq(n)={my(u=S((sqrtint(8*n+1)-1)\2)); [sum(i=1, poldegree(p), polcoef(p, i)*u[i]) | p <- Vec(prod(k=1, n, 1 + x^k*y + O(x*x^n))-1)]} \\ Andrew Howroyd, Oct 26 2018

Crossrefs

Cf. A000669, A005804, A008289, A141268, A292504, A300660, A319312, A320171, A320174, A320175, A320177, A320178.

Sequence in context: A231895 A218426 A321662 * A298478 A144419 A212322

Adjacent sequences: A320173 A320174 A320175 * A320177 A320178 A320179

Keyword

nonn

Author

Gus Wiseman, Oct 07 2018

Extensions

Terms a(31) and beyond from Andrew Howroyd, Oct 26 2018

Status

approved