A058863 -id:A058863 - cp's OEIS frontend

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

0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287

Offset: 0

Vladeta Jovovic, Apr 01 2001

Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020

			From _Gus Wiseman_, Dec 31 2019: (Start)
Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:
  1[2,3[4,5[6,7]]]
  1[2,3[4,5,6,7]]
  1[2[3,4],5[6,7]]
  1[2,3,4[5,6,7]]
  1[2,3,4,5[6,7]]
  1[2,3,4,5,6,7]
(End)

Harry J. Smith, Table of n, a(n) for n = 0..100
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. A052871, A060313.
Cf. A008297.
Column k=0 of A231602.
The unlabeled version is A001678(n + 1).
The case where the root is fixed is A108919.
Unlabeled rooted trees are counted by A000081.
Lone-child-avoiding rooted trees with labeled leaves are A000311.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Singleton-reduced rooted trees are counted by A330951.
Cf. A000669, A004111, A005121, A048816, A292504, A316651, A316652, A318231, A318813, A330465, A330624.

List([0..20],n->Sum([1..n],k->(-1)^(n-k)*Factorial(n)/Factorial(k) *Binomial(n-1,k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018

seq(coeff(series( -LambertW(-x/(1+x)), x, n+1), x, n)*n!, n = 0..20); # G. C. Greubel, Mar 16 2020

CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
a[n_]:=If[n==1,1,n*Sum[Times@@a/@Length/@stn,{stn,Select[sps[Range[n-1]],Length[#]>1&]}]];
Array[a,10] (* Gus Wiseman, Dec 31 2019 *)

{ for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009

my(x='x+O('x^20)); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018

a(n) = Sum_{k=1..n} (-1)^(n-k)*n!/k!*binomial(n-1, k-1)*k^(k-1). a(n) = Sum_{k=0..n} Stirling1(n, k)*A058863(k). - Vladeta Jovovic, Sep 17 2003
a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - Vaclav Kotesovec, Nov 27 2012
a(n) = n * A108919(n). - Gus Wiseman, Dec 31 2019

A048802 Number of labeled rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Original entry on oeis.org

1, 3, 16, 133, 1521, 22184, 393681, 8233803, 198342718, 5408091155, 164658043397, 5537255169582, 203840528337291, 8153112960102283, 352079321494938344, 16325961781591781401, 809073412162081974237, 42674870241038732398720, 2386963662244981472850709

Offset: 1

Christian G. Bower, Mar 15 1999

nonn

			G.f. = x + 3*x^2 + 16*x^3 + 133*x^4 + 1521*x^5 + 22184*x^6 + 393681*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..200
F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 861
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
Index entries for sequences related to rooted trees

Cf. A036249, A038052, A058863, A052807.

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ ComposeSeries[ Series[t,{x,0,nn}],Series[Exp[x]-1 ,{x,0,nn}]],x]  (* Geoffrey Critzer, Sep 16 2012 *)

{a(n) = sum( k=1, n, stirling(n, k, 2) * k^(k - 1))}; /* Michael Somos, Jun 09 2012 */

{a(n) = n! * polcoeff( serreverse( log(1 + x*exp(-x +x*O(x^n))) ),n)}
for(n=1,30,print1(a(n),", ")) \\ Paul D. Hanna, Jan 24 2016

E.g.f.: B(exp(x)-1) where B is e.g.f. of A000169.
E.g.f.: Series_Reversion( log(1 + x*exp(-x)) ). - Paul D. Hanna, Jan 24 2016
a(n) = Sum_{k=1..n} Stirling2(n, k)*k^(k-1). - Vladeta Jovovic, Sep 17 2003
Stirling transform of A000169. - Michael Somos, Jun 09 2012
a(n) ~ sqrt(1+exp(1)) * n^(n-1) / (exp(n) * (log(1+exp(-1)))^(n-1/2)). - Vaclav Kotesovec, Feb 17 2014

A058864 Number of labeled chordal graphs (connected or not) on n nodes with no induced path P_4.

Original entry on oeis.org

1, 2, 8, 49, 402, 4144, 51515, 750348, 12537204, 236424087, 4967735896, 115102258660, 2915655255385, 80164472149454, 2377679022913612, 75674858155603353, 2572626389524849478, 93040490884813025684, 3566833833735159397963, 144485408698878208399296

Offset: 1

Robert Castelo, Jan 06 2001

nonn

A subclass of chordal-comparability graphs.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 417.

G. C. Greubel, Table of n, a(n) for n = 1..398
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, A058863, A058865.

Cf. variants: A196555, A196556, A196557.

Rest[With[{nmax = 50}, CoefficientList[Series[Exp[-LambertW[Exp[-x] - 1]], {x, 0, nmax}], x]*Range[0, nmax]!]] (* G. C. Greubel, Nov 14 2017 *)
a[n_] := Sum[(-1)^(n-k)*StirlingS2[n, k]*(k+1)^(k-1), {k, 0, n}];
Array[a, 18] (* Jean-François Alcover, Dec 17 2017, after Vladeta Jovovic *)

{a(n)=polcoeff(sum(m=1, n, (m+1)^(m-1)*x^m/prod(k=1, m, 1+k*x+x*O(x^n))), n)} /* Paul D. Hanna, Jul 20 2011 */

for(n=1,10, print1(sum(k=0, n, (-1)^(n-k)*stirling(n,k,2)*(k+1)^(k-1)), ", ")) \\ G. C. Greubel, Nov 14 2017

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.
O.g.f.: Sum_{n>=1} (n+1)^(n-1) * x^n / Product_{k=1..n} (1+k*x). - Paul D. Hanna, Jul 20 2011
E.g.f.: exp(-LambertW(exp(-x)-1)). - Vladeta Jovovic, Nov 22 2002
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling2(n, k)*(k+1)^(k-1). - Vladeta Jovovic, Nov 12 2003
a(n) ~ sqrt(exp(1)-1) * exp(1-n) * n^(n-1) * (1-log(exp(1)-1))^(1/2-n). - Vaclav Kotesovec, Oct 18 2013

Formulae edited and completed by Michel Marcus, Apr 07 2013

A058865 Irregular table a(n,k) = number of connected labeled chordal graphs on n nodes with k edges, containing no induced path P_4, for n >= 1, 1 <= k <= n*(n-1)/2, read by rows; also the number of labeled trees with each vertex replaced by a clique.

Original entry on oeis.org

1, 0, 3, 1, 0, 0, 4, 12, 6, 1, 0, 0, 0, 5, 30, 75, 30, 30, 10, 1, 0, 0, 0, 0, 6, 60, 270, 360, 435, 270, 255, 80, 60, 15, 1, 0, 0, 0, 0, 0, 7, 105, 735, 1925, 2940, 3591, 4165, 2310, 2520, 1925, 882, 630, 175, 105, 21, 1, 0, 0, 0, 0, 0, 0, 8, 168, 1680, 7280, 16800

Offset: 1

Robert Castelo, Jan 06 2001

A subclass of chordal-comparability graphs.

			The table starts:
   n | a(n, 1 <= k <= n(n-1)/2)
  ---+---------------------------
   1 | ()    (row length = 0: empty row)
   2 | 1
   3 | 0, 3, 1
   4 | 0, 0, 4, 12, 6, 1
   5 | 0, 0, 0, 5, 30, 75, 30, 30, 10, 1
  ...

G. C. Greubel, Rows n = 2..30 of the irregular triangle, flattened
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.
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. A000217 (row lengths, up to offset), A000292, A007134, A058863, A058864.

Cf. A356916.

T[n_, k_]:= T[n, k]= If[k==Binomial[n, 2], 1, Sum[Binomial[n, j]*(A[n-j, k-j*(2*n -1-j)/2] - T[n-j, k-j*(2*n-1-j)/2]), {j, n-2}]]; (* T = A058865 *)
A[n_, k_]:= A[n, k]= T[n, k] + Sum[Sum[Binomial[n-1, j-1]*T[j, m]*A[n-j, k-m], {j, n-1}], {m, 0, k}]; (* A = A356916 *)
Table[T[n, k], {n,2,12}, {k,Binomial[n, 2]}]//Flatten (* G. C. Greubel, Sep 03 2022 *)

A58865=Map(); A058865(n,q) = if( q < n-1 || q >= n*(n-1)\2, q==n*(n-1)\2, mapisdefined(A58865, [n,q], &q), q, mapput(A58865, [n,q], q = sum(k=1,n-2, binomial(n,k)*(A356916(n-k, q - k*(k-1)/2 - k*(n-k)) - A058865(n-k, q - k*(k-1)\2 - (n-k)*k)))); q) \\ A356916 "outsourced" by M. F. Hasler, Sep 26 2022
[[A058865(n,k)| k<-[1..n*(n-1)/2]] | n<-[1..7]] \\ M. F. Hasler, Sep 03 2022

@CachedFunction
def T(n,k): # T = A058865
    if (k==binomial(n,2)): return 1
    else: return sum( binomial(n,j)*( A(n-j, k-j*(2*n-1-j)/2) - T(n-j, k-j*(2*n-1-j)/2) ) for j in (1..n-2) )
@CachedFunction
def A(n,k): # A = A356916
    return T(n,k) + sum(sum( binomial(n-1,j-1)*T(j,m)*A(n-j,k-m) for j in (1..n-1) ) for m in (0..k) )
flatten([[T(n,k) for k in (1..binomial(n,2))] for n in (2..12)]) # G. C. Greubel, Sep 03 2022

Let A(n,k) be the total number of labeled P_4 - free chordal graphs on n vertices and q edges (= A356916), then:
a(n,q) = Sum_{k=1..n-2} binomial(n,k)*(A(n-k, q - k(k-1)/2 - k(n-k)) - a(n-k, q - k(k-1)/2 - k(n-k))) for q < n(n-1)/2 =: T(n), a(n, T(n)) = 1. [Corrected by M. F. Hasler, Sep 03 2022]
A(n,q) = a(n,q) + Sum_{k = 1..n-1} binomial(n-1, k-1)*Sum_{l = k-1..min(k(k-1)/2, q)} a(k,l)*A(n-k,q-l). [Simplified by M. F. Hasler, Sep 03 2022]
Particular values: a(n,k) = 0 for q < n-1; a(n, T(n)) = 1; a(n,n-1) = n; a(n, T(n)-1) = n(n-1)/2 for n > 2, a(n, n) = a(n, T(n)-2) = n(n-1)(n-2)/2 for n > 3. - M. F. Hasler, Sep 03 2022
From G. C. Greubel, Sep 03 2022: (Start)
a(n, binomial(n,2) - 1) = A000217(n+1) - [n=2], n >= 2.
a(n, n) = 3*A000292(n) - 2*[n=3], n >= 3.
Sum_{k=1..binomial(n,2)} a(n, k) = A058863(n). (End)

Typo in a(6,11) corrected by G. C. Greubel, Sep 03 2022

A350528 Triangle read by rows: T(n,k) is the number of labeled quasi-threshold graphs on vertex set [n] with k components, for n >= 1 and 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 3, 1, 23, 19, 6, 1, 181, 155, 55, 10, 1, 1812, 1591, 600, 125, 15, 1, 22037, 19705, 7756, 1750, 245, 21, 1, 315569, 286091, 116214, 27741, 4270, 434, 28, 1, 5201602, 4766823, 1983745, 493794, 81291, 9198, 714, 36, 1

Offset: 1

David Galvin, Jan 03 2022

The family of quasi-threshold graphs is the smallest family of graphs that contains K_1 (a single vertex), and is closed under taking unions and adding dominating vertices (adjacent to all other vertices).

			Triangle begins:
       1;
       1,      1;
       4,      3,      1;
      23,     19,      6,      1;
     181,    155,     55,     10,     1;
    1812,   1591,    600,    125,    15,    1;
   22037,  19705,   7756,   1750,   245,   21,   1;
  315569, 286091; 116214,  27741,  4270,  434,  28,  1;
  ...

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

First column is A058863.
Row sums are A058864.
Cf. A008277.

T[n_, k_] := T[n, k] = Sum[((-1)^(n - j))*StirlingS2[n, j]*k*Binomial[j, k]*(j^(j - k - 1)), {j, 1, n}]; Table[T[n, k], {n, 1, 12}, {k, 1, n}]

T(n,k) = Sum_{j=1..n} (-1)^(n-j)*Stirling2(n, j)*k*binomial(j, k)*j^(j-k-1) for n >= 1, 1 <= k <= n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI

Formula

A048802 Number of labeled rooted trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A058864 Number of labeled chordal graphs (connected or not) on n nodes with no induced path P_4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A058865 Irregular table a(n,k) = number of connected labeled chordal graphs on n nodes with k edges, containing no induced path P_4, for n >= 1, 1 <= k <= n*(n-1)/2, read by rows; also the number of labeled trees with each vertex replaced by a clique.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

Extensions

A350528 Triangle read by rows: T(n,k) is the number of labeled quasi-threshold graphs on vertex set [n] with k components, for n >= 1 and 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula