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,2

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.

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.

Example

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;

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

Prog

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

Crossrefs

Cf. A000217, A000332, A058865.

Sequence in context: A039798 A193560 A278390 * A001498 A240439 A243211

Adjacent sequences: A356913 A356914 A356915 * A356917 A356918 A356919

Keyword

nonn,tabf

Author

G. C. Greubel, Sep 03 2022

Status

approved