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.

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

Author

G. C. Greubel, Sep 03 2022

Keywords

• nonn
• tabf

Examples

			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;
		

Links

• 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.

Crossrefs

Cf. A000217, A000332, A058865.

Programs

Mathematica

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

PARI

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)))

SageMath

@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)])

Formula

Let a(n, q) be the number of labeled connected P_4 - free chordal graphs on n vertices and q edges (see A058865), then:

a(n, q) = Sum_{k=1..n-2} binomial(n, k)*(A(n-k, q - k(2*n-1-k)/2) - a(n-k, q - k(2*n-1-k)/2)) for 1 <= q <= binomial(n,2), n >= 2, with a(n, binomial(n,2)) = 1.

A(n, q) = a(n, q) + Sum_{k = 1..n-1} binomial(n-1, k-1)*Sum_{j = k-1..min(k(k-1)/2, q)} a(k, j)*A(n-k, q-j).

A(n, binomial(n,2)) = 1, n >= 2.

A(n, 1) = A(n, binomial(n,2) - 1) = A000217(n-1), n >= 2.

A(n, 2) = 3*A000332(n+1), n >= 3.