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
Examples
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 ...
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.
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[T[n, k], {n,2,12}, {k,Binomial[n, 2]}]//Flatten (* G. C. Greubel, Sep 03 2022 *) -
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
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)
Extensions
Typo in a(6,11) corrected by G. C. Greubel, Sep 03 2022
Comments