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

0, 0, 12, 384, 53184

Offset

0,3

Comments

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

Links

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

Wikipedia, Hamiltonian path

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

Formula

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

Example

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}

Mathematica

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

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.

Sequence in context: A352651 A196459 A193132 * A187513 A138914 A326220

Adjacent sequences: A326211 A326212 A326213 * A326215 A326216 A326217

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Status

approved