A326213 - OEIS

%I #13 Jun 11 2024 15:37:41

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

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

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

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>

%H Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.

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

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

%Y The unlabeled case is A326224.

%Y The case without loops is A326216.

%Y Digraphs containing a Hamiltonian path are A326214.

%Y Digraphs not containing a Hamiltonian cycle are A326220.

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

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Jun 15 2019

%E a(5)-a(6) from _Bert Dobbelaere_, Jun 11 2024