A320154 -id:A320154 - cp's OEIS frontend

A320173 Number of inequivalent colorings of series-reduced balanced rooted trees with n leaves.

1, 2, 3, 12, 23, 84, 204, 830, 2940, 13397, 58794, 283132, 1377302, 7087164, 37654377, 209943842, 1226495407, 7579549767, 49541194089, 341964495985, 2476907459261, 18703210872343, 146284738788714, 1179199861398539, 9760466433602510, 82758834102114911, 717807201648148643

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.

			Inequivalent representatives of the a(1) = 1 through a(5) = 23 colorings:
  1  (11)  (111)    (1111)      (11111)
     (12)  (112)    (1112)      (11112)
           (123)    (1122)      (11122)
                    (1123)      (11123)
                    (1234)      (11223)
                  ((11)(11))    (11234)
                  ((11)(12))    (12345)
                  ((11)(22))  ((11)(111))
                  ((11)(23))  ((11)(112))
                  ((12)(12))  ((11)(122))
                  ((12)(13))  ((11)(123))
                  ((12)(34))  ((11)(223))
                              ((11)(234))
                              ((12)(111))
                              ((12)(112))
                              ((12)(113))
                              ((12)(123))
                              ((12)(134))
                              ((12)(345))
                              ((13)(122))
                              ((22)(111))
                              ((23)(111))
                              ((23)(114))

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

Cf. A320154, A320155, A320160, A320174, A320175, A320179, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(p=x*sv(1) + O(x*x^n), q=0); while(p, q+=p; p=sEulerT(p)-1-p); q}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 11 2020

Terms a(8) and beyond from Andrew Howroyd, Dec 11 2020

A008826 Triangle of coefficients from fractional iteration of e^x - 1.

Original entry on oeis.org

1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674, 74165, 114345, 56700, 1, 4138, 155477, 1208830, 3394790, 3919860, 1587600, 1, 21145, 1542699, 19800165, 90265560, 182184030, 167310360, 57153600, 1, 115973, 16385857, 335976195, 2338275240, 7342024200, 11471572350, 8719666200, 2571912000

Offset: 2

N. J. A. Sloane, Mar 15 1996

The triangle reflects the Jordan-decomposition of the matrix of Stirling numbers of the second kind. A display of the matrix formula can be found at the Helms link which also explains the generation rule for the A()-numbers in a different way. - Gottfried Helms Apr 19 2014
From Gus Wiseman, Jan 02 2020: (Start)
Also the number of balanced reduced multisystems with atoms {1..n} and depth k. 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. For example, row n = 4 counts the following multisystems:
  {1,2,3,4}  {{1},{2,3,4}}    {{{1}},{{2},{3,4}}}
             {{1,2},{3,4}}    {{{1},{2}},{{3,4}}}
             {{1,2,3},{4}}    {{{1},{2,3}},{{4}}}
             {{1,2,4},{3}}    {{{1,2}},{{3},{4}}}
             {{1,3},{2,4}}    {{{1,2},{3}},{{4}}}
             {{1,3,4},{2}}    {{{1},{2,4}},{{3}}}
             {{1,4},{2,3}}    {{{1,2},{4}},{{3}}}
             {{1},{2},{3,4}}  {{{1}},{{3},{2,4}}}
             {{1},{2,3},{4}}  {{{1},{3}},{{2,4}}}
             {{1,2},{3},{4}}  {{{1,3}},{{2},{4}}}
             {{1},{2,4},{3}}  {{{1,3},{2}},{{4}}}
             {{1,3},{2},{4}}  {{{1},{3,4}},{{2}}}
             {{1,4},{2},{3}}  {{{1,3},{4}},{{2}}}
                              {{{1}},{{4},{2,3}}}
                              {{{1},{4}},{{2,3}}}
                              {{{1,4}},{{2},{3}}}
                              {{{1,4},{2}},{{3}}}
                              {{{1,4},{3}},{{2}}}
(End)
From Harry Richman, Mar 30 2023: (Start)
Equivalently, T(n,k) is the number of length-k chains from minimum to maximum in the lattice of set partitions of {1..n} ordered by refinement. For example, row n = 4 counts the following chains, leaving out the minimum {1|2|3|4} and maximum {1234}:
  (empty)  {12|3|4}  {12|3|4} < {123|4}
           {13|2|4}  {12|3|4} < {124|3}
           {14|2|3}  {12|3|4} < {12|34}
           {1|23|4}  {13|2|4} < {123|4}
           {1|24|3}  {13|2|4} < {134|2}
           {1|2|34}  {13|2|4} < {13|24}
           {123|4}   {14|2|3} < {124|3}
           {124|3}   {14|2|3} < {134|2}
           {134|2}   {14|2|3} < {14|23}
           {1|234}   {1|23|4} < {123|4}
           {12|34}   {1|23|4} < {1|234}
           {13|24}   {1|23|4} < {14|23}
           {14|23}   {1|24|3} < {124|3}
                     {1|24|3} < {1|234}
                     {1|24|3} < {13|24}
                     {1|2|34} < {134|2}
                     {1|2|34} < {1|234}
                     {1|2|34} < {12|34}
(End)
Also the number of cells of dimension k in the fine subdivision of the Bergman complex of the complete graph on n vertices. - Harry Richman, Mar 30 2023

			Triangle starts:
  1;
  1,    3;
  1,   13,     18;
  1,   50,    205,     180;
  1,  201,   1865,    4245,    2700;
  1,  875,  16674,   74165,  114345,   56700;
  1, 4138, 155477, 1208830, 3394790, 3919860, 1587600;
  ...
The f-vector of (the fine subdivision of) the Bergman complex of the complete graph K_3 is (1, 3). The f-vector of the Bergman complex of K_4 is (1, 13, 18). - _Harry Richman_, Mar 30 2023

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.

Alois P. Heinz, Rows n = 2..150, flattened (first 19 rows from Vincenzo Librandi)
Gottfried Helms, How this expression leads to the given sequence, MathOverflow.
Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96 (2006), 38-49.

Row sums are A005121.
Alternating row sums are signed factorials A133942(n-1).
Column k = 2 is A008827.
Diagonal k = n - 1 is A006472.
Diagonal k = n - 2 is A059355.
Row n equals row 2^n of A330727.
Cf. A000110, A000111, A000258, A002846, A005121, A008277, A306186, A317176, A318813, A320154, A330667, A330679, A330784.

b:= proc(n) option remember; expand(`if`(n=1, 1,
      add(Stirling2(n, j)*b(j)*x, j=0..n-1)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1..n-1), n=2..10);  # Alois P. Heinz, Mar 31 2023

a[n_, x_] := Sum[ StirlingS2[n, k]*a[k, x]*x, {k, 0, n-1}]; a[1, ] = 1; Table[ CoefficientList[ a[n, x], x] // Rest, {n, 2, 10}] // Flatten (* _Jean-François Alcover, Dec 11 2012, after Vladeta Jovovic *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
tots[m_]:=Prepend[Join@@Table[tots[p],{p,Select[sps[m],1Gus Wiseman, Jan 02 2020 *)

G.f. A(n;x) for n-th row satisfies A(n;x) = Sum_{k=0..n-1} Stirling2(n, k)*A(k;x)*x, A(1;x) = 1. - Vladeta Jovovic, Jan 02 2004

Sum_{k=1..n-1} (-1)^k*T(n,k) = (-1)^(n-1)*(n-1)! = A133942(n-1). - Geoffrey Critzer, Sep 06 2020

More terms from Vladeta Jovovic, Jan 02 2004

A330668 Number of non-isomorphic balanced reduced multisystems of weight n whose leaves (which are multisets of atoms) are all sets.

Original entry on oeis.org

1, 1, 1, 3, 22, 204, 2953

Offset: 0

Gus Wiseman, Dec 27 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(1) = 1 through a(4) = 22 multisystems:
  {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},{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 case with all atoms different is A318813.
The version where the leaves are multisets is A330474.
The tree version is A330626.
The maximum-depth case is A330677.
Unlabeled series-reduced rooted trees whose leaves are sets are A330624.
Cf. A000311, A004114, A005121, A005804, A007716, A048816, A141268, A283877, A306186, A318812, A320154, A330470, A330628, A330663.

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

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

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

A320173 Number of inequivalent colorings of series-reduced balanced rooted trees with n leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A008826 Triangle of coefficients from fractional iteration of e^x - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A330668 Number of non-isomorphic balanced reduced multisystems of weight n whose leaves (which are multisets of atoms) are all sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions