A320173 -id:A320173 - cp's OEIS frontend

A320160 Number of series-reduced balanced rooted trees whose leaves form an integer partition of n.

1, 2, 3, 6, 9, 19, 31, 63, 110, 215, 391, 773, 1451, 2879, 5594, 11173, 22041, 44136, 87631, 175155, 348186, 694013, 1378911, 2743955, 5452833, 10853541, 21610732, 43122952, 86192274, 172753293, 347114772, 699602332, 1414033078, 2866580670, 5826842877, 11874508385

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

Also the number of balanced unlabeled phylogenetic rooted trees with n leaves.

			The a(1) = 1 through a(6) = 19 rooted trees:
  1  2     3      4           5            6
     (11)  (12)   (13)        (14)         (15)
           (111)  (22)        (23)         (24)
                  (112)       (113)        (33)
                  (1111)      (122)        (114)
                  ((11)(11))  (1112)       (123)
                              (11111)      (222)
                              ((11)(12))   (1113)
                              ((11)(111))  (1122)
                                           (11112)
                                           (111111)
                                           ((11)(13))
                                           ((11)(22))
                                           ((12)(12))
                                           ((11)(112))
                                           ((12)(111))
                                           ((11)(1111))
                                           ((111)(111))
                                           ((11)(11)(11))

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

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

Cf. A316624, A320154, A320155, A320169, A320173, A320179.

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]]]];
phy2[labs_]:=If[Length[labs]==1,labs,Union@@Table[Sort/@Tuples[phy2/@ptn],{ptn,Select[mps[Sort[labs]],Length[#1]>1&]}]];
Table[Sum[Length[Select[phy2[ptn],SameQ@@Length/@Position[#,_Integer]&]],{ptn,IntegerPartitions[n]}],{n,8}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=vector(n, n, 1), v=vector(n)); while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 25 2018

Terms a(14) and beyond from Andrew Howroyd, Oct 25 2018

A320154 Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 18, 92, 588, 4328, 35920, 338437, 3654751, 45105744, 625582147, 9539374171, 157031052142, 2757275781918, 51293875591794, 1007329489077804, 20840741773898303, 453654220906310222, 10380640686263467204, 249559854371799622350, 6301679967177242849680

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

Also the number of balanced phylogenetic rooted trees on n distinct labels.

			The a(1) = 1 through a(4) = 18 rooted trees:
  (1)  (12)      (123)        (1234)
       ((1)(2))  ((1)(23))    ((1)(234))
                 ((2)(13))    ((12)(34))
                 ((3)(12))    ((13)(24))
                 ((1)(2)(3))  ((14)(23))
                              ((2)(134))
                              ((3)(124))
                              ((4)(123))
                              ((1)(2)(34))
                              ((1)(3)(24))
                              ((1)(4)(23))
                              ((2)(3)(14))
                              ((2)(4)(13))
                              ((3)(4)(12))
                              ((1)(2)(3)(4))
                              (((1)(2))((3)(4)))
                              (((1)(3))((2)(4)))
                              (((1)(4))((2)(3)))

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

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A292504, A300660, A319312.

Cf. A320155, A320160, A316624, A320169, A320173, A320176, A320179.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
gug[m_]:=Prepend[Join@@Table[Union[Sort/@Tuples[gug/@mtn]],{mtn,Select[sps[m],Length[#]>1&]}],m];
Table[Length[Select[gug[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,9}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; u=EulerT(u); while(u, v+=u; u=EulerT(u)-u); v}
seq(n)={my(M=Mat(vectorv(n,k,b(n,k)))); vector(n, k, sum(i=1, k, binomial(k,i)*(-1)^(k-i)*M[i,k]))} \\ Andrew Howroyd, Oct 26 2018

Terms a(9) and beyond from Andrew Howroyd, Oct 26 2018

A320179 Regular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 3, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 1, 6, 1, 0, 0, 0, 0, 0, 1, 7, 1, 0, 0, 0, 0, 0, 0, 1, 11, 4, 0, 0, 0, 0, 0, 0, 0, 1, 13, 6, 0, 0, 0, 0, 0, 0, 0, 0, 1, 20, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 23, 23, 0, 0, 0

Offset: 1

Gus Wiseman, Oct 07 2018

			Triangle begins:
  1
  0  1
  0  1  0
  0  1  1  0
  0  1  1  0  0
  0  1  3  0  0  0
  0  1  3  0  0  0  0
  0  1  6  1  0  0  0  0
  0  1  7  1  0  0  0  0  0
  0  1 11  4  0  0  0  0  0  0
  0  1 13  6  0  0  0  0  0  0  0
  0  1 20 16  0  0  0  0  0  0  0  0
  0  1 23 23  0  0  0  0  0  0  0  0  0
  0  1 33 46  0  0  0  0  0  0  0  0  0  0
The T(10,3) = 4 rooted trees:
   (((oo)(oo))((oo)(oooo)))
   (((oo)(oo))((ooo)(ooo)))
   (((oo)(ooo))((oo)(ooo)))
  (((oo)(oo))((oo)(oo)(oo)))

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

Row sums are A120803. Third column is A083751. An irregular version is A320221.
Cf. A000669, A001678, A048816, A079500, A119262, A244925, A316655, A319312.
Cf. A316624, A320154, A320155, A320160, A320172, A320173.

qurt[n_]:=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[qurt/@ptn]],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}]];
Table[Length[Select[qurt[n],SameQ[##,k]&@@Length/@Position[#,{}]&]],{n,14},{k,0,n-1}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
T(n)={my(u=vector(n), v=vector(n), h=1); u[1]=1; while(u, v+=u*h; h*=x; u=EulerT(u)-u); vector(n, n, Vecrev(v[n], n))}
{ my(A=T(15)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 09 2020

A320155 Number of series-reduced balanced rooted trees with n labeled leaves.

Original entry on oeis.org

1, 1, 1, 4, 11, 41, 162, 1030, 7205, 55522, 442443, 3810852, 35272030, 351697516, 3735838550, 42719792640, 529195988635, 7128835815387, 103651381499810, 1610812109555323, 26489497655582729, 457497408108551450, 8248899117402701046, 154624472715479106919

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

			The a(1) = 1 through a(5) = 11 rooted trees:
  1  (12)  (123)    (1234)      (12345)
                  ((12)(34))  ((12)(345))
                  ((13)(24))  ((13)(245))
                  ((14)(23))  ((14)(235))
                              ((15)(234))
                              ((23)(145))
                              ((24)(135))
                              ((25)(134))
                              ((34)(125))
                              ((35)(124))
                              ((45)(123))

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

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

Cf. A320154, A320160, A316624, A320169, A320173, A320179.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
phy2[labs_]:=If[Length[labs]==1,labs,Union@@Table[Sort/@Tuples[phy2/@ptn],{ptn,Select[sps[Sort[labs]],Length[#1]>1&]}]];
Table[Length[Select[phy2[Range[n]],SameQ@@Length/@Position[#,_Integer]&]],{n,7}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
b(n,k)={my(u=vector(n), v=vector(n)); u[1]=k; while(u, v+=u; u=EulerT(u)-u); v}
seq(n)={my(M=Mat(vectorv(n,k,b(n,k)))); vector(n, k, sum(i=1, k, binomial(k,i)*(-1)^(k-i)*M[i,k]))} \\ Andrew Howroyd, Oct 26 2018

E.g.f. A(x) satisfies A(x) = x + A(exp(x)-x-1). - Ira M. Gessel, Nov 17 2021

Terms a(10) and beyond from Andrew Howroyd, Oct 26 2018

A320174 Number of series-reduced rooted trees whose leaves are constant integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 3, 6, 19, 55, 200, 713, 2740, 10651, 42637, 173012, 713280, 2972389, 12514188, 53119400, 227140464, 977382586, 4229274235, 18391269922, 80330516578, 352269725526, 1550357247476, 6845517553493, 30316222112019, 134626183784975, 599341552234773, 2674393679352974

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(1) = 1 through a(4) = 19 trees:
  (1)  (2)       (3)            (4)
       (11)      (111)          (22)
       ((1)(1))  ((1)(2))       (1111)
                 ((1)(11))      ((1)(3))
                 ((1)(1)(1))    ((2)(2))
                 ((1)((1)(1)))  ((2)(11))
                                ((1)(111))
                                ((11)(11))
                                ((1)(1)(2))
                                ((1)(1)(11))
                                ((1)((1)(2)))
                                ((2)((1)(1)))
                                ((1)((1)(11)))
                                ((1)(1)(1)(1))
                                ((11)((1)(1)))
                                ((1)((1)(1)(1)))
                                ((1)(1)((1)(1)))
                                (((1)(1))((1)(1)))
                                ((1)((1)((1)(1))))

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

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A317099, A319312, A320173, A320175.

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]]]];
dot[m_]:=If[SameQ@@m,Prepend[#,m],#]&[Join@@Table[Union[Sort/@Tuples[dot/@p]],{p,Select[mps[m],Length[#]>1&]}]];
Table[Length[Join@@Table[dot[m],{m,IntegerPartitions[n]}]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=vector(n)); for(n=1, n, v[n]=numdiv(n) + EulerT(v[1..n])[n]); v} \\ Andrew Howroyd, Oct 25 2018

Terms a(11) and beyond from Andrew Howroyd, Oct 25 2018

A320175 Number of series-reduced rooted trees whose leaves are strict integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 2, 5, 13, 37, 120, 395, 1381, 4931, 18074, 67287, 254387, 972559, 3756315, 14629237, 57395490, 226613217, 899773355, 3590349661, 14390323014, 57907783039, 233867667197, 947601928915, 3851054528838, 15693587686823, 64114744713845, 262543966114921, 1077406218930902

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches.

			The a(1) = 1 through a(4) = 13 trees:
  (1)  (2)       (3)            (4)
       ((1)(1))  (21)           (31)
                 ((1)(2))       ((1)(3))
                 ((1)(1)(1))    ((2)(2))
                 ((1)((1)(1)))  ((1)(21))
                                ((1)(1)(2))
                                ((1)((1)(2)))
                                ((2)((1)(1)))
                                ((1)(1)(1)(1))
                                ((1)((1)(1)(1)))
                                ((1)(1)((1)(1)))
                                (((1)(1))((1)(1)))
                                ((1)((1)((1)(1))))

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

Cf. A000081, A000311, A000669, A001678, A005804, A141268, A292504, A300660, A317099, A319312, A320173, A320174.

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]]]];
sot[m_]:=If[UnsameQ@@m,Prepend[#,m],#]&[Join@@Table[Union[Sort/@Tuples[sot/@p]],{p,Select[mps[m],Length[#]>1&]}]];
Table[Length[Join@@Table[sot[m],{m,IntegerPartitions[n]}]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(p=prod(k=1, n, 1 + x^k + O(x*x^n)), v=vector(n)); for(n=1, n, v[n]=polcoef(p, n) + EulerT(v[1..n])[n]); v} \\ Andrew Howroyd, Oct 25 2018

Terms a(11) and beyond from Andrew Howroyd, Oct 25 2018

A320172 Number of series-reduced balanced rooted identity trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Original entry on oeis.org

1, 2, 5, 9, 19, 38, 79, 163, 352, 750, 1633, 3558, 7783, 17020, 37338, 81920, 180399, 398600, 885101, 1975638, 4435741, 10013855, 22726109, 51807432, 118545425, 272024659, 625488420, 1440067761, 3317675261, 7644488052, 17610215982, 40547552277, 93298838972, 214516498359, 492844378878

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root. In an identity tree, all branches directly under any given node are different.

			The a(1) = 1 through a(5) = 19 rooted identity trees:
  (1)  (2)   (3)        (4)         (5)
       (11)  (21)       (22)        (32)
             (111)      (31)        (41)
             ((1)(2))   (211)       (221)
             ((1)(11))  (1111)      (311)
                        ((1)(3))    (2111)
                        ((1)(21))   (11111)
                        ((2)(11))   ((1)(4))
                        ((1)(111))  ((2)(3))
                                    ((1)(31))
                                    ((1)(22))
                                    ((2)(21))
                                    ((3)(11))
                                    ((1)(211))
                                    ((11)(21))
                                    ((2)(111))
                                    ((1)(1111))
                                    ((11)(111))
                                    ((1)(2)(11))

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

Cf. A000669, A005804, A048816, A079500, A119262, A120803, A141268, A292504, A300660, A319312.

Cf. A320154, A320155, A320160, A320171, A320173, A320177, A320178, A320179.

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]]]];
gig[m_]:=Prepend[Join@@Table[Union[Sort/@Select[Sort/@Tuples[gig/@mtn],UnsameQ@@#&]],{mtn,Select[mps[m],Length[#]>1&]}],m];
Table[Sum[Length[Select[gig[y],SameQ@@Length/@Position[#,_Integer]&]],{y,Sort /@IntegerPartitions[n]}],{n,8}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(n)={my(u=vector(n, n, numbpart(n)), v=vector(n)); while(u, v+=u; u=WeighT(u)-u); v} \\ Andrew Howroyd, Oct 25 2018

Terms a(13) and beyond from Andrew Howroyd, Oct 25 2018

A320221 Irregular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k, (n>=1, min(1,n-1) <= k <= log_2(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 6, 1, 1, 7, 1, 1, 11, 4, 1, 13, 6, 1, 20, 16, 1, 23, 23, 1, 33, 46, 1, 40, 70, 1, 54, 127, 1, 1, 65, 189, 1, 1, 87, 320, 5, 1, 104, 476, 10, 1, 136, 771, 32, 1, 164, 1145, 63, 1, 209, 1795, 154, 1, 252, 2657, 304, 1, 319, 4091, 656

Offset: 1

Gus Wiseman, Oct 07 2018

			Triangle begins:
  1
  1
  1
  1  1
  1  1
  1  3
  1  3
  1  6  1
  1  7  1
  1 11  4
  1 13  6
  1 20 16
  1 23 23
  1 33 46
  1 40 70
The T(11,3) = 6 rooted trees:
   (((oo)(oo))((oo)(ooooo)))
   (((oo)(oo))((ooo)(oooo)))
   (((oo)(ooo))((oo)(oooo)))
   (((oo)(ooo))((ooo)(ooo)))
  (((oo)(oo))((oo)(oo)(ooo)))
  (((oo)(ooo))((oo)(oo)(oo)))

Andrew Howroyd, Table of n, a(n) for n = 1..1154 (rows 1..200)

Row sums are A120803. Second column is A083751. A regular version is A320179.
Cf. A000669, A005804, A048816, A119262, A120803, A141268, A244925, A319312.
Cf. A316624, A320154, A320155, A320160, A320172, A320173.

qurt[n_]:=If[n==1,{{}},Join@@Table[Union[Sort/@Tuples[qurt/@ptn]],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}]];
DeleteCases[Table[Length[Select[qurt[n],SameQ[##,k]&@@Length/@Position[#,{}]&]],{n,10},{k,0,n-1}],0,{2}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
T(n)={my(u=vector(n), v=vector(n), h=1); u[1]=1; while(u, v+=u*h; h*=x; u=EulerT(u)-u); v[1]=x; [Vecrev(p/x) | p<-v]}
{ my(A=T(15)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 09 2020

Terms a(36) and beyond from Andrew Howroyd, Dec 09 2020

Name clarified by Andrew Howroyd, Dec 09 2020

cp's OEIS Frontend

A320160 Number of series-reduced balanced rooted trees whose leaves form an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320154 Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320179 Regular triangle where T(n,k) is the number of unlabeled series-reduced rooted trees with n leaves in which every leaf is at height k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A320155 Number of series-reduced balanced rooted trees with n labeled leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A320174 Number of series-reduced rooted trees whose leaves are constant integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320175 Number of series-reduced rooted trees whose leaves are strict integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A320172 Number of series-reduced balanced rooted identity trees whose leaves are integer partitions whose multiset union is an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs