login
Number of ménage permutations.
(Formerly M1524 N0597)
1

%I M1524 N0597 #33 Aug 03 2015 12:25:01

%S 1,2,5,20,87,616,4843,44128,444621,4936274,59661265,780547332,

%T 10987097799,165587196328,2660378564791,45392026278108,

%U 819716784789209,15620011000052754,313219935456572497,6593238656843759572

%N Number of ménage permutations.

%D C. Berge, Principles of Combinatorics, Academic Press, NY, 1971, p. 162.

%D E. N. Gilbert, Knots and classes of menage permutations, Scripta Math., 22 (1956), 228-233 (1957).

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 195.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A002484/b002484.txt">Table of n, a(n) for n = 3..200</a>

%H E. N. Gilbert, <a href="/A002484/a002484.pdf">Knots and classes of menage permutations</a> [Annotated scanned copy of preprint]

%F Gilbert gives a formula (see Maple code).

%F a(n) ~ (n-1)! * exp(-2). - _Vaclav Kotesovec_, May 23 2014

%p with(numtheory): d := n->divisors(n): U := (m,t)->sum(2*m*binomial(2*m-k,k)*(m-k)!*(t-1)^k/(2*m-k),k=0..m): A := (n,i)->phi(n/dd[i])*(n/dd[i])^dd[i]*U(dd[i],1-dd[i]/n)/n: for n from 3 to 28 do dd := d(n): B := [seq(A(n,j),j=1..nops(dd))]: a[n] := sum(B[i],i=1..nops(B)) od: seq(a[n],n=3..28); # _Emeric Deutsch_, Mar 08 2004

%t u[m_, t_] := Sum[ 2m*Binomial[ 2m-k, k]*(m-k)!*((t-1)^k / (2m-k)), {k, 0, m}]; a[n_] := Sum[ EulerPhi[n/d] * (n/d)^d * (u[d, 1-d/n]/n), {d, Divisors[n]} ]; Table[ a[n], {n, 3, 22} ] (* _Jean-François Alcover_, Dec 07 2011, after Maple *)

%Y Cf. A000179.

%K nonn,nice,easy

%O 3,2

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, Mar 08 2004