A330625 -id:A330625 - cp's OEIS frontend

A330465 Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.

1, 4, 14, 87, 608, 5573, 57876, 687938, 9058892, 130851823, 2048654450, 34488422057, 620046639452, 11839393796270, 238984150459124, 5079583100918338, 113299159314626360, 2644085918303683758, 64393240540265515110, 1632731130253043991252, 43013015553755764179000

Offset: 1

Gus Wiseman, Dec 21 2019

nonn

Also inequivalent leaf-colorings of phylogenetic rooted trees with n labels. A phylogenetic rooted tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets.

			Non-isomorphic representatives of the a(3) = 14 trees:
  ((1)((1)(1)))  ((1)((1)(2)))  ((1)((2)(3)))  ((2)((1)(1)))
  ((1)(1)(1))    ((1)(1)(2))    ((1)(2)(3))    ((2)(1,1))
  ((1)(1,1))     ((1)(1,2))     ((1)(2,3))
  (1,1,1)        (1,1,2)        (1,2,3)

The version where leaves are atoms is A318231.
The case with sets as leaves is A330624.
The case with disjoint sets as leaves is A141268.
Labeled versions are A330467 (strongly normal) and A330469 (normal).
The singleton-reduced version is A330470.
Cf. A000311, A000669, A004114, A005804, A007716, A281118, A289501, A292504, A316651, A316652, A318812, A319312, A330471, A330474, A330625, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n), p=sEulerT(x*sv(1) + O(x*x^n))); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(v[1..n])), n ) + polcoef(p,n)); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 13 2020

Terms a(7) and beyond from Andrew Howroyd, Dec 13 2020

A330467 Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.

Original entry on oeis.org

1, 1, 4, 18, 154, 1614, 23733, 396190, 8066984, 183930948, 4811382339, 138718632336, 4451963556127, 155416836338920, 5920554613563841, 242873491536944706, 10725017764009207613, 505671090907469848248, 25415190929321149684700, 1354279188424092012064226

Offset: 0

Gus Wiseman, Dec 22 2019

nonn

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.

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

The singleton-reduced version is A316652.
The unlabeled version is A330465.
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.

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

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

Terms a(10) and beyond from Andrew Howroyd, Dec 28 2020

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

Original entry on oeis.org

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

A330675 Number of balanced reduced multisystems of maximum depth whose atoms constitute a strongly normal multiset of size n.

Original entry on oeis.org

1, 1, 2, 6, 43, 440, 7158, 151414

Offset: 0

Gus Wiseman, Dec 30 2019

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem.

A finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

			The a(2) = 2 and a(3) = 6 multisystems:
  {1,1}  {{1},{1,1}}
  {1,2}  {{1},{1,2}}
         {{1},{2,3}}
         {{2},{1,1}}
         {{2},{1,3}}
         {{3},{1,2}}
The a(4) = 43 multisystems (commas and outer brackets elided):
  {{1}}{{1}{11}} {{1}}{{1}{12}} {{1}}{{1}{22}} {{1}}{{1}{23}} {{1}}{{2}{34}}
  {{11}}{{1}{1}} {{11}}{{1}{2}} {{11}}{{2}{2}} {{11}}{{2}{3}} {{12}}{{3}{4}}
                 {{1}}{{2}{11}} {{1}}{{2}{12}} {{1}}{{2}{13}} {{1}}{{3}{24}}
                 {{12}}{{1}{1}} {{12}}{{1}{2}} {{12}}{{1}{3}} {{13}}{{2}{4}}
                 {{2}}{{1}{11}} {{2}}{{1}{12}} {{1}}{{3}{12}} {{1}}{{4}{23}}
                                {{2}}{{2}{11}} {{13}}{{1}{2}} {{14}}{{2}{3}}
                                {{22}}{{1}{1}} {{2}}{{1}{13}} {{2}}{{1}{34}}
                                               {{2}}{{3}{11}} {{2}}{{3}{14}}
                                               {{23}}{{1}{1}} {{23}}{{1}{4}}
                                               {{3}}{{1}{12}} {{2}}{{4}{13}}
                                               {{3}}{{2}{11}} {{24}}{{1}{3}}
                                                              {{3}}{{1}{24}}
                                                              {{3}}{{2}{14}}
                                                              {{3}}{{4}{12}}
                                                              {{34}}{{1}{2}}
                                                              {{4}}{{1}{23}}
                                                              {{4}}{{2}{13}}
                                                              {{4}}{{3}{12}}

The case with all atoms equal is A000111.
The case with all atoms different is A006472.
The version allowing all depths is A330475.
The unlabeled version is A330663.
The version where the atoms are the prime indices of n is A330665.
The (weakly) normal version is A330676.
The version where the degrees are the prime indices of n is A330728.
Multiset partitions of strongly normal multisets are A035310.
Series-reduced rooted trees with strongly normal leaves are A316652.
Cf. A000311, A000669, A001055, A001678, A005121, A005804, A316651, A318812, A330467, A330474, A330625, A330628, A330664, A330677, A330679.

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]]]];
totm[m_]:=Prepend[Join@@Table[totm[p],{p,Select[mps[m],1

A330624 Number of non-isomorphic series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with a total of n elements.

Original entry on oeis.org

1, 1, 3, 10, 61, 410, 3630

Offset: 0

Gus Wiseman, Dec 25 2019

A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 10 trees:
  {1}  {1,2}      {1,2,3}
       {{1},{1}}  {{1},{1,2}}
       {{1},{2}}  {{1},{2,3}}
                  {{1},{1},{1}}
                  {{1},{1},{2}}
                  {{1},{2},{3}}
                  {{1},{{1},{1}}}
                  {{1},{{1},{2}}}
                  {{1},{{2},{3}}}
                  {{2},{{1},{1}}}

The version with multisets as leaves is A330465.
The singleton-reduced case is A330626.
A labeled version is A330625 (strongly normal).
The case with all atoms distinct is A141268.
The case where all leaves are singletons is A330470.
Cf. A000669, A004111, A005804, A007716, A273873, A300660, A320296, A330628, A330668, A330677.

A330626 Number of non-isomorphic series/singleton-reduced rooted trees whose leaves are sets (not necessarily disjoint) with a total of n atoms.

Original entry on oeis.org

1, 1, 1, 3, 17, 100, 755

Offset: 0

Gus Wiseman, Dec 26 2019

A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part).

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 17 trees:
  {1}  {1,2}  {1,2,3}      {1,2,3,4}
              {{1},{1,2}}  {{1},{1,2,3}}
              {{1},{2,3}}  {{1,2},{1,2}}
                           {{1,2},{1,3}}
                           {{1},{2,3,4}}
                           {{1,2},{3,4}}
                           {{1},{1},{1,2}}
                           {{1},{1},{2,3}}
                           {{1},{2},{1,2}}
                           {{1},{2},{1,3}}
                           {{1},{2},{3,4}}
                           {{1},{{1},{1,2}}}
                           {{1},{{1},{2,3}}}
                           {{1},{{2},{1,2}}}
                           {{1},{{2},{1,3}}}
                           {{1},{{2},{3,4}}}
                           {{2},{{1},{1,3}}}

The non-singleton-reduced version is A330624.
The generalization where leaves are multisets is A330470.
A labeled version is A330628 (strongly normal).
The case with all atoms distinct is A004114.
The balanced version is A330668.
Cf. A000669, A004111, A005804, A007716, A141268, A330465, A330625, A330627, A330654, A330663, A330677.

A330628 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).

Original entry on oeis.org

1, 1, 1, 5, 42, 423, 5458, 80926

Offset: 0

Gus Wiseman, Dec 26 2019

A series/singleton-reduced rooted tree on a multiset m is either the multiset m itself or a sequence of series/singleton-reduced rooted trees, one on each part of a multiset partition of m that is neither minimal (all singletons) nor maximal (only one part).

A finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

			The a(4) = 42 trees:
  {{1}{1}{12}}    {{12}{12}}      {{1}{123}}      {1234}
  {{1}{{1}{12}}}  {{1}{2}{12}}    {{12}{13}}      {{1}{234}}
                  {{1}{{2}{12}}}  {{1}{1}{23}}    {{12}{34}}
                  {{2}{{1}{12}}}  {{1}{2}{13}}    {{13}{24}}
                                  {{1}{3}{12}}    {{14}{23}}
                                  {{1}{{1}{23}}}  {{2}{134}}
                                  {{1}{{2}{13}}}  {{3}{124}}
                                  {{1}{{3}{12}}}  {{4}{123}}
                                  {{2}{{1}{13}}}  {{1}{2}{34}}
                                  {{3}{{1}{12}}}  {{1}{3}{24}}
                                                  {{1}{4}{23}}
                                                  {{2}{3}{14}}
                                                  {{2}{4}{13}}
                                                  {{3}{4}{12}}
                                                  {{1}{{2}{34}}}
                                                  {{1}{{3}{24}}}
                                                  {{1}{{4}{23}}}
                                                  {{2}{{1}{34}}}
                                                  {{2}{{3}{14}}}
                                                  {{2}{{4}{13}}}
                                                  {{3}{{1}{24}}}
                                                  {{3}{{2}{14}}}
                                                  {{3}{{4}{12}}}
                                                  {{4}{{1}{23}}}
                                                  {{4}{{2}{13}}}
                                                  {{4}{{3}{12}}}

The generalization where leaves are multisets is A330471.
The non-singleton-reduced version is A330625.
The unlabeled version is A330626.
The case with all atoms distinct is A000311.
Strongly normal multiset partitions are A035310.
Cf. A000669, A004111, A004114, A005804, A196545, A281118, A330465, A330467, A330624, A330654, A330668.

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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
ssrtrees[m_]:=Prepend[Join@@Table[Tuples[ssrtrees/@p],{p,Select[mps[m],Length[m]>Length[#1]>1&]}],m];
Table[Sum[Length[Select[ssrtrees[s],FreeQ[#,{_,x_Integer,x_Integer,_}]&]],{s,strnorm[n]}],{n,0,5}]

A330783 Number of set multipartitions (multisets of sets) of strongly normal multisets of size n, where a finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

Original entry on oeis.org

1, 1, 3, 8, 27, 94, 385, 1673, 8079, 41614, 231447, 1364697, 8559575, 56544465, 393485452, 2867908008, 21869757215, 173848026202, 1438593095272, 12360614782433, 110119783919367, 1015289796603359, 9674959683612989, 95147388659652754, 964559157655032720, 10067421615492769230

Offset: 0

Gus Wiseman, Jan 02 2020

nonn

The (weakly) normal version is A116540.

			The a(1) = 1 through a(3) = 8 set multipartitions:
  {{1}}  {{1,2}}    {{1,2,3}}
         {{1},{1}}  {{1},{1,2}}
         {{1},{2}}  {{1},{2,3}}
                    {{2},{1,3}}
                    {{3},{1,2}}
                    {{1},{1},{1}}
                    {{1},{1},{2}}
                    {{1},{2},{3}}
The a(4) = 27 set multipartitions:
  {{1},{1},{1},{1}}  {{1},{1},{1,2}}  {{1},{1,2,3}}  {{1,2,3,4}}
  {{1},{1},{1},{2}}  {{1},{1},{2,3}}  {{1,2},{1,2}}
  {{1},{1},{2},{2}}  {{1},{2},{1,2}}  {{1,2},{1,3}}
  {{1},{1},{2},{3}}  {{1},{2},{1,3}}  {{1},{2,3,4}}
  {{1},{2},{3},{4}}  {{1},{2},{3,4}}  {{1,2},{3,4}}
                     {{1},{3},{1,2}}  {{1,3},{2,4}}
                     {{1},{3},{2,4}}  {{1,4},{2,3}}
                     {{1},{4},{2,3}}  {{2},{1,3,4}}
                     {{2},{3},{1,4}}  {{3},{1,2,4}}
                     {{2},{4},{1,3}}  {{4},{1,2,3}}
                     {{3},{4},{1,2}}

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

Allowing edges to be multisets gives is A035310.
The strict case is A318402.
The constant case is A000005.
The (weakly) normal version is A116540.
Unlabeled set multipartitions are A049311.
Set multipartitions of prime indices are A050320.
Set multipartitions of integer partitions are A089259.
Cf. A001055, A047968, A255906, A269134, A283877, A296119, A317775, A318360, A318362, A330625, A330628.

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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[Join@@mps/@strnorm[n],And@@UnsameQ@@@#&]],{n,0,5}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
D(p, n)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); my(u=WeighT(v)); Vec(1/prod(k=1, n, 1 - u[k]*x^k + O(x*x^n)))/prod(i=1, #v, i^v[i]*v[i]!)}
seq(n)={my(s=0); forpart(p=n, s+=D(p,n)); s} \\ Andrew Howroyd, Dec 30 2020

Terms a(10) and beyond from Andrew Howroyd, Dec 30 2020

cp's OEIS Frontend

A330465 Number of non-isomorphic series-reduced rooted trees whose leaves are multisets with a total of n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A330467 Number of series-reduced rooted trees whose leaves are multisets whose multiset union is a strongly normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

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

A330675 Number of balanced reduced multisystems of maximum depth whose atoms constitute a strongly normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330624 Number of non-isomorphic series-reduced rooted trees whose leaves are sets (not necessarily disjoint) with a total of n elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

A330626 Number of non-isomorphic series/singleton-reduced rooted trees whose leaves are sets (not necessarily disjoint) with a total of n atoms.

Views

Author

Keywords

Comments

Examples

Crossrefs

A330628 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n whose leaves are sets (not necessarily disjoint).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330783 Number of set multipartitions (multisets of sets) of strongly normal multisets of size n, where a finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions