A000311 -id:A000311 - cp's OEIS frontend

A319369 Number of series-reduced rooted trees with n leaves of n colors.

1, 3, 28, 430, 9376, 269675, 9632960, 411395268, 20445999734, 1159248404721, 73846864163348, 5221802726902476, 405858598184643930, 34392275731729465799, 3155760058245300968416, 311720334688779807141832, 32980137195294216968253900, 3720954854814866649904474180

Offset: 1

Andrew Howroyd, Sep 17 2018

nonn

Not all of the n colors need to be used.

Alois P. Heinz, Table of n, a(n) for n = 1..340
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

Main diagonal of A319254.

Cf. A000311 (1 leaf of each color), A316651.

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)):
a:= n-> A(n$2):
seq(a(n), n=1..20);  # 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]];
a[n_] := A[n, n];
a /@ Range[1, 20] (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
a(n)={my(v=[n]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v[n]}

a(n) ~ c * d^n * n^(n - 3/2), where d = 1/(2*log(2) - 1) = 2.588699449562089830805384431942090... and c = 0.2580000331300831455241033648... - Vaclav Kotesovec, Sep 18 2019, updated Mar 16 2024

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

A330667 Irregular triangle read by rows where T(n,k) is the number of balanced reduced multisystems of depth k whose atoms are the prime indices of n.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 2, 0, 1, 1, 0, 1, 0, 1, 3, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 1, 1, 5, 5, 0, 1, 0, 1, 0, 1, 1, 0, 1, 2, 0, 1, 1, 3, 0, 1, 1, 5, 9, 5, 0, 1, 0, 1, 0, 1, 0, 1, 7, 7, 0, 1, 1, 0, 1, 0, 1, 5, 5, 0, 1, 1, 3

Offset: 1

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.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			Triangle begins:
  {}
  1
  1
  1 0
  1
  1 0
  1
  1 1 0
  1 0
  1 0
  1
  1 2 0
  1
  1 0
  1 0
  1 3 2 0
  1
  1 2 0
  1
  1 2 0
Row n = 84 counts the following multisystems (commas elided):
  {1124}  {{1}{124}}    {{{1}}{{1}{24}}}
          {{11}{24}}    {{{11}}{{2}{4}}}
          {{12}{14}}    {{{1}}{{2}{14}}}
          {{2}{114}}    {{{12}}{{1}{4}}}
          {{4}{112}}    {{{1}}{{4}{12}}}
          {{1}{1}{24}}  {{{14}}{{1}{2}}}
          {{1}{2}{14}}  {{{2}}{{1}{14}}}
          {{1}{4}{12}}  {{{2}}{{4}{11}}}
          {{2}{4}{11}}  {{{24}}{{1}{1}}}
                        {{{4}}{{1}{12}}}
                        {{{4}}{{2}{11}}}

Row lengths are A001222.
Row sums are A318812.
The last nonzero term of row n is A330665(n).
Column k = 2 is 0 if n is prime; otherwise it is A001055(n) - 2.
Cf. A000311, A000669, A001678, A005121, A008827, A213427, A317145, A318846, A330474, A330475, A330655, A330666.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
totfac[n_,k_]:=If[k==1,1,Sum[totfac[Times@@Prime/@f,k-1],{f,Select[facs[n],1

A005805 Number of phylogenetic trees with n labels.

Original entry on oeis.org

1, 2, 5, 18, 107, 1008, 13113, 214238, 4182487, 94747196, 2440784645, 70431957258, 2249856084803, 78802876705608, 3002702793753489, 123649410977736950, 5471808106109912815, 258948617502187143188, 13049542794706527317597, 697673361673877090147490

Offset: 1

N. J. A. Sloane

Stirling transform of [ 1, 1, 1, 4, 26, 236, ... ] = A000311(n-1).

Series-reduced trees where each leaf is a nonempty subset of the set of n labels. [Christian G. Bower, Dec 15 1999]

Foulds, L. R.; Robinson, R. W. Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..381 (first 100 terms from Vincenzo Librandi)
N. J. A. Sloane, Transforms
Index entries for sequences related to trees

Cf. A000311, A005804.

stirtr:= proc(p) proc(n) add(p(k) *Stirling2(n,k), k=0..n) end end: b:= proc(n) option remember; if n<=1 then n elif n=2 then 1 else (n+1) *b(n-1) +2*add(binomial(n-1, k) *b(k) *b(n-k), k=2..n-2) fi end:
a:= stirtr(n->`if`(n<2,1, b(n-1))):
seq(a(n), n=1..20);  # Alois P. Heinz, Sep 15 2008

max = 18; a311 = CoefficientList[ InverseSeries[ Series[ 1 + 2x - E^x, {x, 0, max}], x], x]*Range[0, max]!; b[1] = 1; b[k_] := a311[[k]]; a[n_] := Sum[ b[k]*StirlingS2[n, k], {k, 1, n}]; Table[ a[n], {n, 1, max}] (* Jean-François Alcover, Feb 22 2012 *)

From Vaclav Kotesovec, Nov 16 2021: (Start)
E.g.f.: exp(2*x)/4 - (1 + LambertW(-exp(exp(x)/2 - 1)/2))^2.
a(n) ~ 2 * log(2)^(3/2) * n^(n-2) / (exp(n) * (log(2) + log(log(2)))^(n - 3/2)).
(End)

More terms from Christian G. Bower, Dec 15 1999

A058478 Total number of interior nodes in all essentially series series-parallel networks with n labeled edges, multiple edges allowed.

Original entry on oeis.org

0, 0, 1, 5, 46, 534, 7596, 127756, 2479856, 54560512, 1341716960, 36468949824, 1085680795200, 35131589529152, 1227777836217856, 46086892351150592, 1849266301464495616, 78990342571085637120, 3578513340735623076864

Offset: 0

N. J. A. Sloane, Dec 20 2000

nonn

J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226 (the e.g.f. I_S(x)).

Index entries for sequences mentioned in Moon (1987)

A058480 = A058478 + A058479.

E.g.f. = (xP'-P)/(1+U), where P = e.g.f. for A000311 and U that for A006351.

A064060 Number of connected, homeomorphically irreducible (also called series-reduced) trees with n >= 2 labeled leaves (numbers in nondecreasing order).

Original entry on oeis.org

1, 1, 1, 3, 1, 10, 15, 1, 10, 15, 15, 45, 60, 90, 1, 21, 35, 70, 105, 105, 105, 105, 210, 315, 420, 630, 630, 1, 28, 35, 56, 105, 168, 210, 210, 280, 280, 280, 315, 420, 420, 560, 560, 840, 840, 840, 1260, 1260

Offset: 2

Wolfdieter Lang and Christoph Mayer (Christoph.Mayer(AT)dlr.de), Sep 13 2001

The number of entries of row n of this array is A007827(n), n >= 2.

With v the total number of nodes (vertices), e the number of edges (links), n >= 2 the number of edges ending in a degree 1 node (leaves), i the number of edges which end in nodes with degree >=3 (internal edges) and v_{d} the number of nodes of degree d=1,3,4,... one has: v = e+1 = n + Sum_{d>=3}v_{d}, i = e-n, Sum_{d>=3}d*v_{d} = 2(v-1)-n.

			Irregular array starts:
{1};
{1};
{1, 3};
{1, 10, 15};
{1, 10, 15, 15, 15, 45, 60, 90};
{1, 21, 35, 70, 105, 105, 105, 105, 210, 315, 420, 630, 630};
{1, 28, 35, 56, 105, 168, 210, 210, 280, 280, 280, 315, 420, 420, 560, 560, 840, 840, 840, 1260, 1260, 1680, 1680, 1680, 1680, 2520, 2520, 2520, 2520, 3360, 5040, 5040};
...

Ch. Mayer, Illustration
Index entries for sequences related to trees

The row sums give A000311(n-1), n >= 2. Cf. A007827.

A176740 Inversion of e.g.f. formal power series. Partition array in Abramowitz-Stegun (A-St) order.

Original entry on oeis.org

-1, -1, 3, -1, 10, -15, -1, 15, 10, -105, 105, -1, 21, 35, -210, -280, 1260, -945, -1, 28, 56, 35, -378, -1260, -280, 3150, 6300, -17325, 10395, -1, 36, 84, 126, -630, -2520, -1575, -2100, 6930, 34650, 15400, -51975, -138600, 270270, -135135, -1, 45, 120, 210, 126, -990, -4620, -6930, -4620, -5775

Offset: 0

Wolfdieter Lang, Jul 14 2010

Compare with A134685 which uses a different order with fewer entries.
For the inversion (aka reversion) of o.g.f. formal power series see A111785, and also A133437.
The sequence of row lengths of this array is p(n)=A000041(n) (number of partitions of n).
The unsigned triangle, with entries for like parts number m summed, is A134991 (2-associated Stirling numers of the second kind).
The row sums are A133942(n) = ((-1)^n) * n!, and the row sums of the unsigned array give A000311(n+1) (Schroeder's fourth problem). These sums coincide with those of the triangle A134991.
The signed a(n,k) numbers, k=1,...,p(n)=A000041(n), derive from the multinomial M_3 numbers A036040 (see also the W. Lang link there), namely, if the k-th partition of n in A-St order has exponents (enk[1],...,enk[n]) then a(n,k) = ((-1)^m)*M3(n+m, (ehatnk[1],...,ehatnk[n+m])) with m the number of parts, i.e., m:=Sum_{j=1..n} enk[j], and M3(n+m, (ehatnk[1],...,ehatnk[n+m])):=(n+m)!/(Product_{j=1..n+m} j!^ehatnk[j]*ehatnk[j]!), where the n+m exponents ehatnk are ehatnk[1]:=0, (ehatnk[2],...,ehatnk[n+1]) := (enk[1],...,enk[n]), and (ehatnk[n+1],...,ehatnk[n+m]):=(0,...,0) (i.e., m-1 zeros).
The compositional inverse of the formal power series of the e.g.f. type g(x) = Sum_{j>=1} g[j]*(x^j)/j! is f = g^[-1] with f(y) = Sum_{n>=1} f[n]*(y^n)/n!, and f[n] = fhat[n]/g[1]^(2*n-1) with fhat[1]=1 (f[1] = 1/g[1]) and f[n+1] = Sum_{k=1..p(n)} a(n,k)*g(n,k), n >= 1, where p(n) = A000041(n) (number of partitions of n), and g(n,k) is the monomial in coefficients of g(x) corresponding to the k-th partition of 2*n with n parts in A-St order. For details and a remark on the Faa di Bruno Hopf algebra see the W. Lang link.

			  -1;
  -1,  3;
  -1, 10, -15;
  -1, 15,  10, -105,  105;
  -1, 21,  35, -210, -280, 1260, -945;
...
a(4,4): 4th partition of 4 has exponents (2,1,0,0) with m=3, and the derived exponents ehatm are (0,2,1,0,0,0,0) with one leading and 2 extra trailing zeros. (4+3)!/(2!^2*2!*3!^1*1!) = 105, hence a(4,4) = ((-1)^3)*105 = -105.
fhat[4] = -1*g[1]^2*g[4] +10*g[1]*g[2]*g[3] - 15*g[2]^3 (n=3: 3 parts partitions of 6 for the g-monomials in A-St order).

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 831-2.
R. Aldrovandi, Special Matrices of Mathematical Physics, World Scientific, 2001, p. 175, eq. (13.84).
Ch. A. Charalambides, Enumerative Combinatorics, Chapman &Hall/CRC, 2002, p. 437, eq. (11.43) with p. 428. eq. (11.29).

W. P. Johnson, Combinatorics of Higher Derivatives of Inverses, Amer. Math. Monthly 109 (3), (2002), 273-277
Wolfdieter Lang, E.g.f. Lagrange inversion partition array.

See the fhat[n] formula explained above, and the W. Lang link for more details.

A320293 Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n with no 1's.

Original entry on oeis.org

0, 1, 1, 3, 3, 9, 11, 30, 45, 112, 195, 475, 901, 2136, 4349, 10156, 21565, 50003, 109325, 252761, 563785, 1303296, 2948555, 6826494, 15604053, 36210591, 83415487, 194094257, 449813607, 1049555795, 2444027917, 5718195984, 13367881473, 31357008065, 73546933115

Offset: 1

Gus Wiseman, Oct 09 2018

nonn

Also phylogenetic trees on integer partitions of n with no 1's.

			The a(2) = 1 through a(7) = 11 trees:
  (2)  (3)  (4)       (5)       (6)            (7)
            (22)      (32)      (33)           (43)
            ((2)(2))  ((2)(3))  (42)           (52)
                                (222)          (322)
                                ((2)(4))       ((2)(5))
                                ((3)(3))       ((3)(4))
                                ((2)(22))      ((2)(23))
                                ((2)(2)(2))    ((3)(22))
                                ((2)((2)(2)))  ((2)(2)(3))
                                               ((2)((2)(3)))
                                               ((3)((2)(2)))

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

Cf. A000045, A000311, A000669, A002865, A141268, A292504, A300660, A304967, A319312, A320289, A320294, A320295, A320296.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(p=1/prod(k=2, 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(23) and beyond from Andrew Howroyd, Oct 25 2018

A058561 A 3-way generalization of series-parallel networks with n labeled edges.

Original entry on oeis.org

0, 1, 3, 12, 78, 708, 8256, 117624, 1980096, 38456736, 846413472, 20819693568, 565998548352, 16852047061632, 545372109629184, 19061178127458816, 715541912895773184, 28713061759257037824, 1226513716981332031488

Offset: 0

N. J. A. Sloane, Dec 26 2000

nonn

Cf. A058534, A000311, A006351.

spec := [ N, {N=Union(Z,S,P,Q), S=Set(Union(Z,P),card>=2), P=Set(Union(Z,Q),card>=2), Q=Set(Union(Z,S),card>=2)}, labeled ]; [seq(combstruct[count](spec,size=n), n=0..40)]; # N = A058561, S=A000311

A119649 a(0)=0, a(1)=1; for n >= 1, a(n+1) = (n+2)a(n) + 2Sum_{k=2..n-1} binomial(n, k)a(k)a(n-k+1).

Original entry on oeis.org

0, 1, 3, 12, 114, 1404, 22968, 456408, 10762992, 292851648, 9038285280, 311858347968, 11896746473088, 497156854363776, 22586083785232128, 1108320770197398528, 58420751739908940288, 3292054745517600648192, 197491129333671926863872, 12566253138627465234487296

Offset: 0

N. J. A. Sloane, Jul 30 2006

nonn

The recurrence for A000311, with slightly different initial conditions.

T. D. Noe, Table of n, a(n) for n = 0..100

Cf. A000311.

M:=50; a:=array(0..100); a[0]:=0; a[1]:=1; lprint(0,a[0]); lprint(1,a[1]); for n from 1 to M do a[n+1]:=(n+2)*a[n]+2*add(binomial(n,k)*a[k]*a[n-k+1],k=2..n-1); lprint(n+1,a[n+1]); od:

cp's OEIS Frontend

A319369 Number of series-reduced rooted trees with n leaves of n colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A330667 Irregular triangle read by rows where T(n,k) is the number of balanced reduced multisystems of depth k whose atoms are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A005805 Number of phylogenetic trees with n labels.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A058478 Total number of interior nodes in all essentially series series-parallel networks with n labeled edges, multiple edges allowed.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A064060 Number of connected, homeomorphically irreducible (also called series-reduced) trees with n >= 2 labeled leaves (numbers in nondecreasing order).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A176740 Inversion of e.g.f. formal power series. Partition array in Abramowitz-Stegun (A-St) order.

Views

Author

Keywords

Comments

Examples

References

Links

Formula

A320293 Number of series-reduced rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n with no 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A119649 a(0)=0, a(1)=1; for n >= 1, a(n+1) = (n+2)a(n) + 2Sum_{k=2..n-1} binomial(n, k)a(k)a(n-k+1).