

A326216


Number of labeled nvertex digraphs (without loops) not containing a (directed) Hamiltonian path.


6




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 ecoefficients of incomparability graphs.


FORMULA

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


EXAMPLE

The a(3) = 16 edgesets:
{} {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



