|
Search: id:A000179
|
|
|
| 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)
|
|
+0
20
|
|
| 1, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053
(list; graph; listen)
|
|
|
OFFSET
|
0,5
|
|
|
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.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
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, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
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 (vladeta(AT)eunet.rs), Jun 26 2007
|
|
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
|
|
PROGRAM
|
(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!).
Sequence in context: A135167 A037491 A037571 this_sequence A037739 A037634 A074581
Adjacent sequences: A000176 A000177 A000178 this_sequence A000180 A000181 A000182
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
More terms from James A. Sellers (sellersj(AT)math.psu.edu), May 02 2000
Additional comments from David W. Wilson, Feb 18, 2003
|
|
|
Search completed in 0.002 seconds
|
