A326217 Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.

0, 0, 3, 48, 3324, 929005, 1014750550, 4305572108670

Offset

0,3

Links

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

Wikipedia, Hamiltonian path

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

Formula

A053763(n) = a(n) + A326216(n).

Example

The a(3) = 48 edge-sets:
  {12,23}  {12,13,21}  {12,13,21,23}  {12,13,21,23,31}  {12,13,21,23,31,32}
  {12,31}  {12,13,23}  {12,13,21,31}  {12,13,21,23,32}
  {13,21}  {12,13,31}  {12,13,21,32}  {12,13,21,31,32}
  {13,32}  {12,13,32}  {12,13,23,31}  {12,13,23,31,32}
  {21,32}  {12,21,23}  {12,13,23,32}  {12,21,23,31,32}
  {23,31}  {12,21,31}  {12,13,31,32}  {13,21,23,31,32}
           {12,21,32}  {12,21,23,31}
           {12,23,31}  {12,21,23,32}
           {12,23,32}  {12,21,31,32}
           {12,31,32}  {12,23,31,32}
           {13,21,23}  {13,21,23,31}
           {13,21,31}  {13,21,23,32}
           {13,21,32}  {13,21,31,32}
           {13,23,31}  {13,23,31,32}
           {13,23,32}  {21,23,31,32}
           {13,31,32}
           {21,23,31}
           {21,23,32}
           {21,31,32}
           {23,31,32}

Mathematica

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

Crossrefs

The undirected case is A326206.

The unlabeled undirected case is A057864.

The case with loops is A326214.

Unlabeled digraphs with a Hamiltonian path are A326221.

Digraphs (without loops) not containing a Hamiltonian path are A326216.

Digraphs (without loops) containing a Hamiltonian cycle are A326219.

Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, A326225.

Sequence in context: A201698 A356612 A295813 * A003029 A049524 A270748

Adjacent sequences: A326214 A326215 A326216 * A326218 A326219 A326220

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Extensions

a(5)-a(7) from Bert Dobbelaere, Feb 21 2023

Status

approved