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).

1, 0, 1, 3, 1, 22, 12, 6, 0, 1, 237, 220, 165, 70, 35, 30, 0, 10, 0, 0, 1, 3961, 5460, 5830, 4140, 2805, 2112, 1230, 720, 600, 180, 230, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 99900, 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

Offset: 0

Author

Gus Wiseman, Apr 23 2024

Keywords

• nonn
• tabf

Examples

			Triangle begins:
    1
    0
    1
    3    1
   22   12    6    0    1
  237  220  165   70   35   30    0   10    0    0    1
  ...
Row k = 4 counts the following graphs:
  12-34      12-13-14-23  12-13-14-23-24  .  12-13-14-23-24-34
  13-24      12-13-14-24  12-13-14-23-34
  14-23      12-13-14-34  12-13-14-24-34
  12-13-14   12-13-23-24  12-13-23-24-34
  12-13-24   12-13-23-34  12-14-23-24-34
  12-13-34   12-14-23-24  13-14-23-24-34
  12-14-23   12-14-24-34
  12-14-34   12-23-24-34
  12-23-24   13-14-23-34
  12-23-34   13-14-24-34
  12-24-34   13-23-24-34
  13-14-23   14-23-24-34
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)
• Gus Wiseman, All simple graphs covering {1,2,3,4} grouped by number of triangles.

Crossrefs

Row sums are A006129, unlabeled A002494.

Row lengths are A050407.

Counting edges instead of triangles gives A054548, unlabeled A370167.

Column k = 0 is A372168 (non-covering A213434), unlabeled A372169.

Covering case of A372170, unlabeled A263340.

Column k = 1 is A372171 (non-covering A372172), unlabeled A372174.

The unlabeled version is A372173.

For all cycles (not just triangles) we have A372175, non-covering A372176.

A001858 counts acyclic graphs, unlabeled A005195.

A006125 counts simple graphs, unlabeled A000088.

A105784 counts acyclic covering graphs, unlabeled A144958.

Cf. A000272, A053530, A121251, A137916, A367868, A369199, A372191.

Programs

Mathematica

cys[y_]:=Select[Subsets[Union@@y,{3}], MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[cys[#]]==k&]], {n,0,5},{k,0,Binomial[n,3]}]

Formula

Inverse binomial transform of columns of A372170.

Extensions

a(42) onwards from Andrew Howroyd, Dec 29 2024