%I A000179 M2062 N0815
%S A000179 1,0,0,1,2,13,80,579,4738,43387,439792,4890741,59216642,775596313,
%T A000179 10927434464,164806435783,2649391469058,45226435601207,817056406224416,
%U A000179 15574618910994665,312400218671253762,6577618644576902053
%N A000179 Menage numbers: number of permutations s of [0, ..., n-1] such that s(i) 
               != i and s(i) != i+1 (mod n) for all i.
%D A000179 W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 
               13th Ed. Dover, p. 50.
%D A000179 Bogart, Kenneth P. and Doyle, Peter G., Nonsexist solution of the menage 
               problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
%D A000179 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).
%D A000179 I. Kaplansky, Solution of the "probleme des menages", Bull. Amer. Math. 
               Soc. 49, (1943). 784-785.
%D A000179 I. Kaplansky, Symbolic solution of certain problems in permutations, 
               Bull. Amer. Math. Soc., 50 (1944), 906-914.
%D A000179 Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta 
               Math. 12, (1946). 113-124.
%D A000179 P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and 
               New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.
%D A000179 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 
               197.
%D A000179 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000179 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000179 H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.
%D A000179 J. Touchard, Permutations discordant with two given permutations, Scripta 
               Math., 19 (1953), 108-119.
%D A000179 M. Wyman and L. Moser, On the probleme des menages, Canad. J. Math., 
               10 (1958), 468-480.
%H A000179 T. D. Noe, <a href="b000179.txt">Table of n, a(n) for n=0..100</a>
%H A000179 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               372
%H A000179 Nick Hobson, <a href="a000179.py.txt">Python program for this sequence</
               a>
%H A000179 A. R. Kr\"auter, <a href="http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html">
               \"Uber die Permanente gewisser zirkul\"arer Matrizen...</a>
%H A000179 E. Lucas, <a href="http://gallica.bnf.fr/scripts/ConsultationTout.exe?E=0&O=N029021">
               Th\'{e}orie des Nombres</a>. Gauthier-Villars, Paris, 1891, Vol. 
               1, p. 495.
%H A000179 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               MarriedCouplesProblem.html">Link to a section of The World of Mathematics.</
               a>
%H A000179 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               RooksProblem.html">Link to a section of The World of Mathematics.</
               a>
%F A000179 a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4(-1)^n)/(n-2) for n >= 4.
%F A000179 a(n) = Sum {0<=k<=n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k) - 
               Touchard.
%F A000179 G.f.: x+(1-x)/(1+x)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic (vladeta(AT)eunet.rs), 
               Jun 26 2007
%e A000179 a(0) = 1; () works. a(1) = 0; nothing works. a(2) = 0; nothing works. 
               a(3) = 1; (201) works. a(4) = 2; (2301), (3012) work. a(5) = 13; 
               (20413), (23401), (24013), (24103), (30412), (30421), (34012), (34021), 
               (34102), (40123), (43012), (43021), (43102) work.
%p A000179 A000179 := n -> add ((-1)^k*(2*n)*binomial(2*n-k,k)*(n-k)!/(2*n-k), k=0..n); 
               # for n >= 2
%p A000179 U := proc(n) local k; add( (2*n/(2*n-k))*binomial(2*n-k,k)*(n-k)!*(x-1)^k, 
               k=0..n); end; W := proc(r,s) coeff( U(r),x,s ); end; A000179 := n->
               W(n,0); # valid for n >= 2
%o A000179 (PARI) {a(n) = local(A); if( n<3, n==0, A = vector(n); A[3] = 1; for(k=4, 
               n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); 
               A[n])} /* Michael Somos Jan 22 2008 */
%Y A000179 Diagonal of A058087. Equals A059375(n)/(2*n!).
%Y A000179 Sequence in context: A135167 A037491 A037571 this_sequence A037739 A037634 
               A074581
%Y A000179 Adjacent sequences: A000176 A000177 A000178 this_sequence A000180 A000181 
               A000182
%K A000179 nonn,nice,easy
%O A000179 0,5
%A A000179 N. J. A. Sloane (njas(AT)research.att.com).
%E A000179 More terms from James A. Sellers (sellersj(AT)math.psu.edu), May 02 2000
%E A000179 Additional comments from David W. Wilson, Feb 18, 2003