|
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.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
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.
P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..100
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.
A. R. Kr\"auter, \"Uber die Permanente gewisser zirkul\"arer Matrizen...
Nick Hobson, Python program for this sequence
|
|
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.yu), 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
|
njas
|
|
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.003 seconds
|
