A372168 Number of triangle-free simple labeled graphs covering n vertices.

1, 0, 1, 3, 22, 237, 3961, 99900, 3757153, 208571691, 16945953790, 1999844518737, 340422874696873, 83041703920313712, 28850117307732482737, 14191512425207950473867, 9829313296102303971441502

Offset

0,4

Comments

The unlabeled version is A372169.

Links

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

Eric Weisstein's World of Mathematics, Triangle-Free Graph

Formula

Binomial transform is A213434.

Example

The a(4) = 22 graphs are:
  12-34
  13-24
  14-23
  12-13-14
  12-13-24
  12-13-34
  12-14-23
  12-14-34
  12-23-24
  12-23-34
  12-24-34
  13-14-23
  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[#]]==0&]], {n, 0, 5}]

Crossrefs

Dominated by A006129, unlabeled A002494.

For all cycles (not just triangles) we have A105784, unlabeled A144958.

Covering case of A213434 (column k = 0 of A372170, unlabeled A263340).

The connected case is A345218, unlabeled A024607.

Column k = 0 of A372167, unlabeled A372173.

The unlabeled version is A372169.

For a unique triangle we have A372171, non-covering A372172.

A000088 counts unlabeled graphs, labeled A006125.

A001858 counts acyclic graphs, unlabeled A005195.

A054548 counts covering graphs by number of edges, unlabeled A370167.

Cf. A000272, A053530, A121251, A367862, A367863, A372191, A372174, A372175.

Sequence in context: A161567 A213109 A141006 * A367835 A374316 A042703

Adjacent sequences: A372165 A372166 A372167 * A372169 A372170 A372171

Keyword

nonn,more

Author

Gus Wiseman, Apr 23 2024

Status

approved