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

1, 1, 1, 16, 772

Offset

0,4

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

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

Example

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}

Mathematica

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

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.

Sequence in context: A134183 A042109 A221061 * A194610 A215171 A224736

Adjacent sequences: A326213 A326214 A326215 * A326217 A326218 A326219

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Status

approved