cp's OEIS Frontend

A137886 Number of (directed) Hamiltonian paths in the n-crown graph.

%I A137886 #41 Feb 16 2025 08:33:07
%S A137886 12,144,3840,138240,6804000,436504320,35417088000,3546005299200,
%T A137886 429451518988800,61883150757120000,10463789706751180800,
%U A137886 2051763183437532364800,461802751261297205760000,118254166096501129863168000
%N A137886 Number of (directed) Hamiltonian paths in the n-crown graph.
%C A137886 The reference to A094047 arises in the formula because that sequence is also the number of directed Hamiltonian cycles in the n-crown graph. (Each cycle can be broken in 2n ways to give a path.) - _Andrew Howroyd_, Feb 21 2016
%C A137886 Also, the number of ways of seating n married couples at 2*n chairs arranged side-by-side in a straight line, men and women in alternate positions, so that no husband is next to his wife. - _Andrew Howroyd_, Sep 19 2017
%H A137886 Seiichi Manyama, <a href="/A137886/b137886.txt">Table of n, a(n) for n = 3..253</a> (terms 3..50 from Andrew Howroyd)
%H A137886 Max Alekseyev, <a href="http://home.gwu.edu/~maxal/gpscripts/">PARI/GP Scripts for Miscellaneous Math Problems</a>
%H A137886 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CrownGraph.html">Crown Graph</a>
%H A137886 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>
%F A137886 For n>3, a(n) = 2*n*A094047(n) + n*a(n-1) = A059375(n) + n*a(n-1). - _Andrew Howroyd_, Feb 21 2016
%F A137886 a(n) ~ 4*Pi*n^(2*n+1) / exp(2*n+2). - _Vaclav Kotesovec_, Feb 25 2016
%F A137886 a(n) = (n-1)*n*a(n-1) + (n-1)^2*n*a(n-2) + (n-2)*(n-1)*n*a(n-3). - _Vaclav Kotesovec_, Feb 25 2016
%F A137886 a(n) = 2*n! * A000271(n). - _Andrew Howroyd_, Sep 19 2017
%t A137886 Table[2 n! Sum[(-1)^(n - k) k! Binomial[n + k, 2 k], {k, 0, n}], {n, 3, 20}] (* _Eric W. Weisstein_, Sep 20 2017 *)
%t A137886 Table[2 (-1)^n n! HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 3, 20}] (* _Eric W. Weisstein_, Sep 20 2017 *)
%o A137886 (PARI) /* needs the routine nhp() from the Alekseyev link */
%o A137886 { A137886(n) = nhp( matrix(2*n,2*n,i,j, if(min(i,j)<=n && max(i,j)>n && abs(j-i)!=n, 1, 0)) ) }
%Y A137886 Cf. A000271, A059375, A094047, A259212, A270174.
%K A137886 nonn
%O A137886 3,1
%A A137886 _Eric W. Weisstein_, Feb 20 2008
%E A137886 More terms from _Max Alekseyev_, Feb 13 2009
%E A137886 a(14) from _Eric W. Weisstein_, Jan 15 2014
%E A137886 a(15)-a(16) from _Andrew Howroyd_, Feb 21 2016