A058865 Irregular table a(n,k) = number of connected labeled chordal graphs on n nodes with k edges, containing no induced path P_4, for n >= 1, 1 <= k <= n*(n-1)/2, read by rows; also the number of labeled trees with each vertex replaced by a clique.

1, 0, 3, 1, 0, 0, 4, 12, 6, 1, 0, 0, 0, 5, 30, 75, 30, 30, 10, 1, 0, 0, 0, 0, 6, 60, 270, 360, 435, 270, 255, 80, 60, 15, 1, 0, 0, 0, 0, 0, 7, 105, 735, 1925, 2940, 3591, 4165, 2310, 2520, 1925, 882, 630, 175, 105, 21, 1, 0, 0, 0, 0, 0, 0, 8, 168, 1680, 7280, 16800

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

Cf. A000217 (row lengths, up to offset), A000292, A007134, A058863, A058864.

Cf. A356916.

Sequence in context: A217334 A369455 A353859 * A318502 A115090 A112295

Adjacent sequences: A058862 A058863 A058864 * A058866 A058867 A058868

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