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

12, 144, 3840, 138240, 6804000, 436504320, 35417088000, 3546005299200, 429451518988800, 61883150757120000, 10463789706751180800, 2051763183437532364800, 461802751261297205760000, 118254166096501129863168000

Offset

3,1

Comments

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

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

Links

Seiichi Manyama, Table of n, a(n) for n = 3..253 (terms 3..50 from Andrew Howroyd)

Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems

Eric Weisstein's World of Mathematics, Crown Graph

Eric Weisstein's World of Mathematics, Hamiltonian Path

Formula

For n>3, a(n) = 2*n*A094047(n) + n*a(n-1) = A059375(n) + n*a(n-1). - Andrew Howroyd, Feb 21 2016

a(n) ~ 4*Pi*n^(2*n+1) / exp(2*n+2). - Vaclav Kotesovec, Feb 25 2016

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

a(n) = 2*n! * A000271(n). - Andrew Howroyd, Sep 19 2017

Mathematica

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 *)
Table[2 (-1)^n n! HypergeometricPFQ[{1, -n, n + 1}, {1/2}, 1/4], {n, 3, 20}] (* Eric W. Weisstein, Sep 20 2017 *)

Prog

(PARI) /* needs the routine nhp() from the Alekseyev link */
{ 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)) ) }

Crossrefs

Cf. A000271, A059375, A094047, A259212, A270174.

Sequence in context: A123237 A143248 A138444 * A097303 A067219 A075619

Adjacent sequences: A137883 A137884 A137885 * A137887 A137888 A137889

Keyword

nonn

Author

Eric W. Weisstein, Feb 20 2008

Extensions

More terms from Max Alekseyev, Feb 13 2009

a(14) from Eric W. Weisstein, Jan 15 2014

a(15)-a(16) from Andrew Howroyd, Feb 21 2016

Status

approved