OFFSET
1,3
COMMENTS
A subclass of chordal-comparability graphs.
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,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)
EXAMPLE
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
...
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[T[n, k], {n, 2, 12}, {k, Binomial[n, 2]}]//Flatten (* G. C. Greubel, Sep 03 2022 *)
PROG
(PARI) 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
(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([[T(n, k) for k in (1..binomial(n, 2))] for n in (2..12)]) # G. C. Greubel, Sep 03 2022
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
EXTENSIONS
Typo in a(6,11) corrected by G. C. Greubel, Sep 03 2022
STATUS
approved