cp's OEIS Frontend

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

%I A326216 #15 Aug 23 2023 08:35:34
%S A326216 1,1,1,16,772
%N A326216 Number of labeled n-vertex digraphs (without loops) not containing a (directed) Hamiltonian path.
%C A326216 A path is Hamiltonian if it passes through every vertex exactly once.
%H A326216 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>
%H A326216 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 A326216 A053763(n) = a(n) + A326217(n).
%e A326216 The a(3) = 16 edge-sets:
%e A326216   {}  {12}  {12,13}
%e A326216       {13}  {12,21}
%e A326216       {21}  {12,32}
%e A326216       {23}  {13,23}
%e A326216       {31}  {13,31}
%e A326216       {32}  {21,23}
%e A326216             {21,31}
%e A326216             {23,32}
%e A326216             {31,32}
%t A326216 Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]=={}&]],{n,4}] (* Mathematica 10.2+ *)
%Y A326216 Unlabeled digraphs not containing a Hamiltonian path are A326224.
%Y A326216 The undirected case is A326205.
%Y A326216 The unlabeled undirected case is A283420.
%Y A326216 The case with loops is A326213.
%Y A326216 Digraphs (without loops) containing a Hamiltonian path are A326217.
%Y A326216 Digraphs (without loops) not containing a Hamiltonian cycle are A326218.
%Y A326216 Cf. A000595, A002416, A003024, A003216, A057864, A326206, A326214, A326220, A326221, A326225.
%K A326216 nonn,more
%O A326216 0,4
%A A326216 _Gus Wiseman_, Jun 15 2019