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

1, 1, 2, 7, 1, 41, 16, 6, 0, 1, 388, 290, 195, 70, 40, 30, 0, 10, 0, 0, 1, 5789, 6980, 6910, 4560, 3030, 2292, 1230, 780, 600, 180, 236, 60, 45, 60, 0, 0, 15, 0, 0, 0, 1, 133501, 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

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..340 (rows 0..10)

Formula

Binomial transform of columns of A372167.

Example

Triangle begins:
     1
     1
     2
     7    1
    41   16    6    0    1
   388  290  195   70   40   30    0   10    0    0    1
   ...
For example, the T(4,1) = 16 graphs are:
  12-13-23
  12-14-24
  13-14-34
  23-24-34
  12-13-14-23
  12-13-14-24
  12-13-14-34
  12-13-23-24
  12-13-23-34
  12-14-23-24
  12-14-24-34
  12-23-24-34
  13-14-23-34
  13-14-24-34
  13-23-24-34
  14-23-24-34

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}]], Length[cys[#]]==k&]], {n, 0, 5}, {k, 0, Binomial[n, 3]}]

Crossrefs

Row sums are A006125, covering A006129.

Row lengths are A050407.

Counting edges instead of triangles gives A084546, covering A054548.

Column k = 0 is A213434, covering A372168.

The unlabeled version is A263340.

The covering case is A372167, unlabeled A372173.

Column k = 1 is A372172, covering A372171.

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

A001858 counts acyclic graphs, unlabeled A005195.

A367867 counts non-choosable graphs, covering A367868.

A372193 counts unicyclic graphs, unlabeled A236570, covering A372191.

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

Sequence in context: A125699 A372176 A372153 * A369371 A242207 A060465

Adjacent sequences: A372167 A372168 A372169 * A372171 A372172 A372173

Keyword

nonn,tabf

Author

Gus Wiseman, Apr 23 2024

Extensions

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

Status

approved