|
| |
|
|
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.
(Formerly M2062 N0815)
|
|
28
|
|
|
|
1, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
According to rook theory, J. Riordan considered a(1) to be -1. [From Vladimir Shevelev, Apr 02 2010]
Or, for n>=3, the number of 3Xn Latin rectangles the second row of which is full cycle with a fixed order of its elements, e.g., the cycle (x_2,x_3,...,x_n,x_1) with x_1<x_2<...<x_n. [From Vladimir Shevelev, Mar 22 2010]
Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare A186638. - N. J. A. Sloane, Feb 24 2011.
|
|
|
REFERENCES
|
W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50.
Bogart, Kenneth P. and Doyle, Peter G., Nonsexist solution of the menage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).
I. Kaplansky, Solution of the "probleme des menages", Bull. Amer. Math. Soc. 49, (1943). 784-785.
I. Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.
Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124.
P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.
T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - From N. J. A. Sloane, Feb 24 2011.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr.Mat.(J. of the Akademy of Sciences of Russia) 4(1992),91-110. [From Vladimir Shevelev, Mar 22 2010]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.
J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119.
M. Wyman and L. Moser, On the probleme des menages, Canad. J. Math., 10 (1958), 468-480.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..100
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 372
Nick Hobson, Python program for this sequence
A. R. Kr\"auter, \"Uber die Permanente gewisser zirkul\"arer Matrizen...
E. Lucas, Th\'{e}orie des Nombres. Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.
Eric Weisstein's World of Mathematics, Married Couples Problem
Eric Weisstein's World of Mathematics, Rooks Problem
|
|
|
FORMULA
|
a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4(-1)^n)/(n-2) for n >= 4.
a(n) = Sum {0<=k<=n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k) - Touchard.
G.f.: x+(1-x)/(1+x)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 26 2007
a(2^k+2)==0 (mod 2^k); for k>=2, a(2^k)==2(mod 2^k). -Vladimir Shevelev, Jan 14 2011
a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n>0. - Mark van Hoeij, Oct 25 2011
|
|
|
EXAMPLE
|
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.
|
|
|
MAPLE
|
A000179 := n -> add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); # for n >= 2
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
|
|
|
MATHEMATICA
|
a[n_] := 2*n*Sum[(-1)^k*Binomial[2*n - k, k]*(n - k)!/(2*n - k), {k, 0, n}]; a[0] = 1; a[1] = 0; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 05 2012, from 2nd formula *)
|
|
|
PROG
|
(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 */
|
|
|
CROSSREFS
|
Diagonal of A058087. Equals A059375(n)/(2*n!).
Cf. A000186 A094047 [From Vladimir Shevelev, Mar 22 2010]
Sequence in context: A179237 A216316 * A102761 A189087 A037739 A037634
Adjacent sequences: A000176 A000177 A000178 * A000180 A000181 A000182
|
|
|
KEYWORD
|
nonn,nice,easy,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from James A. Sellers, May 02 2000
Additional comments from David W. Wilson, Feb 18, 2003
|
|
|
STATUS
|
approved
|
| |
|
|
