|
|
A330469
|
|
Number of series-reduced rooted trees whose leaves are multisets with a total of n elements covering an initial interval of positive integers.
|
|
10
|
|
|
1, 1, 4, 24, 250, 3744, 73408, 1768088, 50468854, 1664844040, 62304622320, 2607765903568, 120696071556230, 6120415124163512, 337440974546042416, 20096905939846645064, 1285779618228281270718, 87947859243850506008984, 6404472598196204610148232
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also the number of different colorings of phylogenetic trees with n labels using a multiset of colors covering an initial interval of positive integers. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(3) = 24 trees:
(123) (122) (112) (111)
((1)(23)) ((1)(22)) ((1)(12)) ((1)(11))
((2)(13)) ((2)(12)) ((2)(11)) ((1)(1)(1))
((3)(12)) ((1)(2)(2)) ((1)(1)(2)) ((1)((1)(1)))
((1)(2)(3)) ((1)((2)(2))) ((1)((1)(2)))
((1)((2)(3))) ((2)((1)(2))) ((2)((1)(1)))
((2)((1)(3)))
((3)((1)(2)))
|
|
MATHEMATICA
|
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
multing[t_, n_]:=Array[(t+#-1)/#&, n, 1, Times];
amemo[m_]:=amemo[m]=1+Sum[Product[multing[amemo[s[[1]]], Length[s]], {s, Split[c]}], {c, Select[mps[m], Length[#]>1&]}];
Table[Sum[amemo[m], {m, allnorm[n]}], {n, 0, 5}]
|
|
PROG
|
(PARI)
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[]); for(n=1, n, v=concat(v, EulerT(concat(v, [binomial(n+k-1, k-1)]))[n])); v}
seq(n)={concat([1], sum(k=1, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k))))} \\ Andrew Howroyd, Dec 29 2019
|
|
CROSSREFS
|
The singleton-reduced version is A316651.
The strongly normal case is A330467.
The case when leaves are sets is A330764.
Cf. A000311, A000669, A004114, A005121, A005804, A141268, A292504, A292505, A316652, A318812, A318849, A319312, A330625.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|