cp's OEIS Frontend

A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).

%I A372167 #12 Dec 29 2024 19:19:44
%S A372167 1,0,1,3,1,22,12,6,0,1,237,220,165,70,35,30,0,10,0,0,1,3961,5460,5830,
%T A372167 4140,2805,2112,1230,720,600,180,230,60,45,60,0,0,15,0,0,0,1,99900,
%U A372167 191975,269220,272055,240485,207095,166005,121530,98770,65905,48503,37065,20055,17570,11445,6552,4410,3570,1680,1785,147,735,455,140,0,105,105,0,0,0,21,0,0,0,0,1
%N A372167 Irregular triangle read by rows where T(n,k) is the number of simple graphs covering n vertices with exactly k triangles, 0 <= k <= binomial(n,3).
%H A372167 Andrew Howroyd, <a href="/A372167/b372167.txt">Table of n, a(n) for n = 0..340</a> (rows 0..10)
%H A372167 Gus Wiseman, <a href="/A372167/a372167.png">All simple graphs covering {1,2,3,4} grouped by number of triangles</a>.
%F A372167 Inverse binomial transform of columns of A372170.
%e A372167 Triangle begins:
%e A372167     1
%e A372167     0
%e A372167     1
%e A372167     3    1
%e A372167    22   12    6    0    1
%e A372167   237  220  165   70   35   30    0   10    0    0    1
%e A372167   ...
%e A372167 Row k = 4 counts the following graphs:
%e A372167   12-34      12-13-14-23  12-13-14-23-24  .  12-13-14-23-24-34
%e A372167   13-24      12-13-14-24  12-13-14-23-34
%e A372167   14-23      12-13-14-34  12-13-14-24-34
%e A372167   12-13-14   12-13-23-24  12-13-23-24-34
%e A372167   12-13-24   12-13-23-34  12-14-23-24-34
%e A372167   12-13-34   12-14-23-24  13-14-23-24-34
%e A372167   12-14-23   12-14-24-34
%e A372167   12-14-34   12-23-24-34
%e A372167   12-23-24   13-14-23-34
%e A372167   12-23-34   13-14-24-34
%e A372167   12-24-34   13-23-24-34
%e A372167   13-14-23   14-23-24-34
%e A372167   13-14-24
%e A372167   13-23-24
%e A372167   13-23-34
%e A372167   13-24-34
%e A372167   14-23-24
%e A372167   14-23-34
%e A372167   14-24-34
%e A372167   12-13-24-34
%e A372167   12-14-23-34
%e A372167   13-14-23-24
%t A372167 cys[y_]:=Select[Subsets[Union@@y,{3}], MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
%t A372167 Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cys[#]]==k&]], {n,0,5},{k,0,Binomial[n,3]}]
%Y A372167 Row sums are A006129, unlabeled A002494.
%Y A372167 Row lengths are A050407.
%Y A372167 Counting edges instead of triangles gives A054548, unlabeled A370167.
%Y A372167 Column k = 0 is A372168 (non-covering A213434), unlabeled A372169.
%Y A372167 Covering case of A372170, unlabeled A263340.
%Y A372167 Column k = 1 is A372171 (non-covering A372172), unlabeled A372174.
%Y A372167 The unlabeled version is A372173.
%Y A372167 For all cycles (not just triangles) we have A372175, non-covering A372176.
%Y A372167 A001858 counts acyclic graphs, unlabeled A005195.
%Y A372167 A006125 counts simple graphs, unlabeled A000088.
%Y A372167 A105784 counts acyclic covering graphs, unlabeled A144958.
%Y A372167 Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.
%K A372167 nonn,tabf
%O A372167 0,4
%A A372167 _Gus Wiseman_, Apr 23 2024
%E A372167 a(42) onwards from _Andrew Howroyd_, Dec 29 2024