login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000179 Ménage 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)
29
1, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

According to rook theory, J. Riordan considered a(1) to be -1. - Vladimir Shevelev, Apr 02 2010

Or, for n>=3, the number of 3 X n 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. - 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

Sequence discovered by Touchard in 1934. - L. Edson Jeffery, Nov 13 2013

Actually, though theses are known as Touchard numbers, the problem was formulated by Lucas in 1891, who gave the first recurrence formula shown below. See Cerasoli et al, 1988. - Stanislav Sykora, Mar 14 2014

REFERENCES

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50.

M. Cerasoli, F. Eugeni and M. Protasi, Elementi di Matematica Discreta, Nicola Zanichelli Editore, Bologna 1988, Chapter 3, p.78.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).

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. - 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. - 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.

LINKS

T. D. Noe, Table of n, a(n) for n=0..100

Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the ménage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519.

A. de Gennaro, How may latin rectangles are there?, arXiv:0711.0527 [math.CO] (2007), see p. 2.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 372

Nick Hobson, Python program for this sequence

Irving Kaplansky, Solution of the "Problème des ménages", Bull. Amer. Math. Soc. 49, (1943). 784-785.

Irving Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914.

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 221.

A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen...

E. Lucas, Th\'{e}orie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.

J. Touchard, Théorie des substitutions. Sur un problème de permutations, C. R. Acad. Sci. Paris 198 (1934), 631-633.

Eric Weisstein's World of Mathematics, Married Couples Problem

Eric Weisstein's World of Mathematics, Rooks Problem

M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089, 2014

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 (1934).

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 */

(Haskell)

import Data.List (zipWith5)

a000179 n = a000179_list !! n

a000179_list = 1 : 0 : 0 : 1 : zipWith5

   (\v w x y z -> (x * y + (v + 2) * z - w) `div` v) [2..] (cycle [4, -4])

   (drop 4 a067998_list) (drop 3 a000179_list) (drop 2 a000179_list)

-- Reinhard Zumkeller, Aug 26 2013

CROSSREFS

Diagonal of A058087. Also a diagonal of A008305. Equals A059375(n)/(2*n!).

Cf. A000186, A094047, A067998, A033999.

Sequence in context: A179237 A216316 A102761 * A246383 A189087 A037739

Adjacent sequences:  A000176 A000177 A000178 * A000180 A000181 A000182

KEYWORD

nonn,nice,easy

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 1 08:43 EDT 2014. Contains 247504 sequences.