A326214 Number of labeled n-vertex digraphs (with loops) containing a (directed) Hamiltonian path.

0, 0, 12, 384, 53184

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Comments

A path is Hamiltonian if it passes through every vertex exactly once.

Examples

			The a(2) = 12 edge-sets:
  {12}
  {21}
  {11,12}
  {11,21}
  {12,21}
  {12,22}
  {21,22}
  {11,12,21}
  {11,12,22}
  {11,21,22}
  {12,21,22}
  {11,12,21,22}
		

Links

• Wikipedia, Hamiltonian path
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Crossrefs

The unlabeled case is A326221.

The undirected case is A326206.

The case without loops is A326217.

Digraphs not containing a Hamiltonian path are A326213.

Digraphs containing a Hamiltonian cycle are A326204.

Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.

Programs

Mathematica

Table[Length[Select[Subsets[Tuples[Range[n],2]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,4}] (* Mathematica 10.2+ *)

Formula

A002416(n) = a(n) + A326213(n).