A372170 - OEIS

%I #17 Dec 29 2024 19:19:36

%S 1,1,2,7,1,41,16,6,0,1,388,290,195,70,40,30,0,10,0,0,1,5789,6980,6910,

%T 4560,3030,2292,1230,780,600,180,236,60,45,60,0,0,15,0,0,0,1,133501,

%U 235270,313705,302505,260890,222509,174615,126780,102970,67165,50134,37485,20370,17990,11445,6552,4515,3570,1680,1785,154,735,455,140,0,105,105,0,0,0,21,0,0,0,0,1

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

%H Andrew Howroyd, <a href="/A372170/b372170.txt">Table of n, a(n) for n = 0..340</a> (rows 0..10)

%F Binomial transform of columns of A372167.

%e Triangle begins:

%e      1

%e      1

%e      2

%e      7    1

%e     41   16    6    0    1

%e    388  290  195   70   40   30    0   10    0    0    1

%e    ...

%e For example, the T(4,1) = 16 graphs are:

%e   12-13-23

%e   12-14-24

%e   13-14-34

%e   23-24-34

%e   12-13-14-23

%e   12-13-14-24

%e   12-13-14-34

%e   12-13-23-24

%e   12-13-23-34

%e   12-14-23-24

%e   12-14-24-34

%e   12-23-24-34

%e   13-14-23-34

%e   13-14-24-34

%e   13-23-24-34

%e   14-23-24-34

%t cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}]&&MemberQ[y,{#[[1]],#[[3]]}]&&MemberQ[y,{#[[2]],#[[3]]}]&];

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[cys[#]]==k&]],{n,0,5},{k,0,Binomial[n,3]}]

%Y Row sums are A006125, covering A006129.

%Y Row lengths are A050407.

%Y Counting edges instead of triangles gives A084546, covering A054548.

%Y Column k = 0 is A213434, covering A372168.

%Y The unlabeled version is A263340.

%Y The covering case is A372167, unlabeled A372173.

%Y Column k = 1 is A372172, covering A372171.

%Y For all cycles (not just triangles) we have A372176, covering A372175.

%Y A001858 counts acyclic graphs, unlabeled A005195.

%Y A367867 counts non-choosable graphs, covering A367868.

%Y A372193 counts unicyclic graphs, unlabeled A236570, covering A372191.

%Y Cf. A000088, A000272, A002494, A006785, A053530, A062734, A121251, A372194.

%K nonn,tabf,changed

%O 0,3

%A _Gus Wiseman_, Apr 23 2024

%E a(42) onwards from _Andrew Howroyd_, Dec 29 2024