A330465 -id:A330465 - cp's OEIS frontend

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

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.

A331678 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 3, 6, 18, 44, 149, 450, 1573, 5352, 19283, 69483, 257206

Offset: 1

Gus Wiseman, Jan 25 2020

Lone-child-avoiding means there are no unary branchings. Locally disjoint means no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex.

			The a(1) = 1 through a(4) = 18 trees:
  (1)  (2)       (3)            (4)
       (11)      (12)           (13)
       ((1)(1))  (111)          (22)
                 ((1)(2))       (112)
                 ((1)(1)(1))    (1111)
                 ((1)((1)(1)))  ((1)(3))
                                ((2)(2))
                                ((2)(11))
                                ((11)(11))
                                ((1)(1)(2))
                                ((1)((1)(2)))
                                ((2)((1)(1)))
                                ((1)(1)(1)(1))
                                ((11)((1)(1)))
                                ((1)((1)(1)(1)))
                                ((1)(1)((1)(1)))
                                (((1)(1))((1)(1)))
                                ((1)((1)((1)(1))))

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

The case where all leaves are singletons is A316696.
The case where all leaves are (1) is A316697.
The non-locally disjoint version is A319312.
The case with all atoms equal to 1 is A331679.
The identity tree case is A331686.
Cf. A000081, A000669, A001678, A005804, A060356, A141268, A196545, A300660, A316471, A316694, A316495, A330465, A331680, A331687.

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]]]];
disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
mpti[m_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[mpti/@p]],disjointQ],{p,Select[mps[m],Length[#]>1&]}],m];
Table[Sum[Length[mpti[m]],{m,Sort/@IntegerPartitions[n]}],{n,8}]

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

Original entry on oeis.org

1, 1, 1, 2, 6, 4, 5, 30, 51, 26, 12, 146, 474, 576, 236, 33, 719, 3950, 8572, 8060, 2752, 90, 3590, 31464, 108416, 175380, 134136, 39208, 261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032, 766, 94648, 1908858, 14047288, 49885320, 95715728, 101799712, 56555904, 12818912

Offset: 1

Andrew Howroyd, Sep 17 2018

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     6,      4;
    5,    30,     51,      26;
   12,   146,    474,     576,     236;
   33,   719,   3950,    8572,    8060,   2752;
   90,  3590,  31464,  108416,  175380,  134136,   39208;
  261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
  ...
From _Gus Wiseman_, Dec 31 2020: (Start)
The 12 trees counted by row n = 3:
  (111)    (112)    (123)
  (1(11))  (122)    (1(23))
           (1(12))  (2(13))
           (1(22))  (3(12))
           (2(11))
           (2(12))
(End)

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

Columns k=1..2 are A000669, A319377.
Main diagonal is A000311.
Row sums are A316651.
Cf. A141610, A242249, A255517, A256064, A256068, A319254, A319541, A326396.
The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465.
Lone-child-avoiding rooted trees are counted by A001678 (shifted left once).
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000014, A000081, A000169, A005804, A206429, A330951.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 18 2018

b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)
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]]]];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],1Gus Wiseman, Dec 31 2020 *)

\\ here R(n,k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[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]))}

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).

Sum_{k=1..n} k * T(n,k) = A326396(n). - Alois P. Heinz, Sep 11 2019

A330471 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.

Original entry on oeis.org

1, 1, 2, 9, 69, 623, 7803, 110476, 1907428

Offset: 0

Gus Wiseman, Dec 23 2019

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

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). This is a multiset generalization of singleton-reduced phylogenetic trees (A000311).

			The a(0) = 1 through a(3) = 9 trees:
  ()  (1)  (11)  (111)
           (12)  (112)
                 (123)
                 ((1)(11))
                 ((1)(12))
                 ((1)(23))
                 ((2)(11))
                 ((2)(13))
                 ((3)(12))
The a(4) = 69 trees, with singleton leaves (x) replaced by just x:
  (1111)      (1112)      (1122)      (1123)      (1234)
  (1(111))    (1(112))    (1(122))    (1(123))    (1(234))
  (11(11))    (11(12))    (11(22))    (11(23))    (12(34))
  ((11)(11))  (12(11))    (12(12))    (12(13))    (13(24))
  (1(1(11)))  (2(111))    (2(112))    (13(12))    (14(23))
              ((11)(12))  (22(11))    (2(113))    (2(134))
              (1(1(12)))  ((11)(22))  (23(11))    (23(14))
              (1(2(11)))  (1(1(22)))  (3(112))    (24(13))
              (2(1(11)))  ((12)(12))  ((11)(23))  (3(124))
                          (1(2(12)))  (1(1(23)))  (34(12))
                          (2(1(12)))  ((12)(13))  (4(123))
                          (2(2(11)))  (1(2(13)))  ((12)(34))
                                      (1(3(12)))  (1(2(34)))
                                      (2(1(13)))  ((13)(24))
                                      (2(3(11)))  (1(3(24)))
                                      (3(1(12)))  ((14)(23))
                                      (3(2(11)))  (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 case with all atoms different is A000311.
The case with all atoms equal is A196545.
The orderless version is A316652.
The unlabeled version is A330470.
The case where the leaves are sets is A330628.
The version for just normal (not strongly normal) is A330654.
Cf. A000669, A004114, A005121, A005804, A281118, A318812, A318848, A319312, A330465, A330467, A330475.

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];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],Length[#]>1&&Length[#]

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

A330677 Number of non-isomorphic balanced reduced multisystems of weight n and maximum depth whose leaves (which are multisets of atoms) are sets.

Original entry on oeis.org

1, 1, 1, 2, 11, 81, 859

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. The weight of an atom is 1, while the weight of a multiset is the sum of weights of its elements.

			Non-isomorphic representatives of the a(0) = 1 through a(4) = 11 multisystems:
  {}  {1}  {1,2}  {{1},{1,2}}  {{{1}},{{1},{1,2}}}
                  {{1},{2,3}}  {{{1}},{{1},{2,3}}}
                               {{{1,2}},{{1},{1}}}
                               {{{1}},{{2},{1,2}}}
                               {{{1,2}},{{1},{2}}}
                               {{{1}},{{2},{1,3}}}
                               {{{1,2}},{{1},{3}}}
                               {{{1}},{{2},{3,4}}}
                               {{{1,2}},{{3},{4}}}
                               {{{2}},{{1},{1,3}}}
                               {{{2,3}},{{1},{1}}}

The version with all distinct atoms is A000111.
Non-isomorphic set multipartitions are A049311.
The (non-maximal) tree version is A330626.
Allowing leaves to be multisets gives A330663.
The case with prescribed degrees is A330664.
The version allowing all depths is A330668.
Cf. A000669, A001678, A004114, A005121, A007716, A141268, A283877, A306186, A330465, A330470, A330624.

A330627 Number of non-isomorphic phylogenetic trees with n nodes.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 4, 5, 9, 14, 24, 39, 69, 116, 205, 357, 632, 1118, 2001, 3576, 6445, 11627, 21080, 38293, 69819, 127539, 233644, 428825, 788832, 1453589, 2683602, 4962167, 9190155, 17044522, 31655676, 58866237, 109600849, 204293047, 381212823, 712073862

Offset: 1

Gus Wiseman, Dec 28 2019

nonn

A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) sets. Each branching as well as each element of each leaf contributes to the number of nodes.

			Non-isomorphic representatives of the a(2) = 1 through a(9) = 9 trees (commas and outer brackets elided):
  1  12  123  1234    12345    123456     1234567      12345678
              (1)(2)  (1)(23)  (1)(234)   (1)(2345)    (1)(23456)
                               (12)(34)   (12)(345)    (12)(3456)
                               (1)(2)(3)  (1)(2)(34)   (123)(456)
                                          (1)((2)(3))  (1)(2)(345)
                                                       (1)(23)(45)
                                                       (1)((2)(34))
                                                       (1)(2)(3)(4)
                                                       (12)((3)(4))

Andrew Howroyd, Table of n, a(n) for n = 1..500

Phylogenetic trees by number of labels are A005804, with unlabeled version A141268.
Balanced phylogenetic trees are A320154.
Cf. A000311, A000669, A001678, A004114, A005121, A007716, A048816, A060356, A330465, A330467, A330469.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[0]); for(n=1, n-1, v=concat(v, EulerT(v)[n] - v[n] + 1)); v} \\ Andrew Howroyd, Jan 02 2021

G.f.: A(x) satisfies A(x) = x*(1/(1-x) - A(x) - 2 + exp(Sum_{k>0} A(x^k)/k)). - Andrew Howroyd, Jan 02 2021

Terms a(11) and beyond from Andrew Howroyd, Jan 02 2021

A331685 Number of tree-factorizations of Heinz numbers of integer partitions of n.

Original entry on oeis.org

1, 3, 7, 23, 69, 261, 943, 3815, 15107, 63219, 262791, 1130953, 4838813, 21185125, 92593943, 411160627, 1823656199, 8186105099, 36728532951, 166310761655

Offset: 1

Gus Wiseman, Jan 31 2020

A tree-factorization of n > 1 is either (case 1) the number n itself, or (case 2) a sequence of two or more tree-factorizations, one of each part of a weakly increasing factorization of n into factors > 1.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The a(1) = 1 through a(4) = 23 tree-factorizations:
  2  3      5          7
     4      6          9
     (2*2)  8          10
            (2*3)      12
            (2*4)      16
            (2*2*2)    (2*5)
            (2*(2*2))  (2*6)
                       (2*8)
                       (3*3)
                       (3*4)
                       (4*4)
                       (2*2*3)
                       (2*2*4)
                       (2*2*2*2)
                       (2*(2*3))
                       ((2*2)*4)
                       (2*(2*4))
                       (3*(2*2))
                       (4*(2*2))
                       (2*(2*2*2))
                       (2*2*(2*2))
                       ((2*2)*(2*2))
                       (2*(2*(2*2)))

The orderless version is A319312.
Factorizations are A001055.
P-trees are A196545.
Twice-factorizations are A281113.
Tree-factorizations are A281118.
Enriched p-trees are A289501.
Cf. A000081 A000669, A000720, A001678, A005804, A056239, A112798, A141268, A273873, A330465.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
physemi[n_]:=Prepend[Join@@Table[Tuples[physemi/@f],{f,Select[facs[n],Length[#]>1&]}],n];
Table[Sum[Length[physemi[Times@@Prime/@m]],{m,IntegerPartitions[n]}],{n,8}]

\\ here TF(n) is n terms of A281118 as vector.
TF(n)={my(v=vector(n), w=vector(n)); w[1]=v[1]=1; for(k=2, n, w[k]=v[k]+1; forstep(j=n\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j] += w[k]^e*v[i]))); w}
a(n)={my(v=[prod(i=1, #p, prime(p[i])) | p<-partitions(n)], tf=TF(vecmax(v))); sum(i=1, #v, tf[v[i]])} \\ Andrew Howroyd, Dec 09 2020

a(n) = Sum_i A281118(A215366(n,i)).

a(13)-a(20) from Andrew Howroyd, Dec 09 2020

cp's OEIS Frontend

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

A331678 Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A330471 Number of series/singleton-reduced rooted trees on strongly normal multisets of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A330677 Number of non-isomorphic balanced reduced multisystems of weight n and maximum depth whose leaves (which are multisets of atoms) are sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

A330627 Number of non-isomorphic phylogenetic trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A331685 Number of tree-factorizations of Heinz numbers of integer partitions of n.

Views

Author

Keywords

Comments