login
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.
2

%I #19 Sep 26 2022 18:11:20

%S 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 516,625,465,540,495,276,255,80,60,15,1,21,210,910,2100,3192,4767,

%U 5355,4830,5845,5061,5397,4725,2730,2625,1932,882,630,175,105,21,1

%N 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 G. C. Greubel, <a href="/A356916/b356916.txt">Rows n = 2..30 of the irregular triangle, flattened</a>

%H 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 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 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 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 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 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 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 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 A(n, binomial(n,2)) = 1, n >= 2.

%F A(n, 1) = A(n, binomial(n,2) - 1) = A000217(n-1), n >= 2.

%F A(n, 2) = 3*A000332(n+1), n >= 3.

%e The irregular triangle begins as:

%e 1;

%e 3, 3, 1;

%e 6, 15, 8, 12, 6, 1;

%e 10, 45, 60, 75, 60, 80, 30, 30, 10, 1;

%e 15, 105, 275, 420, 516, 625, 465, 540, 495, 276, 255, 80, 60, 15, 1;

%t 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 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 Table[A[n, k], {n,2,12}, {k,Binomial[n, 2]}]//Flatten

%o (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 vector(7, n, vector(binomial(n+1,2), k, A356916(n+1, k)))

%o (SageMath)

%o @CachedFunction

%o def t(n,k): # t = A058865

%o if (k==binomial(n,2)): return 1

%o 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 @CachedFunction

%o def A(n,k): # A = A356916

%o 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 flatten([[A(n,k) for k in (1..binomial(n,2))] for n in (2..12)])

%Y Cf. A000217, A000332, A058865.

%K nonn,tabf

%O 1,2

%A _G. C. Greubel_, Sep 03 2022