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

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

Offset: 0

Author

Gus Wiseman, Jun 15 2019

Keywords

• nonn
• more

Examples

			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}
		

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 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.

Programs

Mathematica

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

Formula

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

Extensions

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