A060356 -id:A060356 - cp's OEIS frontend

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

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

A376106 Expansion of e.g.f. LambertW(x / (1 - 2*x)).

Original entry on oeis.org

0, 1, 2, 9, 56, 465, 4764, 58345, 830192, 13466817, 245254580, 4955259441, 109995693576, 2661003245329, 69682488950060, 1963774182830265, 59261538449833184, 1906643335934717697, 65149411890671521380, 2356212733788818122561, 89920484394446094721400

Offset: 0

Seiichi Manyama, Sep 10 2024

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..400
Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A060356, A376107.

Cf. A376100.

nmax=20; CoefficientList[InverseSeries[Series[x / (2*x + E^(-x)), {x, 0, nmax}], x], x] * Range[0, nmax]! (* Vaclav Kotesovec, Sep 20 2024 *)

my(N=30, x='x+O('x^N)); concat(0, Vec(serlaplace(lambertw(x/(1-2*x)))))

a(n) = n!*sum(k=1, n, 2^(n-k)*(-k)^(k-1)*binomial(n-1, k-1)/k!);

E.g.f. A(x) satisfies A(x) = x * (2*A(x) + exp(-A(x))).
E.g.f.: Series_Reversion( x / (2*x + exp(-x)) ).
a(n) = n! * Sum_{k=1..n} 2^(n-k) * (-k)^(k-1) * binomial(n-1,k-1)/k!.

A231602 Triangular array read by rows: T(n,k) is the number of rooted labeled trees on n nodes that have exactly k nodes with outdegree = 1, n>=1, 0<=k<=n-1.

Original entry on oeis.org

1, 0, 2, 3, 0, 6, 4, 36, 0, 24, 65, 80, 360, 0, 120, 306, 1950, 1200, 3600, 0, 720, 4207, 12852, 40950, 16800, 37800, 0, 5040, 38424, 235592, 359856, 764400, 235200, 423360, 0, 40320, 573057, 2766528, 8481312, 8636544, 13759200, 3386880, 5080320, 0, 362880

Offset: 1

Geoffrey Critzer, Nov 11 2013

T(n,k) is also the number of functions f:{1,2,...,n-1}->{1,2,...,n} that have exactly k elements whose preimage has cardinality = 1.
T(n,n-1) = n! = A000142(n).
Column k = 0 = A060356(n).
Row sums = n^(n-1) = A000169(n).
Refinement given by A248120. Sum coefficients of the partition polynomials with h_1 = (1') = t and all other h_n = (n') = 1 to obtain this entry. - Tom Copeland, Feb 01 2016

			1;
0, 2;
3, 0, 6;
4, 36, 0, 24;
65, 80, 360, 0, 120;
306, 1950, 1200, 3600, 0, 720;
4207, 12852, 40950, 16800, 37800, 0, 5040;
38424, 235592, 359856, 764400, 235200, 423360, 0, 40320;
....0..........0........
....|........./ \.......
....0........0...0......
.../ \.......|..........
..0   0......0..........
T(4,1) = 36.  Both of these graphs on 4 nodes have exactly 1 node that has outdegree = 1.  There are 12 + 24 = 36 labelings.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A055302, A206823.

Cf. A248120.

with(combinat): C:= binomial:
b:= proc(t, i, u) option remember; `if`(t=0, 1,
      `if`(i<2, 0, b(t, i-1, u) +add(multinomial(t, t-i*j, i$j)
      *b(t-i*j, i-1, u-j)*u!/(u-j)!/j!, j=1..t/i)))
    end:
T:= (n, k)-> C(n, k)*C(n-1, k)*k! *b(n-1-k$2, n-k):
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Nov 12 2013

nn=8;Table[Table[Drop[Range[0,nn]!CoefficientList[Series[-ProductLog[x/(-1-x+x y)],{x,0,nn}],{x,y}],1][[r,c]],{c,1,r}],{r,1,nn}]//Grid

E.g.f. satisfies A(x,y) = y*x*A(x,y) + x*( exp(A(x,y)) - A(x,y) ).

A305276 Expansion of e.g.f. 1/(1 + LambertW(-x/(1 - x))).

Original entry on oeis.org

1, 1, 6, 57, 748, 12565, 257526, 6232765, 173980920, 5502613833, 194477548330, 7596028355641, 324920533473108, 15106155118606045, 758463525318426942, 40901033617318501845, 2357682497456804486896, 144670077586483815863569, 9414952083720893890165842, 647715776085173413399687633

Offset: 0

Ilya Gutkovskiy, Aug 18 2018

nonn

Lah transform of A000312.

Robert Israel, Table of n, a(n) for n = 0..369
N. J. A. Sloane, Transforms

Cf. A000312, A052871, A060356, A305304.

S:= series(1/(1+LambertW(-x/(1-x))),x,51):
seq(coeff(S,x,j)*j!,j=0..50); # Robert Israel, Aug 19 2018

nmax = 19; CoefficientList[Series[1/(1 + LambertW[-x/(1 - x)]), {x, 0, nmax}], x] Range[0, nmax]!
Join[{1}, Table[Sum[Binomial[n - 1, k - 1] k^k n!/k!, {k, n}], {n, 19}]]

a(n) = Sum_{k=0..n} binomial(n-1,k-1)*k^k*n!/k!.

a(n) ~ n^n * (1 + exp(1))^(n - 1/2) / exp(n - 1/2). - Vaclav Kotesovec, Aug 18 2018

A331577 Number of labeled rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 4, 65, 1026, 17857, 349224, 7657281, 186895270, 5037424601, 148805552556, 4784793219505, 166458635341194, 6231891513395745, 249886992888096976, 10686839817678846209, 485632267141865950926, 23370062118676064101801, 1187393725239246382405140

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

			Non-isomorphic representatives of the a(6) = 1026 trees (in the format root[branches]) are:
  1[2,3,4[5[6]]]
  1[2,3[4],5[6]]
  1[2,3,4[5,6]]
  1[2,3,4,5[6]]
  1[2,3,4,5,6]

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

The series-reduced version is A331578.
The unlabeled version is A331233.
Labeled rooted trees are counted by A000169.
Cf. A000081, A033185, A060313, A060356, A206429, A331488, A331490.

lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
Table[Length[Select[lrt[Range[n]],Length[#]>2&]],{n,6}]

seq(n)={my(f=serreverse(x*exp(O(x^n) -x ))); Vec(serlaplace(f - x*(1 + f + f^2/2)), -n)} \\ Andrew Howroyd, Jan 23 2020

For n > 1, a(n) = Sum_{k > 2} A206429(n, k).

E.g.f.: f(x) - x*(1 + f(x) + f(x)^2/2), where f(x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 23 2020

A335945 E.g.f. A(x) satisfies A(x) = exp(x*A(x)/(1 + x)).

Original entry on oeis.org

1, 1, 1, 4, 17, 116, 907, 9010, 102097, 1348408, 19939571, 330204854, 6015657529, 120016789348, 2597201945899, 60667591974826, 1520434054966433, 40710815980598000, 1159627208850209251, 35018022339726428926, 1117395892399939407241, 37569709612314269554396

Offset: 0

Ilya Gutkovskiy, Jul 01 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..414
Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A052868, A060356, A108919.

nmax = 21; A[] = 0; Do[A[x] = Exp[x A[x]/(1 + x)] + O[x]^(nmax + 1) // Normal, nmax + 1];CoefficientList[A[x], x] Range[0, nmax]!
nmax = 21; CoefficientList[Series[-(1 + x) LambertW[-x/(1 + x)]/x, {x, 0, nmax}], x] Range[0, nmax]!
Table[Sum[(-1)^(n - k) Binomial[n - 1, k - 1] (k + 1)^(k - 1) n!/k!, {k, 0, n}], {n, 0, 21}]

my(N=30, x='x+O('x^N)); Vec(serlaplace(exp(-lambertw(-x/(1+x))))) \\ Seiichi Manyama, Mar 05 2023

E.g.f.: -(1 + x) * LambertW(-x/(1 + x)) / x.
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n-1,k-1) * (k+1)^(k-1) * n! / k!.
a(n) ~ (exp(1) - 1)^(n + 1/2) * n^(n-1) / exp(n - 1/2). - Vaclav Kotesovec, Jul 01 2020
E.g.f.: exp ( -LambertW(-x/(1+x)) ). - Seiichi Manyama, Mar 05 2023

A300402 Smallest integer i such that TREE(i) >= n.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 0

Felix Fröhlich, Mar 05 2018

nonn

The sequence grows very slowly.
A rooted tree is a tree containing one special node labeled the "root".
TREE(n) gives the largest integer k such that a sequence T(1), T(2), ..., T(k) of vertex-colored (using up to n colors) rooted trees, each one T(i) having at most i vertices, exists such that T(i) <= T(j) does not hold for any i < j <= k. - Edited by Gus Wiseman, Jul 06 2020

			TREE(1) = 1, so a(n) = 1 for n <= 1.
TREE(2) = 3, so a(n) = 2 for 2 <= n <= 3.
TREE(3) > A(A(...A(1)...)), where A(x) = 2[x+1]x is a variant of Ackermann's function, a[n]b denotes a hyperoperation and the number of nested A() functions is 187196, so a(n) = 3 for at least 4 <= n <= A^A(187196)(1).

Priyabrata Biswas, Towards Data Science: How Big Is The Number — Tree(3)
Eric Weisstein's World of Mathematics, Rooted Tree
Wikipedia, Hyperoperation - Notations
Wikipedia, Kruskal's tree theorem

Cf. A090529, A300403, A300404.
Labeled rooted trees are counted by A000169 and A206429.
Cf. A000081, A000311, A060313, A060356, A317713.

A331727 E.g.f.: -LambertW(-x/(1 + x)) / (1 + x).

Original entry on oeis.org

0, 1, -2, 9, -32, 225, -1044, 11515, -53696, 1056321, -2809700, 164953371, 374457744, 42734920657, 415505963068, 17518516958475, 310367497789696, 10529847396874497, 258747727039635132, 8599295530916762779, 258064489282796717200, 9014901067536225062481

Offset: 0

Ilya Gutkovskiy, Jan 25 2020

sign

Vaclav Kotesovec, Table of n, a(n) for n = 0..400

Cf. A000169, A060356, A231797, A277511, A331726.

nmax = 21; CoefficientList[Series[-LambertW[-x/(1 + x)]/(1 + x), {x, 0, nmax}], x] Range[0, nmax]!
Table[Sum[(-1)^k Binomial[n, k]^2 k! (n - k)^(n - k - 1), {k, 0, n - 1}], {n, 0, 21}]

seq(n)={Vec(serlaplace(-lambertw(-x/(1 + x) + O(x*x^n)) / (1 + x)), -(n+1))} \\ Andrew Howroyd, Jan 25 2020

a(n) = Sum_{k=0..n-1} (-1)^k * binomial(n,k)^2 * k! * (n - k)^(n - k - 1).

a(n) ~ (1 - exp(-1))^(n + 3/2) * n^(n-1). - Vaclav Kotesovec, Jan 26 2020

A376107 Expansion of e.g.f. LambertW(x / (1 - 3*x)).

Original entry on oeis.org

0, 1, 4, 27, 260, 3265, 50634, 935263, 20053816, 489677697, 13416375950, 407609962111, 13600700469828, 494442286466401, 19452778285314178, 823489845351967935, 37323572563440199664, 1803303384581598518785, 92523649833821902792086

Offset: 0

Seiichi Manyama, Sep 10 2024

nonn

Eric Weisstein's World of Mathematics, Lambert W-Function.

Cf. A060356, A376106.

Cf. A376101.

nmax=20; CoefficientList[InverseSeries[Series[x / (3*x + E^(-x)), {x, 0, nmax}], x], x] * Range[0, nmax]! (* Vaclav Kotesovec, Sep 20 2024 *)

my(N=20, x='x+O('x^N)); concat(0, Vec(serlaplace(lambertw(x/(1-3*x)))))

a(n) = n!*sum(k=1, n, 3^(n-k)*(-k)^(k-1)*binomial(n-1, k-1)/k!);

E.g.f. A(x) satisfies A(x) = x * (3*A(x) + exp(-A(x))).
E.g.f.: Series_Reversion( x / (3*x + exp(-x)) ).
a(n) = n! * Sum_{k=1..n} 3^(n-k) * (-k)^(k-1) * binomial(n-1,k-1)/k!.

A305304 Expansion of e.g.f. 1/(1 + LambertW(-x/(1 + x))).

Original entry on oeis.org

1, 1, 2, 9, 52, 405, 3786, 42301, 542984, 7924041, 129110230, 2327399481, 45940938924, 986045445853, 22856850513602, 569163515043285, 15150885843083536, 429364157810169105, 12905794670246364078, 410108007771441394129, 13736898888997174964660, 483740530150449507164901, 17866185834825657429606682

Offset: 0

Ilya Gutkovskiy, Aug 18 2018

nonn

Inverse Lah transform of A000312.

N. J. A. Sloane, Transforms

Cf. A000312, A052871, A060356, A305276.

a:=series(1/(1+LambertW(-x/(1+x))),x=0,23): seq(n!*coeff(a,x,n),n=0..22); # Paolo P. Lava, Mar 26 2019

nmax = 22; CoefficientList[Series[1/(1 + LambertW[-x/(1 + x)]), {x, 0, nmax}], x] Range[0, nmax]!
Join[{1}, Table[Sum[(-1)^(n - k) Binomial[n - 1, k - 1] k^k n!/k!, {k, n}], {n, 22}]]

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n-1,k-1)*k^k*n!/k!.

a(n) ~ n^n * (exp(1) - 1)^(n - 1/2) / exp(n - 1/2). - Vaclav Kotesovec, Aug 18 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A376106 Expansion of e.g.f. LambertW(x / (1 - 2*x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A231602 Triangular array read by rows: T(n,k) is the number of rooted labeled trees on n nodes that have exactly k nodes with outdegree = 1, n>=1, 0<=k<=n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A305276 Expansion of e.g.f. 1/(1 + LambertW(-x/(1 - x))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A331577 Number of labeled rooted trees with n vertices and more than two branches of the root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A335945 E.g.f. A(x) satisfies A(x) = exp(x*A(x)/(1 + x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300402 Smallest integer i such that TREE(i) >= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A331727 E.g.f.: -LambertW(-x/(1 + x)) / (1 + x).

Views

Author

Keywords