A330762 -id:A330762 - cp's OEIS frontend

A330469 Number of series-reduced rooted trees whose leaves are multisets with a total of n elements covering an initial interval of positive integers.

1, 1, 4, 24, 250, 3744, 73408, 1768088, 50468854, 1664844040, 62304622320, 2607765903568, 120696071556230, 6120415124163512, 337440974546042416, 20096905939846645064, 1285779618228281270718, 87947859243850506008984, 6404472598196204610148232

Offset: 0

Gus Wiseman, Dec 22 2019

nonn

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.

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

Andrew Howroyd, Table of n, a(n) for n = 0..200

The singleton-reduced version is A316651.
The unlabeled version is A330465.
The strongly normal case is A330467.
The case when leaves are sets is A330764.
Row sums of A330762.
Cf. A000311, A000669, A004114, A005121, A005804, A141268, A292504, A292505, A316652, A318812, A318849, A319312, A330625.

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

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

Terms a(9) and beyond from Andrew Howroyd, Dec 29 2019

A330763 Triangle read by rows: T(n,k) is the number of series-reduced rooted trees whose leaves are sets of colors with a total of n elements using exactly k colors.

Original entry on oeis.org

1, 1, 2, 2, 8, 8, 5, 41, 90, 58, 12, 204, 852, 1264, 612, 33, 1046, 7428, 19568, 21510, 8374, 90, 5456, 62682, 262912, 496270, 431040, 140408, 261, 29165, 523167, 3291021, 9520220, 13884960, 9947294, 2785906, 766, 158792, 4358182, 39636784, 165204730, 360421716, 426677440, 259854304, 63830764

Offset: 1

Andrew Howroyd, Dec 29 2019

			Triangle begins:
    1;
    1,     2;
    2,     8,      8;
    5,    41,     90,      58;
   12,   204,    852,    1264,     612;
   33,  1046,   7428,   19568,   21510,     8374;
   90,  5456,  62682,  262912,  496270,   431040,  140408;
  261, 29165, 523167, 3291021, 9520220, 13884960, 9947294, 2785906;
  ...
The T(3,2) = 8 trees are: ((1)(12)), ((2)(12)), ((1)(2)(2)), ((1)(1)(2)), ((1)((2)(2))), ((1)((1)(2))), ((2)((1)(2))), ((2)((1)(1))).

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Column 1 is A000669.
Main diagonal is A005804.
Row sums are A330764.
Cf. A330762 (leaves are multisets).

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(k,n)]))[n])); v}
M(n)={my(v=vector(n, k, R(n, k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, 1..n]))} \\ Andrew Howroyd, Dec 29 2019

cp's OEIS Frontend

A330469 Number of series-reduced rooted trees whose leaves are multisets with a total of n elements covering an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions