A326214 - OEIS

%I #9 Aug 23 2023 08:36:29

%S 0,0,12,384,53184

%N Number of labeled n-vertex digraphs (with loops) 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) + A326213(n).

%e The a(2) = 12 edge-sets:

%e   {12}

%e   {21}

%e   {11,12}

%e   {11,21}

%e   {12,21}

%e   {12,22}

%e   {21,22}

%e   {11,12,21}

%e   {11,12,22}

%e   {11,21,22}

%e   {12,21,22}

%e   {11,12,21,22}

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

%Y The unlabeled case is A326221.

%Y The undirected case is A326206.

%Y The case without loops is A326217.

%Y Digraphs not containing a Hamiltonian path are A326213.

%Y Digraphs containing a Hamiltonian cycle are A326204.

%Y Cf. A000595, A002416, A003024, A003216, A057864, A326224, A326225, A326226.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jun 15 2019