Robert Castelo - cp's OEIS frontend

User: Robert Castelo

Robert Castelo has authored 4 sequences.

A058862 Number of chordal labeled graphs (connected or not) with n nodes.

1, 2, 8, 61, 822, 18154, 617675, 30888596, 2192816760, 215488096587, 28791414081916, 5165908492061926, 1234777416771739141, 391374602835914994534, 164188178238479142509452

Offset: 1

Robert Castelo, Jan 06 2001

N. C. Wormald, Counting labeled chordal graphs. Graphs Combin. 1 (1985), no. 2, 193-200.

Ursula Hebert-Johnson, Daniel Lokshtanov, and Eric Vigoda, Counting and Sampling Labeled Chordal Graphs in Polynomial Time, arXiv:2308.09703 [cs.DS], 2023.
Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka, Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams, arXiv:1804.03822 [cs.DS], 2018.

Cf. A007134.

A007134 = Cases[Import["https://oeis.org/A007134/b007134.txt", "Table"],
   {, }][[All, 2]];
c[n_ /; 1 <= n <= Length[A007134]] := A007134[[n]];
a[n_] := a[n] = If[n == 0, 0, c[n] + 1/n * Sum[k*Binomial[n, k]*c[k]*
   a[n - k], {k, 1, n + 1}]];
Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Jul 20 2022 *)

From the relation G(x)=exp(g(x)) between generating functions for connected g(x) and all G(x) labeled structures and considering generating functions for chordal graphs (c_n, A007134), we have a(n) = c(n) + 1/n * Sum_{k=1}^(n - 1) k * binomial(n, k) * c(k) * a(n - k). [Formula edited by Michael De Vlieger, Jul 04 2018]

a(13) from formula by Falk Hüffner, Jul 24 2019

a(14)-a(15) from Brendan McKay, Jun 05 2021

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

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

cp's OEIS Frontend

User: Robert Castelo

A058862 Number of chordal labeled graphs (connected or not) with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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