

A326214


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


6




OFFSET

0,3


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

A002416(n) = a(n) + A326213(n).


EXAMPLE

The a(2) = 12 edgesets:
{12}
{21}
{11,12}
{11,21}
{12,21}
{12,22}
{21,22}
{11,12,21}
{11,12,22}
{11,21,22}
{12,21,22}
{11,12,21,22}


MATHEMATICA

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


CROSSREFS

The unlabeled case is A326221.
The undirected case is A326206.
The case without loops is A326217.
Digraphs not containing a Hamiltonian path are A326213.
Digraphs containing a Hamiltonian cycle are A326204.
Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.
Sequence in context: A251590 A196459 A193132 * A187513 A138914 A326220
Adjacent sequences: A326211 A326212 A326213 * A326215 A326216 A326217


KEYWORD

nonn,more


AUTHOR

Gus Wiseman, Jun 15 2019


STATUS

approved



