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

Author

Gus Wiseman, Oct 07 2018

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

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

Programs

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}]

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

Formula

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

Extensions

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