A356916
Irregular triangle A(n, q) = total number of labeled P_4 - free chordal graphs on n vertices and q edges, read by rows; also companion triangle to A058865.
Original entry on oeis.org
1, 3, 3, 1, 6, 15, 8, 12, 6, 1, 10, 45, 60, 75, 60, 80, 30, 30, 10, 1, 15, 105, 275, 420, 516, 625, 465, 540, 495, 276, 255, 80, 60, 15, 1, 21, 210, 910, 2100, 3192, 4767, 5355, 4830, 5845, 5061, 5397, 4725, 2730, 2625, 1932, 882, 630, 175, 105, 21, 1
Offset: 1
The irregular triangle begins as:
1;
3, 3, 1;
6, 15, 8, 12, 6, 1;
10, 45, 60, 75, 60, 80, 30, 30, 10, 1;
15, 105, 275, 420, 516, 625, 465, 540, 495, 276, 255, 80, 60, 15, 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.
-
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[A[n, k], {n,2,12}, {k,Binomial[n, 2]}]//Flatten
-
A356916(n, q)={A058865(n, q) + sum(k=1, n-1, k*binomial(n, k)*sum(j=k-1, k*(k-1)/2, A058865(k, j)*A356916(n-k, q-j)))/n} \\ Edited: Code for A058865 should exist and be updated only there. - M. F. Hasler, Sep 26 2022
vector(7, n, vector(binomial(n+1,2), k, A356916(n+1, k)))
-
@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([[A(n,k) for k in (1..binomial(n,2))] for n in (2..12)])
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
- 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.
-
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
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
- 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.
-
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
Showing 1-3 of 3 results.
Comments