A372175 Irregular triangle read by rows where T(n,k) is the number of labeled simple graphs covering n vertices with exactly 2k directed cycles of length > 2.

1, 0, 1, 3, 1, 19, 15, 0, 6, 0, 0, 0, 1, 155, 232, 15, 190, 0, 0, 70, 50, 0, 0, 0, 0, 30, 15, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset

0,4

Comments

A directed cycle in a simple (undirected) graph is a sequence of distinct vertices, up to rotation, such that there are edges between all consecutive elements, including the last and the first.

Links

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

Example

Triangle begins (zeros shown as dots):
  1
  .
  1
  3 1
  19 15 . 6 ... 1
  155 232 15 190 .. 70 50 .... 30 15 .......... 10 .............. 1
Row n = 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,13,24,34     13,14,23,24,34
  12,14,23  12,14,23,24
  12,14,34  12,14,23,34
  12,23,24  12,14,24,34
  12,23,34  12,23,24,34
  12,24,34  13,14,23,24
  13,14,23  13,14,23,34
  13,14,24  13,14,24,34
  13,23,24  13,23,24,34
  13,23,34  14,23,24,34
  13,24,34
  14,23,24
  14,23,34
  14,24,34

Mathematica

cycles[g_]:=Join@@Table[Select[Join@@Permutations /@ Subsets[Union@@g, {k}], Min@@#==First[#]&&And@@Table[MemberQ[Sort/@g, Sort[{#[[i]], #[[If[i==k, 1, i+1]]]}]], {i, k}]&], {k, 3, Length[g]}];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[cycles[#]]==2k&]], {n, 0, 5}, {k, 0, Length[cycles[Subsets[Range[n], {2}]]]/2}]

Crossrefs

Row lengths are A002807 + 1.

Row sums are A006129, unlabeled A002494.

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

Counting triangles instead of cycles gives A372167 (non-covering A372170), unlabeled A372173 (non-covering A263340).

The non-covering version is A372176.

Column k = 1 is A372195 (non-covering A372193, for triangles A372171), unlabeled A372191 (non-covering A372192, for triangles A372174).

A000088 counts unlabeled graphs, labeled A006125.

A001858 counts acyclic graphs, unlabeled A005195.

A322661 counts covering loop-graphs, unlabeled A322700.

Cf. A000272, A053530, A121251, A137916, A137917, A372172, A372194.

Sequence in context: A188109 A247232 A147076 * A027537 A192721 A370949

Adjacent sequences: A372172 A372173 A372174 * A372176 A372177 A372178

Keyword

nonn,more,tabf,new

Author

Gus Wiseman, Apr 24 2024

Status

approved