|
|
A330467
|
|
Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.
|
|
10
|
|
|
1, 1, 4, 18, 154, 1614, 23733, 396190, 8066984, 183930948, 4811382339, 138718632336, 4451963556127, 155416836338920, 5920554613563841, 242873491536944706, 10725017764009207613, 505671090907469848248, 25415190929321149684700, 1354279188424092012064226
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.
Also the number of different colorings of phylogenetic trees with n labels using strongly normal multisets of colors. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(3) = 18 trees:
{1,1,1} {1,1,2} {1,2,3}
{{1},{1,1}} {{1},{1,2}} {{1},{2,3}}
{{1},{1},{1}} {{2},{1,1}} {{2},{1,3}}
{{1},{{1},{1}}} {{1},{1},{2}} {{3},{1,2}}
{{1},{{1},{2}}} {{1},{2},{3}}
{{2},{{1},{1}}} {{1},{{2},{3}}}
{{2},{{1},{3}}}
{{3},{{1},{2}}}
|
|
MATHEMATICA
|
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
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, strnorm[n]}], {n, 0, 5}]
|
|
PROG
|
(PARI) \\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n), p=sExp(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n ) + polcoef(p, n)); 1 + x*Ser(v)}
StronglyNormalLabelingsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 28 2020
|
|
CROSSREFS
|
The singleton-reduced version is A316652.
Not requiring weakly decreasing multiplicities gives A330469.
The case where the leaves are sets is A330625.
Cf. A000311, A000669, A004114, A005121, A005804, A141268, A292504, A292505, A318812, A318849, A319312, A330471, A330475.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|