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

1, 1, 2, 7, 1, 38, 19, 0, 6, 0, 0, 0, 1, 291, 317, 15, 220, 0, 0, 70, 55, 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

Author

Gus Wiseman, Apr 25 2024

Keywords

• nonn
• tabf
• more

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.

Examples

			Triangle begins (zeros shown as dots):
   1
   1
   2
   7 1
   38 19 . 6 ... 1
   291 317 15 220 .. 70 55 .... 30 15 ........ 10 ............... 1
The T(4,3) = 6 graphs:
  12,13,14,23,24
  12,13,14,23,34
  12,13,14,24,34
  12,13,23,24,34
  12,14,23,24,34
  13,14,23,24,34
		

Crossrefs

Column k = 0 is A001858 (unlabeled A005195), covering A105784.

Row lengths are A002807 + 1.

Row sums are A006125, unlabeled A000088.

Counting edges instead of cycles gives A084546 (covering A054548), unlabeled A008406 (covering A370167).

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

The covering case is A372175.

Column k = 1 is A372193 (covering A372195), unlabeled A236570.

A006129 counts graphs, unlabeled A002494.

A322661 counts covering loop-graphs, unlabeled A322700.

Cf. A000272, A053530, A137916, A144958, A213434, A367863, A372168, A372169, A372171, A372172, A372191.

Programs

Mathematica

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