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
KEYWORD
nonn,tabf
AUTHOR
G. C. Greubel, Sep 03 2022
STATUS
approved