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

1, 2, 4, 128, 12352, 3826272, 3775441536

Offset

0,2

Comments

A path is Hamiltonian if it passes through every vertex exactly once.

Links

Table of n, a(n) for n=0..6.

Wikipedia, Hamiltonian path

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Formula

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

Mathematica

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

Crossrefs

The unlabeled case is A326224.

The case without loops is A326216.

Digraphs containing a Hamiltonian path are A326214.

Digraphs not containing a Hamiltonian cycle are A326220.

Cf. A000595, A002416, A003024, A003216, A057864, A283420, A326204, A326206, A326221.

Sequence in context: A376315 A134710 A009073 * A369699 A012561 A012558

Adjacent sequences: A326210 A326211 A326212 * A326214 A326215 A326216

Keyword

nonn,more

Author

Gus Wiseman, Jun 15 2019

Extensions

a(5)-a(6) from Bert Dobbelaere, Jun 11 2024

Status

approved