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

1, 1, 1, 16, 772

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(3) = 16 edge-sets:
  {}  {12}  {12,13}
      {13}  {12,21}
      {21}  {12,32}
      {23}  {13,23}
      {31}  {13,31}
      {32}  {21,23}
            {21,31}
            {23,32}
            {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

Unlabeled digraphs not containing a Hamiltonian path are A326224.

The undirected case is A326205.

The unlabeled undirected case is A283420.

The case with loops is A326213.

Digraphs (without loops) containing a Hamiltonian path are A326217.

Digraphs (without loops) not containing a Hamiltonian cycle are A326218.

Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, 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) + A326217(n).