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

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

Offset

0,4

Links

Table of n, a(n) for n=0..41.

Gus Wiseman, All simple graphs covering {1,2,3,4} grouped by number of triangles.

Formula

Inverse binomial transform of columns of A372170.

Example

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

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]}]

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.

Sequence in context: A346214 A190962 A010291 * A370948 A306619 A335644

Adjacent sequences: A372164 A372165 A372166 * A372168 A372169 A372170

Keyword

nonn,tabf,more

Author

Gus Wiseman, Apr 23 2024

Status

approved