cp's OEIS Frontend

A356916 Irregular triangle A(n, q) = total number of labeled P_4 - free chordal graphs on n vertices and q edges, read by rows; also companion triangle to A058865.

%I A356916 #19 Sep 26 2022 18:11:20
%S A356916 1,3,3,1,6,15,8,12,6,1,10,45,60,75,60,80,30,30,10,1,15,105,275,420,
%T A356916 516,625,465,540,495,276,255,80,60,15,1,21,210,910,2100,3192,4767,
%U A356916 5355,4830,5845,5061,5397,4725,2730,2625,1932,882,630,175,105,21,1
%N A356916 Irregular triangle A(n, q) = total number of labeled P_4 - free chordal graphs on n vertices and q edges, read by rows; also companion triangle to A058865.
%H A356916 G. C. Greubel, <a href="/A356916/b356916.txt">Rows n = 2..30 of the irregular triangle, flattened</a>
%H A356916 R. Castelo and N. C. Wormald, <a href="http://www.cs.uu.nl/research/techreps/repo/CS-2001/2001-12.pdf">Enumeration of P4-free chordal graphs</a>.
%H A356916 R. Castelo and N. C. Wormald, <a href="http://dx.doi.org/10.1007/s00373-002-0513-9">Enumeration of P4-Free chordal graphs</a>, Graphs and Combinatorics, 19:467-474, 2003.
%H A356916 M. C. Golumbic, <a href="http://dx.doi.org/10.1016/0012-365X(78)90178-4">Trivially perfect graphs</a>, Discr. Math. 24(1) (1978), 105-107.
%H A356916 T. H. Ma and J. P. Spinrad, <a href="http://dx.doi.org/10.1007/BF00385814">Cycle-free partial orders and chordal comparability graphs</a>, Order, 1991, 8:49-61.
%H A356916 E. S. Wolk, <a href="http://dx.doi.org/10.1090/S0002-9939-1965-0172274-5">A note on the comparability graph of a tree</a>, Proc. Am. Math. Soc., 1965, 16:17-20.
%F A356916 Let a(n, q) be the number of labeled connected P_4 - free chordal graphs on n vertices and q edges (see A058865), then:
%F A356916 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.
%F A356916 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).
%F A356916 A(n, binomial(n,2)) = 1, n >= 2.
%F A356916 A(n, 1) = A(n, binomial(n,2) - 1) = A000217(n-1), n >= 2.
%F A356916 A(n, 2) = 3*A000332(n+1), n >= 3.
%e A356916 The irregular triangle begins as:
%e A356916    1;
%e A356916    3,   3,   1;
%e A356916    6,  15,   8,  12,   6,   1;
%e A356916   10,  45,  60,  75,  60,  80,  30,  30,  10,   1;
%e A356916   15, 105, 275, 420, 516, 625, 465, 540, 495, 276, 255, 80, 60, 15, 1;
%t A356916 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 *)
%t A356916 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 *)
%t A356916 Table[A[n, k], {n,2,12}, {k,Binomial[n, 2]}]//Flatten
%o A356916 (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
%o A356916 vector(7, n, vector(binomial(n+1,2), k, A356916(n+1, k)))
%o A356916 (SageMath)
%o A356916 @CachedFunction
%o A356916 def t(n,k): # t = A058865
%o A356916     if (k==binomial(n,2)): return 1
%o A356916     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) )
%o A356916 @CachedFunction
%o A356916 def A(n,k): # A = A356916
%o 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) )
%o A356916 flatten([[A(n,k) for k in (1..binomial(n,2))] for n in (2..12)])
%Y A356916 Cf. A000217, A000332, A058865.
%K A356916 nonn,tabf
%O A356916 1,2
%A A356916 _G. C. Greubel_, Sep 03 2022