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

 

Logo


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)
49

%I M2062 N0815

%S 1,0,0,1,2,13,80,579,4738,43387,439792,4890741,59216642,775596313,

%T 10927434464,164806435783,2649391469058,45226435601207,

%U 817056406224416,15574618910994665,312400218671253762,6577618644576902053,145051250421230224304,3343382818203784146955,80399425364623070680706,2013619745874493923699123

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

%C According to rook theory, J. Riordan considered a(1) to be -1; see A102761. - _Vladimir Shevelev_, Apr 02 2010

%C 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

%C Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare A186638. - _N. J. A. Sloane_, Feb 24 2011

%C Sequence discovered by Touchard in 1934. - _L. Edson Jeffery_, Nov 13 2013

%C Although these are also known as Touchard numbers, the problem was formulated by Lucas in 1891, who gave the recurrence formula shown below. See Cerasoli et al., 1988. - _Stanislav Sykora_, Mar 14 2014

%C From _Vladimir Shevelev_, Jun 25 2015: (Start)

%C According to the ménage problem, 2*n!*a(n) is the number of ways of seating n married couples at 2*n chairs around a circular table, men and women in alternate positions, so that no husband is next to his wife.

%C It is known [Riordan, ch. 7] that a(n) is the number of arrangements of n non-attacking rooks on the positions of the 1's in an n X n (0,1)-matrix A_n with 0's in positions (i,i), i = 1,...,n, (i,i+1), i = 1,...,n-1, and (n,1). This statement could be written as a(n) = per(A_n). For example, A_5 has the form

%C 001*11

%C 1*0011

%C 11001* (1)

%C 11*100

%C 0111*0,

%C where 5 non-attacking rooks are denoted by {1*}.

%C We can indicate a one-to-one correspondence between arrangements of n non-attacking rooks on the 1's of a matrix A_n and arrangements of n married couples around a circular table by the rules of the ménage problem, after the ladies w_1, w_2,..., w_n have taken the chairs numbered

%C 2*n, 2, 4, ..., 2*n-2 (2)

%C respectively. Suppose we consider an arrangement of rooks: (1,j_1), (2,j_2),..., (n,j_n). Then the men m_1, m_2,..., m_n took chairs with numbers

%C 2*j_i - 3 (mod 2*n), (3)

%C where the residues are chosen from the interval[1,2*n]. Indeed {j_i} is a permutation of 1,...,n. So {2*j_i-3}(mod 2*n) is a permutation of odd positive integers <= 2*n-1. Besides, the distance between m_i and w_i cannot be 1. Indeed, the equality |2*(j_i-i)-1| = 1 (mod 2*n) is possible if and only if either j_i=i or j_i=i+1 (mod n) that correspond to positions of 0's in matrix A_n.

%C For example, in the case of positions of {1*} in(1) we have j_1=3, j_2=1, j_3=5, j_4=2, j_5=4. So, by(2) and (3) the chairs 1,2,...,10 are taken by m_4, w_2, m_1, w_3, m_5, w_4, m_3, w_5, m_2, w_1, respectively. (End)

%C The first 20 terms of this sequence were calculated in 1891 by E. Lucas (see [Lucas, p. 495]). - _Peter J. C. Moses_, Jun 26 2015

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

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

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

%D Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124.

%D E. Lucas, Théorie des nombres, Paris, 1891, pp. 491-495.

%D 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 T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - _N. J. A. Sloane_, Feb 24 2011

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

%D 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.

%D J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119.

%H Seiichi Manyama, <a href="/A000179/b000179.txt">Table of n, a(n) for n = 0..450</a> (terms 0..100 from T. D. Noe)

%H M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:<a href="http://doi.org/10.1007/978-3-319-44543-4_12">10.1007/978-3-319-44543-4_12</a> arXiv:<a href="http://arxiv.org/abs/1510.07926">1510.07926</a>, [math.CO], 2015-2016.

%H Vladimir Baltic, <a href="https://doi.org/10.2298/AADM1000008B">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135.

%H Kenneth P. Bogart and Peter G. Doyle, <a href="http://www.jstor.org/stable/2323022">Nonsexist solution of the ménage problem</a>, Amer. Math. Monthly 93 (1986), no. 7, 514-519.

%H A. de Gennaro, <a href="https://arxiv.org/abs/0711.0527">How many latin rectangles are there?</a>, arXiv:0711.0527 [math.CO] (2007), see p. 2.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 372

%H Nick Hobson, <a href="/A000179/a000179.py.txt">Python program for this sequence</a>

%H Irving Kaplansky, <a href="http://projecteuclid.org/euclid.bams/1183505432">Solution of the "Problème des ménages"</a>, Bull. Amer. Math. Soc. 49, (1943). 784-785.

%H Irving Kaplansky, <a href="http://projecteuclid.org/euclid.bams/1183506627">Symbolic solution of certain problems in permutations</a>, Bull. Amer. Math. Soc., 50 (1944), 906-914.

%H S. M. Kerawala, <a href="/A001569/a001569.pdf">Asymptotic solution of the "Probleme des menages</a>, Bull. Calcutta Math. Soc., 39 (1947), 82-84. [Annotated scanned copy]

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 221.

%H A. R. Kräuter, <a href="http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html">Über die Permanente gewisser zirkulärer Matrizen...</a>, Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp.

%H Y. Li, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Li2/li51.html">Ménage Numbers and Ménage Permutations</a>, J. Int. Seq. 18 (2015) 15.6.8

%H E. Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k29021h">Théorie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.

%H Vladimir Shevelev, Peter J. C. Moses, <a href="https://arxiv.org/abs/1101.5321">The ménage problem with a known mathematician</a>, arXiv:1101.5321 [math.CO], 2011, 2015.

%H Vladimir Shevelev and Peter J. C. Moses, <a href="http://www.emis.de/journals/INTEGERS/papers/q72/q72.Abstract.html">Alice and Bob go to dinner: A variation on menage</a>, INTEGERS, Vol. 16 (2016), #A72.

%H R. J. Stones, S. Lin, X. Liu, G. Wang, <a href="https://dx.doi.org/10.1007/s00373-015-1643-1">On Computing the Number of Latin Rectangles</a>, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1.

%H H. M. Taylor, <a href="/A000179/a000179.pdf">A problem on arrangements</a>, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]

%H J. Touchard, <a href="http://visualiseur.bnf.fr/ark:/12148/bpt6k31506">Théorie des substitutions. Sur un problème de permutations</a>, C. R. Acad. Sci. Paris 198 (1934), 631-633.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MarriedCouplesProblem.html">Married Couples Problem</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RooksProblem.html">Rooks Problem</a>

%H M. Wyman and L. Moser, <a href="http://dx.doi.org/10.4153/CJM-1958-045-6">On the problème des ménages</a>, Canad. J. Math., 10 (1958), 468-480.

%H D. Zeilberger, <a href="https://arxiv.org/abs/1401.1089">Automatic Enumeration of Generalized Menage Numbers</a>, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

%F a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4(-1)^n)/(n-2) for n >= 4.

%F a(n) = A059375(n)/(2*n!).

%F a(n) = Sum {0<=k<=n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k). - Touchard (1934)

%F G.f.: x+(1-x)/(1+x)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 26 2007

%F a(2^k+2)==0 (mod 2^k); for k>=2, a(2^k)==2(mod 2^k). - _Vladimir Shevelev_, Jan 14 2011

%F a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n>0. - _Mark van Hoeij_, Oct 25 2011

%F a(n) ~ (n/e)^n * sqrt(2*Pi*n)/e^2. - _Charles R Greathouse IV_, Jan 21 2016

%F 0 = a(n)*(-a(n+2) +a(n+4)) +a(n+1)*(+a(n+1) +a(n+2) -3*a(n+3) -5*a(n+4) +a(n+5)) +a(n+2)*(+2*a(n+2) +3*a(n+3) -3*a(n+4)) +a(n+3)*(+2*a(n+3) +a(n+4) -a(n+5)) +a(n+4)*(+a(n+4)), for all n>1. If a(-2..1) = (0, -1, 2, -1) then also true for those values of n. - _Michael Somos_, Apr 29 2018

%F 0 = a(n) +n*a(n+1) -2*a(n+2) +(-n-4)*a(n+3) +a(n+4), for all n in Z where a(n) = a(-n) for all n in Z and a(0) = 2, a(1) = -1. - _Michael Somos_, May 02 2018

%e 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 := n -> add ((-1)^k*(2*n)*binomial(2*n-k,k)*(n-k)!/(2*n-k), k=0..n); # for n >= 2

%p 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

%t 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 *)

%o (PARI) {a(n) = my(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 */

%o (PARI) a(n)=if(n,round(2*n*exp(-2)*besselk(n,2)),1) \\ _Charles R Greathouse IV_, Nov 03 2014

%o (PARI) {a(n) = my(A); if( n<3, n==0, n==3, 1, n==4, 2, A = vector(n); A[1] = -1; A[3] = 1; A[4] = 2; for(k=5, n, A[k] = k * A[k-1] + 2 * A[k-2] + (4-k) * A[k-3] - A[k-4]); A[n])}; /* _Michael Somos_, May 02 2018 */

%o (Haskell)

%o import Data.List (zipWith5)

%o a000179 n = a000179_list !! n

%o a000179_list = 1 : 0 : 0 : 1 : zipWith5

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

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

%o -- _Reinhard Zumkeller_, Aug 26 2013

%Y Diagonal of A058087. Also a diagonal of A008305.

%Y Cf. A000904, A059375, A102761, A000186, A094047, A067998, A033999, A258664, A258665, A258666, A258667, A258673, A259212.

%K nonn,nice,easy

%O 0,5

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, May 02 2000

%E Additional comments from _David W. Wilson_, Feb 18 2003

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 21 22:52 EDT 2018. Contains 313958 sequences. (Running on oeis4.)