cp's OEIS Frontend

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

%I A326217 #12 Aug 23 2023 08:36:41
%S A326217 0,0,3,48,3324,929005,1014750550,4305572108670
%N A326217 Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.
%H A326217 Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a>
%H A326217 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 A326217 A053763(n) = a(n) + A326216(n).
%e A326217 The a(3) = 48 edge-sets:
%e A326217   {12,23}  {12,13,21}  {12,13,21,23}  {12,13,21,23,31}  {12,13,21,23,31,32}
%e A326217   {12,31}  {12,13,23}  {12,13,21,31}  {12,13,21,23,32}
%e A326217   {13,21}  {12,13,31}  {12,13,21,32}  {12,13,21,31,32}
%e A326217   {13,32}  {12,13,32}  {12,13,23,31}  {12,13,23,31,32}
%e A326217   {21,32}  {12,21,23}  {12,13,23,32}  {12,21,23,31,32}
%e A326217   {23,31}  {12,21,31}  {12,13,31,32}  {13,21,23,31,32}
%e A326217            {12,21,32}  {12,21,23,31}
%e A326217            {12,23,31}  {12,21,23,32}
%e A326217            {12,23,32}  {12,21,31,32}
%e A326217            {12,31,32}  {12,23,31,32}
%e A326217            {13,21,23}  {13,21,23,31}
%e A326217            {13,21,31}  {13,21,23,32}
%e A326217            {13,21,32}  {13,21,31,32}
%e A326217            {13,23,31}  {13,23,31,32}
%e A326217            {13,23,32}  {21,23,31,32}
%e A326217            {13,31,32}
%e A326217            {21,23,31}
%e A326217            {21,23,32}
%e A326217            {21,31,32}
%e A326217            {23,31,32}
%t A326217 Table[Length[Select[Subsets[Select[Tuples[Range[n],2],UnsameQ@@#&]],FindHamiltonianPath[Graph[Range[n],DirectedEdge@@@#]]!={}&]],{n,4}] (* Mathematica 10.2+ *)
%Y A326217 The undirected case is A326206.
%Y A326217 The unlabeled undirected case is A057864.
%Y A326217 The case with loops is A326214.
%Y A326217 Unlabeled digraphs with a Hamiltonian path are A326221.
%Y A326217 Digraphs (without loops) not containing a Hamiltonian path are A326216.
%Y A326217 Digraphs (without loops) containing a Hamiltonian cycle are A326219.
%Y A326217 Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, A326225.
%K A326217 nonn,more
%O A326217 0,3
%A A326217 _Gus Wiseman_, Jun 15 2019
%E A326217 a(5)-a(7) from _Bert Dobbelaere_, Feb 21 2023