A060356 -id:A060356 - cp's OEIS frontend

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

0, 1, 4, 27, 268, 3585, 60846, 1255471, 30535912, 855688833, 27148954330, 962037575631, 37659124454700, 1613921425656865, 75156944627712598, 3778932799275876495, 204039148080188427856, 11774630933193827543553

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Previous name was: A simple grammar.

G. C. Greubel, Table of n, a(n) for n = 0..369
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 842
Index entries for reversions of series

Cf. A008297, A060356.

spec := [S,{C=Sequence(Z,1 <= card),B=Set(S),S=Prod(B,C)},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

CoefficientList[Series[-LambertW[x/(-1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 30 2013 *)

makelist(sum((n!/k!)*binomial(n-1, k-1)*k^(k-1), k, 1, n), n, 0, 17);  /* Bruno Berselli, May 25 2011 */

x='x+O('x^50); concat([0], Vec(serlaplace(- lambertw(x/(-1+x))) )) \\ G. C. Greubel, Nov 08 2017

E.g.f.: -LambertW(x/(-1+x))
a(n) = Sum_{k=1..n} (n!/k!)*binomial(n-1, k-1)*k^(k-1). - Vladeta Jovovic, Sep 17 2003
a(n) ~ (1+exp(-1))^(n+1/2)*n^(n-1). - Vaclav Kotesovec, Sep 30 2013
From Seiichi Manyama, Sep 10 2024: (Start)
E.g.f. A(x) satisfies A(x) = x * (A(x) + exp(A(x))).
E.g.f.: Series_Reversion( x / (x + exp(x)) ). (End)

New name using e.g.f., Vaclav Kotesovec, Sep 30 2013

A005512 Number of series-reduced labeled trees with n nodes.

Original entry on oeis.org

1, 1, 0, 4, 5, 96, 427, 6448, 56961, 892720, 11905091, 211153944, 3692964145, 75701219608, 1613086090995, 38084386700896, 949168254452993, 25524123909350112, 725717102391257347, 21955114496683796680

Offset: 1

N. J. A. Sloane, Simon Plouffe

			a(6) = 96 because there are two unlabeled series-reduced trees on six vertices, the star and the tree with two vertices of degree three and four leaves; the first of these can be labeled in 6 ways and the second in 90, for a total of 96. - Isabel C. Lugo (izzycat(AT)gmail.com), Aug 19 2004

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 188 (3.1.94)
F. Harary and E. M. Palmer, Graphical Enumeration. New York: Academic Press, 1973. (gives g.f. for unlabeled series-reduced trees)
R. C. Read, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..100
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)
D. M. Jackson, Letter to N. J. A. Sloane, May 1975
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
A. Meir and J. W. Moon, On nodes of degree two in random trees, Mathematika 15 1968 188-192.
R. C. Read, Some Unusual Enumeration Problems, Annals of the New York Academy of Sciences, Vol. 175, 1970, 314-326.
Eric Weisstein's World of Mathematics, Series-reduced Tree
Index entries for sequences related to trees

Cf. A000014 (unlabeled analog), A060313.

[1] cat [Factorial(n-2)*(&+[(-1)^k*Binomial(n,k)*(n-k)^(n-k-2)/Factorial(n-k-2): k in [0..n-2]]): n in [2..20]]

A005512 := proc(n)
    if n = 1 then
        1;
    else
        add( (-1)^(n-r)*binomial(n,r)*r^(r-2)/(r-2)!,r=2..n) ;
        %*(n-2)! ;
    end if;
end proc: # R. J. Mathar, Sep 09 2014

a[1] = a[2] = 1; a[3] = 0; a[n_] := n!*(n-2)!*Sum[ (-1)^k*(n-k)^(n-k-3) / (k!*(n-k-2)!^2*(n-k-1)), {k, 0, n-2}]; Table[a[n], {n, 1, 20}](* Jean-François Alcover, Feb 16 2012, after given formula *)
u[1, 1] = 1; u[2, 1] = 0; u[2, 2] = 1; u[3, k_] := 0;
u[n_, k_] /; k <= 0 := 0;
u[n_, k_] /; k >= 1 :=
u[n, k] = (n (n - k) u[n - 1, k - 1] + n (n - 1) (n - 3) u[n - 2, k - 1])/k;
Table[Sum[u[n, m], {m, 1, n}], {n, 50}] (* David Callan, Jun 25 2014, fast generation, after R. C. Read link *)

a(n) = if(n<=1, n==1, sum(k=0, n-2, (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!)) \\ Andrew Howroyd, Dec 18 2017

[1]+[factorial(n-2)*sum((-1)^k*binomial(n,k)*(n-k)^(n-k-2)/factorial( n-k-2) for k in (0..n-2)) for n in (2..20)] # G. C. Greubel, Mar 07 2020

a(n) = A060313(n)/n.
a(n) = Sum_{k=0..n-2} (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!, n>=2.
E.g.f.: (1+x)*B(x)*(1-B(x)/2), where B(x) is e.g.f. for A060356. - Vladeta Jovovic, Dec 17 2004
a(n) ~ (1-exp(-1))^(n+1/2)*n^(n-2). - Vaclav Kotesovec, Aug 07 2013

Formula from Christian G. Bower, Jan 16 2004

A331488 Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 3, 6, 10, 20, 36, 70, 134, 263, 513, 1022, 2030, 4076, 8203, 16614, 33738, 68833, 140796, 288989, 594621, 1226781, 2536532, 5256303, 10913196, 22700682, 47299699, 98714362, 206323140, 431847121, 905074333, 1899247187, 3990145833, 8392281473

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

Also the number of lone-child-avoiding rooted trees with n vertices and more than two branches.

			The a(4) = 1 through a(9) = 10 trees:
  (ooo)  (oooo)  (ooooo)   (oooooo)   (ooooooo)    (oooooooo)
                 (oo(oo))  (oo(ooo))  (oo(oooo))   (oo(ooooo))
                           (ooo(oo))  (ooo(ooo))   (ooo(oooo))
                                      (oooo(oo))   (oooo(ooo))
                                      (o(oo)(oo))  (ooooo(oo))
                                      (oo(o(oo)))  (o(oo)(ooo))
                                                   (oo(o(ooo)))
                                                   (oo(oo)(oo))
                                                   (oo(oo(oo)))
                                                   (ooo(o(oo)))

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

The not necessarily lone-child-avoiding version is A331233.
The Matula-Goebel numbers of these trees are listed by A331490.
A000081 counts unlabeled rooted trees.
A001678 counts lone-child-avoiding rooted trees.
A001679 counts topologically series-reduced rooted trees.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A331489 lists Matula-Goebel numbers of series-reduced rooted trees.
Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],Length[#]>2&&FreeQ[#,{_}]&]],{n,10}]

For n > 1, a(n) = A001679(n) - A001678(n).

a(37)-a(38) from Jinyuan Wang, Jun 26 2020

Terminology corrected (lone-child-avoiding, not series-reduced) by Gus Wiseman, May 10 2021

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

A331490 Matula-Goebel numbers of series-reduced rooted trees with more than two branches (of the root).

Original entry on oeis.org

8, 16, 28, 32, 56, 64, 76, 98, 112, 128, 152, 172, 196, 212, 224, 256, 266, 304, 343, 344, 392, 424, 428, 448, 512, 524, 532, 602, 608, 652, 686, 688, 722, 742, 784, 848, 856, 896, 908, 931, 1024, 1048, 1052, 1064, 1204, 1216, 1244, 1304, 1372, 1376, 1444

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

We say that a rooted tree is (topologically) series-reduced if no vertex has degree 2.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.
Also Matula-Goebel numbers of lone-child-avoiding rooted trees with more than two branches.

			The sequence of all series-reduced rooted trees with more than two branches together with their Matula-Goebel numbers begins:
    8: (ooo)
   16: (oooo)
   28: (oo(oo))
   32: (ooooo)
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   98: (o(oo)(oo))
  112: (oooo(oo))
  128: (ooooooo)
  152: (ooo(ooo))
  172: (oo(o(oo)))
  196: (oo(oo)(oo))
  212: (oo(oooo))
  224: (ooooo(oo))
  256: (oooooooo)
  266: (o(oo)(ooo))
  304: (oooo(ooo))
  343: ((oo)(oo)(oo))
  344: (ooo(o(oo)))

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

These trees are counted by A331488.
Unlabeled rooted trees are counted by A000081.
Lone-child-avoiding rooted trees are counted by A001678.
Topologically series-reduced rooted trees are counted by A001679.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Matula-Goebel numbers of series-reduced rooted trees are A331489.
Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
srQ[n_]:=Or[n==1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];
Select[Range[1000],PrimeOmega[#]>2&&srQ[#]&]

A254382 Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.

Original entry on oeis.org

0, 1, 2, 3, 16, 85, 696, 6349, 72080, 918873, 13484080, 219335281, 3962458248, 78203547877, 1680235050872, 38958029188485, 970681471597216, 25847378934429361, 732794687650764000, 22032916968153975769, 700360446794528578520

Offset: 0

Geoffrey Critzer, Jan 29 2015

nonn

Here, a branching node is a node with at least two children.
In other words, a(n) is the number of labeled rooted trees on n nodes such that the path from every node towards the root reaches a branching node (or the root) in one step.
Also labeled rooted trees that are lone-child-avoiding except possibly for the root. The unlabeled version is A198518. - Gus Wiseman, Jan 22 2020

			a(5) = 85:
...0................0...............0-o...
...|.............../ \............ /|\....
...o..............o   o...........o o o...
../|\............/ \   ...................
.o o o..........o   o   ..................
These trees have 20 + 60 + 5 = 85 labelings.
From _Gus Wiseman_, Jan 22 2020: (Start)
The a(1) = 1 through a(4) = 16 trees (in the format root[branches]) are:
  1  1[2]  1[2,3]  1[2,3,4]
     2[1]  2[1,3]  1[2[3,4]]
           3[1,2]  1[3[2,4]]
                   1[4[2,3]]
                   2[1,3,4]
                   2[1[3,4]]
                   2[3[1,4]]
                   2[4[1,3]]
                   3[1,2,4]
                   3[1[2,4]]
                   3[2[1,4]]
                   3[4[1,2]]
                   4[1,2,3]
                   4[1[2,3]]
                   4[2[1,3]]
                   4[3[1,2]]
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..200
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.

Cf. A231797, A052318 (condition is applied only to leaf nodes).
The unlabeled version is A198518
The non-planted case is A060356.
Labeled rooted trees are A000169.
Lone-child-avoiding rooted trees are A001678(n + 1).
Labeled topologically series-reduced rooted trees are A060313.
Labeled lone-child-avoiding unrooted trees are A108919.
Cf. A000014, A000669, A001679, A005512, A291636, A331488, A331578.

nn = 20; b = 1 + Sum[nn = n; n! Coefficient[Series[(Exp[x] - x)^n, {x, 0, nn}], x^n]*x^n/n!, {n,1, nn}]; c = Sum[a[n] x^n/n!, {n, 0, nn}]; sol = SolveAlways[b == Series[1/(1 - (c - x)), {x, 0, nn}], x]; Flatten[Table[a[n], {n, 0, nn}] /. sol]
nn = 30; CoefficientList[Series[1+x-1/Sum[SeriesCoefficient[(E^x-x)^n,{x,0,n}]*x^n,{n,0,nn}],{x,0,nn}],x] * Range[0,nn]! (* Vaclav Kotesovec, Jan 30 2015 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
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]],FreeQ[Z@@#,Integer[]]&]],{n,6}] (* Gus Wiseman, Jan 22 2020 *)

E.g.f.: A(x) satisfies 1/(1 - (A(x) - x)) = B(x) where B(x) is the e.g.f. for A231797.

a(n) ~ (1-exp(-1))^(n-1/2) * n^(n-1). - Vaclav Kotesovec, Jan 30 2015

A331489 Matula-Goebel numbers of topologically series-reduced rooted trees.

Original entry on oeis.org

1, 2, 7, 8, 16, 19, 28, 32, 43, 53, 56, 64, 76, 98, 107, 112, 128, 131, 152, 163, 172, 196, 212, 224, 227, 256, 263, 266, 304, 311, 343, 344, 383, 392, 424, 428, 443, 448, 512, 521, 524, 532, 577, 602, 608, 613, 652, 686, 688, 719, 722, 742, 751, 784, 848, 856

Offset: 1

Gus Wiseman, Jan 20 2020

nonn

We say that a rooted tree is topologically series-reduced if no vertex (including the root) has degree 2.

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of all topologically series-reduced rooted trees together with their Matula-Goebel numbers begins:
    1: o
    2: (o)
    7: ((oo))
    8: (ooo)
   16: (oooo)
   19: ((ooo))
   28: (oo(oo))
   32: (ooooo)
   43: ((o(oo)))
   53: ((oooo))
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   98: (o(oo)(oo))
  107: ((oo(oo)))
  112: (oooo(oo))
  128: (ooooooo)
  131: ((ooooo))
  152: (ooo(ooo))
  163: ((o(ooo)))

Eric Weisstein's World of Mathematics, Series-reduced tree.
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Unlabeled rooted trees are counted by A000081.
Topologically series-reduced trees are counted by A000014.
Topologically series-reduced rooted trees are counted by A001679.
Labeled topologically series-reduced trees are counted by A005512.
Labeled topologically series-reduced rooted trees are counted by A060313.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000669, A001678, A007097, A007821, A060356, A061775, A109082, A109129, A196050, A254382, A276625, A330943, A331490.

nn=1000;
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
srQ[n_]:=Or[n==1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];
Select[Range[nn],PrimeOmega[#]!=2&&And@@srQ/@primeMS[#]&]

A331578 Number of labeled series-reduced rooted trees with n vertices and more than two branches of the root.

Original entry on oeis.org

0, 0, 0, 4, 5, 186, 847, 17928, 166833, 3196630, 45667391, 925287276, 17407857337, 393376875906, 8989368580935, 229332484742416, 6094576250570849, 174924522900914094, 5271210321949744111, 168792243040279327860, 5674164658298121248361, 200870558472768096534490

Offset: 1

Gus Wiseman, Jan 21 2020

nonn

A rooted tree is series-reduced if no vertex (including the root) has degree 2.

Also labeled lone-child-avoiding rooted trees with n vertices and more than two branches, where a rooted tree is lone-child-avoiding if no vertex has exactly one child.

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

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

The non-series-reduced version is A331577.
The unlabeled version is A331488.
Lone-child-avoiding rooted trees are counted by A001678.
Topologically series-reduced rooted trees are counted by A001679.
Labeled topologically series-reduced rooted trees are counted by A060313.
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Matula-Goebel numbers of series-reduced rooted trees are A331489.
Cf. A000014, A000169, A000669, A005512, A108919, A206429, A331233, 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&&FreeQ[#,[]]&]],{n,6}]

a(n) = {if(n<=1, 0, sum(k=1, n, (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k!))} \\ Andrew Howroyd, Dec 09 2020

seq(n)={my(w=lambertw(-x/(1+x) + O(x*x^n))); Vec(serlaplace(-x - w - (x/2)*w^2), -n)} \\ Andrew Howroyd, Dec 09 2020

From Andrew Howroyd, Dec 09 2020: (Start)
a(n) = A060313(n) - n*A060356(n-1) for n > 1.
a(n) = Sum_{k=1..n} (-1)^(n-k)*k^(k-2)*n*(n-2)!*binomial(n-1,k-1)*(2*k*n - n - k^2)/k! for n > 1.
E.g.f.: -x - LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2.
(End)

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

A058863 Number of connected labeled chordal graphs on n nodes with no induced path P_4; also the number of labeled trees with each vertex replaced by a clique.

Original entry on oeis.org

1, 1, 4, 23, 181, 1812, 22037, 315569, 5201602, 97009833, 2019669961, 46432870222, 1168383075471, 31939474693297, 942565598033196, 29866348653695203, 1011335905644178273, 36446897413531401020, 1392821757824071815641, 56259101478392975833333

Offset: 1

Robert Castelo, Jan 06 2001

nonn

A subclass of chordal-comparability graphs.

Jon E. Schoenfield, Table of n, a(n) for n = 1..100
R. Castelo and N. C. Wormald, Enumeration of P4-free chordal graphs
R. Castelo and N. C. Wormald, Enumeration of P4-Free chordal graphs, Graphs and Combinatorics, 19:467-474, 2003.
M. C. Golumbic, Trivially perfect graphs, Discr. Math. 24(1) (1978), 105-107.
Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117.
T. H. Ma and J. P. Spinrad, Cycle-free partial orders and chordal comparability graphs, Order, 1991, 8:49-61.
E. S. Wolk, A note on the comparability graph of a tree, Proc. Am. Math. Soc., 1965, 16:17-20.

Cf. A007134, A058864, A058865.

Cf. A048802.

S:= series(-LambertW(exp(-x)-1), x, 101):
seq(coeff(S,x,j)*j!, j=1..100); # Robert Israel, Nov 30 2015

a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*k^(k-1), {k, 1, n}];
Array[a, 20] (* Jean-François Alcover, Dec 17 2017, after Vladeta Jovovic *)

geta(n, va, vA) = {local(k); if (n==1, return(1)); if (n==2, return(1)); return(1 + sum(k=1, n-2, binomial(n,k)*(vA[n-k] - va[n-k])));}
getA(n, va, vA) = {local(k); if (n==1, return(1)); if (n==2, return(2)); return ((va[n] + sum(k=1, n-1, k*va[k]*binomial(n,k)*vA[n-k])/n));}
both(n) = {va = vector(n); vA = vector(n); for (i=1, n, va[i] = geta(i, va, vA); vA[i] = getA(i, va, vA);); print("va_A058863=", va); print("vA_A058864=", vA);}
\\ Michel Marcus, Apr 03 2013

A058863 and A058864 satisfy:
  1) c(n) = 1 + Sum_{k=1..n-2} binomial(n, k)*(t(n-k) - c(n-k))
  2) t(n) = c(n) + Sum_{k=1..n-1} k*c(k)*binomial(n, k)*t(n-k)/n
  where c(n) (A058863) is the number of connected graphs of this type and t(n) (A058864) is the total number of such graphs.
a(n) is asymptotic to sqrt(r*(e-1))/n*(n/(e*r))^n where r = 1 - log(e-1).
E.g.f.: -LambertW(exp(-x)-1). - Vladeta Jovovic, Nov 22 2002
a(n) = Sum_{k=0..n} Stirling2(n, k)*A060356(k). Also a(n) = Sum_{k=1..n} (-1)^(n-k)*Stirling2(n, k)*k^(k-1). - Vladeta Jovovic, Sep 17 2003

Formulae edited and completed by Michel Marcus, Apr 07 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A005512 Number of series-reduced labeled trees with n nodes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A331488 Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A331490 Matula-Goebel numbers of series-reduced rooted trees with more than two branches (of the root).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A254382 Number of rooted labeled trees on n nodes such that every nonroot node is the child of a branching node or of the root.

Views

Author

Keywords