login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A subclass of chordal-comparability graphs.
LINKS
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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 13:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)