A326217 - OEIS

%I #12 Aug 23 2023 08:36:41

%S 0,0,3,48,3324,929005,1014750550,4305572108670

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

%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 A053763(n) = a(n) + A326216(n).

%e The a(3) = 48 edge-sets:

%e   {12,23}  {12,13,21}  {12,13,21,23}  {12,13,21,23,31}  {12,13,21,23,31,32}

%e   {12,31}  {12,13,23}  {12,13,21,31}  {12,13,21,23,32}

%e   {13,21}  {12,13,31}  {12,13,21,32}  {12,13,21,31,32}

%e   {13,32}  {12,13,32}  {12,13,23,31}  {12,13,23,31,32}

%e   {21,32}  {12,21,23}  {12,13,23,32}  {12,21,23,31,32}

%e   {23,31}  {12,21,31}  {12,13,31,32}  {13,21,23,31,32}

%e            {12,21,32}  {12,21,23,31}

%e            {12,23,31}  {12,21,23,32}

%e            {12,23,32}  {12,21,31,32}

%e            {12,31,32}  {12,23,31,32}

%e            {13,21,23}  {13,21,23,31}

%e            {13,21,31}  {13,21,23,32}

%e            {13,21,32}  {13,21,31,32}

%e            {13,23,31}  {13,23,31,32}

%e            {13,23,32}  {21,23,31,32}

%e            {13,31,32}

%e            {21,23,31}

%e            {21,23,32}

%e            {21,31,32}

%e            {23,31,32}

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

%Y The undirected case is A326206.

%Y The unlabeled undirected case is A057864.

%Y The case with loops is A326214.

%Y Unlabeled digraphs with a Hamiltonian path are A326221.

%Y Digraphs (without loops) not containing a Hamiltonian path are A326216.

%Y Digraphs (without loops) containing a Hamiltonian cycle are A326219.

%Y Cf. A000595, A002416, A003024, A003216, A283420, A326204, A326208, A326213, A326225.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Jun 15 2019

%E a(5)-a(7) from _Bert Dobbelaere_, Feb 21 2023