login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137886 Number of (directed) Hamiltonian paths in the n-crown graph. 3
12, 144, 3840, 138240, 6804000, 436504320, 35417088000, 3546005299200, 429451518988800, 61883150757120000, 10463789706751180800, 2051763183437532364800, 461802751261297205760000, 118254166096501129863168000 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,1

COMMENTS

The reference to A094047 arises in the formula because that sequence is also the number of directed Hamilton 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

Andrew Howroyd, Table of n, a(n) for n = 3..50

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, A270174.

Sequence in context: A123237 A143248 A138444 * A097303 A067219 A075619

Adjacent sequences:  A137883 A137884 A137885 * A137887 A137888 A137889

KEYWORD

nonn,changed

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 10:59 EDT 2017. Contains 292518 sequences.