|
|
A320154
|
|
Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.
|
|
17
|
|
|
1, 2, 5, 18, 92, 588, 4328, 35920, 338437, 3654751, 45105744, 625582147, 9539374171, 157031052142, 2757275781918, 51293875591794, 1007329489077804, 20840741773898303, 453654220906310222, 10380640686263467204, 249559854371799622350, 6301679967177242849680
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.
Also the number of balanced phylogenetic rooted trees on n distinct labels.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(4) = 18 rooted trees:
(1) (12) (123) (1234)
((1)(2)) ((1)(23)) ((1)(234))
((2)(13)) ((12)(34))
((3)(12)) ((13)(24))
((1)(2)(3)) ((14)(23))
((2)(134))
((3)(124))
((4)(123))
((1)(2)(34))
((1)(3)(24))
((1)(4)(23))
((2)(3)(14))
((2)(4)(13))
((3)(4)(12))
((1)(2)(3)(4))
(((1)(2))((3)(4)))
(((1)(3))((2)(4)))
(((1)(4))((2)(3)))
|
|
MATHEMATICA
|
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
gug[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[gug/@mtn]], {mtn, Select[sps[m], Length[#]>1&]}], m];
Table[Length[Select[gug[Range[n]], SameQ@@Length/@Position[#, _Integer]&]], {n, 9}]
|
|
PROG
|
(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n, k)={my(u=vector(n), v=vector(n)); u[1]=k; u=EulerT(u); while(u, v+=u; u=EulerT(u)-u); v}
seq(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]))} \\ Andrew Howroyd, Oct 26 2018
|
|
CROSSREFS
|
Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A292504, A300660, A319312.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|