# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a000179 Showing 1-1 of 1 %I A000179 M2062 N0815 #262 Sep 03 2023 23:40:25 %S A000179 1,-1,0,1,2,13,80,579,4738,43387,439792,4890741,59216642,775596313, %T A000179 10927434464,164806435783,2649391469058,45226435601207, %U A000179 817056406224416,15574618910994665,312400218671253762,6577618644576902053,145051250421230224304,3343382818203784146955,80399425364623070680706,2013619745874493923699123 %N A000179 Ménage numbers: a(0) = 1, a(1) = -1, and for n >= 2, a(n) = number of permutations s of [0, ..., n-1] such that s(i) != i and s(i) != i+1 (mod n) for all i. %C A000179 According to rook theory, _John Riordan_ considered a(1) to be -1. - _Vladimir Shevelev_, Apr 02 2010 %C A000179 This is also the value that the formulas of Touchard and of Wyman and Moser give and is compatible with many recurrences. - _William P. Orrick_, Aug 31 2020 %C A000179 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 A000179 Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare A186638. - _N. J. A. Sloane_, Feb 24 2011 %C A000179 Sequence discovered by Touchard in 1934. - _L. Edson Jeffery_, Nov 13 2013 %C A000179 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 A000179 An equivalent problem was formulated by Tait; solutions to Tait's problem were given by Muir (1878) and Cayley (1878). - _William P. Orrick_, Aug 31 2020 %C A000179 From _Vladimir Shevelev_, Jun 25 2015: (Start) %C A000179 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 A000179 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 A000179 001*11 %C A000179 1*0011 %C A000179 11001* (1) %C A000179 11*100 %C A000179 0111*0, %C A000179 where 5 non-attacking rooks are denoted by {1*}. %C A000179 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 A000179 2*n, 2, 4, ..., 2*n-2 (2) %C A000179 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 A000179 2*j_i - 3 (mod 2*n), (3) %C A000179 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 A000179 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 A000179 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 %C A000179 From _Ira M. Gessel_, Nov 27 2018: (Start) %C A000179 If we invert the formula %C A000179 Sum_{ n>=0 } u_n z^n = ((1-z)/(1+z)) F(z/(1+z)^2) %C A000179 that Don Knuth mentions (see link) (i.e., set x=z/(1+z)^2 and solve for z in terms of x), we get a formula for F(z) = Sum_{n >= 0} n! z^n as a sum with all positive coefficients of (almost) powers of the Catalan number generating function. %C A000179 The exact formula is (5) of the Yiting Li article. %C A000179 This article also gives a combinatorial proof of this formula (though it is not as simple as one might want). (End) %D A000179 W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50. %D A000179 M. Cerasoli, F. Eugeni and M. Protasi, Elementi di Matematica Discreta, Nicola Zanichelli Editore, Bologna 1988, Chapter 3, p. 78. %D A000179 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n). %D A000179 Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124. See u_n. %D A000179 E. Lucas, Théorie des nombres, Paris, 1891, pp. 491-495. %D A000179 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 A000179 T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - _N. J. A. Sloane_, Feb 24 2011 %D A000179 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197. %D A000179 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 A000179 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A000179 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A000179 H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. %D A000179 J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119. %D A000179 J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974. See page 10. %H A000179 Seiichi Manyama, Table of n, a(n) for n = 0..450 (terms 0..100 from T. D. Noe) %H A000179 M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12 arXiv:1510.07926, [math.CO], 2015-2016. %H A000179 Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135. %H A000179 Kenneth P. Bogart and Peter G. Doyle, Nonsexist solution of the ménage problem, Amer. Math. Monthly 93 (1986), no. 7, 514-519. %H A000179 A. Cayley, On a problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342. %H A000179 A. Cayley, On a problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342. %H A000179 A. Cayley, On Mr Muir's discussion of Professor Tait's problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391. %H A000179 A. Cayley, On Mr Muir's discussion of Professor Tait's problem of arrangements, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391. %H A000179 J. Dutka, On the Probleme des Menages, Mathem. Conversat. (2001) 277-287, reprinted from Math. Intell. 8 (1986) 18-25 %H A000179 A. de Gennaro, How many latin rectangles are there?, arXiv:0711.0527 [math.CO] (2007), see p. 2. %H A000179 P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 372 %H A000179 Nick Hobson, Python program for this sequence. %H A000179 Peter Kagey, Ranking and Unranking Restricted Permutations, arXiv:2210.17021 [math.CO], 2022. %H A000179 Irving Kaplansky, Solution of the "Problème des ménages", Bull. Amer. Math. Soc. 49, (1943). 784-785. %H A000179 Irving Kaplansky, Symbolic solution of certain problems in permutations, Bull. Amer. Math. Soc., 50 (1944), 906-914. %H A000179 I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy] %H A000179 S. M. Kerawala, Asymptotic solution of the "Probleme des menages, Bull. Calcutta Math. Soc., 39 (1947), 82-84. [Annotated scanned copy] %H A000179 Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 221. %H A000179 D. E. Knuth, Comments on A000179, Nov 25 2018 - Nov 27 2018. %H A000179 D. E. Knuth, Donald Knuth's 24th Annual Christmas Lecture: Dancing Links, Stanfordonline, Video published on YouTube, Dec 12, 2018. %H A000179 A. R. Kräuter, Über die Permanente gewisser zirkulärer Matrizen..., Séminaire Lotharingien de Combinatoire, B11b (1984), 11 pp. %H A000179 Yiting Li, Ménage Numbers and Ménage Permutations, J. Int. Seq. 18 (2015) 15.6.8 %H A000179 E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495. %H A000179 T. Muir, On Professor Tait's problem of arrangement, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387. %H A000179 T. Muir, On Professor Tait's problem of arrangement, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387. %H A000179 Vladimir Shevelev and Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015. %H A000179 Vladimir Shevelev and Peter J. C. Moses, Alice and Bob go to dinner: A variation on menage, INTEGERS, Vol. 16 (2016), #A72. %H A000179 R. J. Stones, S. Lin, X. Liu and G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1. %H A000179 H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy] %H A000179 J. Touchard, Théorie des substitutions. Sur un problème de permutations, C. R. Acad. Sci. Paris 198 (1934), 631-633. %H A000179 Eric Weisstein's World of Mathematics, Married Couples Problem. %H A000179 Eric Weisstein's World of Mathematics, Rooks Problem. %H A000179 Wikipedia, Menage problem. %H A000179 M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480. %H A000179 D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014. %F A000179 a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4*(-1)^n)/(n-2) for n >= 3. %F A000179 a(n) = A059375(n)/(2*n!) for n >= 2. %F A000179 a(n) = Sum_{k=0..n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k) for n >= 1. - Touchard (1934) %F A000179 G.f.: ((1-x)/(1+x))*Sum_{n>=0} n!*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 26 2007 %F A000179 a(2^k+2) == 0 (mod 2^k); for k >= 2, a(2^k) == 2(mod 2^k). - _Vladimir Shevelev_, Jan 14 2011 %F A000179 a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n > 1. - _Mark van Hoeij_, Oct 25 2011 %F A000179 a(n) ~ (n/e)^n * sqrt(2*Pi*n)/e^2. - _Charles R Greathouse IV_, Jan 21 2016 %F A000179 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 A000179 D-finite with recurrence: 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 %F A000179 a(n) = Sum_{k=0..n} A213234(n,k) * A000023(n-2*k) = Sum_{k=0..n} (-1)^k * n/(n-k) * binomial(n-k, k) * (n-2*k)! Sum_{j=0..n-2*k} (-2)^j/j! for n >= 1. [Wyman and Moser (1958)]. - _William P. Orrick_, Jun 25 2020 %F A000179 a(k+4*p) - 2*a(k+2*p) + a(k) is divisible by p, for any k > 0 and any prime p. - _Mark van Hoeij_, Jan 11 2022 %e A000179 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 A000179:= n ->add ((-1)^k*(2*n)*binomial(2*n-k,k)*(n-k)!/(2*n-k), k=0..n); # for n >= 1 %p A000179 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 >= 1 %t A000179 a[n_] := 2*n*Sum[(-1)^k*Binomial[2*n - k, k]*(n - k)!/(2*n - k), {k, 0, n}]; a[0] = 1; Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Dec 05 2012, from 2nd formula *) %o A000179 (PARI) \\ 3 programs adapted to a(1) = -1 by _Hugo Pfoertner_, Aug 31 2020 %o A000179 (PARI) {a(n) = my(A); if( n, A = vector(n,i,i-2); for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); A[n], 1)};/* _Michael Somos_, Jan 22 2008 */ %o A000179 (PARI) a(n)=if(n>1, round(2*n*exp(-2)*besselk(n, 2)), 1-2*n) \\ _Charles R Greathouse IV_, Nov 03 2014 %o A000179 (PARI) {a(n) = my(A); if( n, A = vector(n,i,i-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], 1)} /* _Michael Somos_, May 02 2018 */ %o A000179 (Haskell) %o A000179 import Data.List (zipWith5) %o A000179 a000179 n = a000179_list !! n %o A000179 a000179_list = 1 : -1 : 0 : 1 : zipWith5 %o A000179 (\v w x y z -> (x * y + (v + 2) * z - w) `div` v) [2..] (cycle [4,-4]) %o A000179 (drop 4 a067998_list) (drop 3 a000179_list) (drop 2 a000179_list) %o A000179 -- _Reinhard Zumkeller_, Aug 26 2013 %o A000179 (Python) %o A000179 from math import comb, factorial %o A000179 def A000179(n): return 1 if n == 0 else sum((-2*n if k & 1 else 2*n)*comb(m:=2*n-k,k)*factorial(n-k)//m for k in range(n+1)) # _Chai Wah Wu_, May 27 2022 %Y A000179 Diagonal of A058087. Also a diagonal of A008305. %Y A000179 Cf. A000904, A059375, A102761, A000186, A094047, A067998, A033999, A258664, A258665, A258666, A258667, A258673, A259212, A213234, A000023. %Y A000179 A000179, A102761, and A335700 are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1). - _N. J. A. Sloane_, Aug 06 2020 %K A000179 sign,nice,easy %O A000179 0,5 %A A000179 _N. J. A. Sloane_ %E A000179 More terms from _James A. Sellers_, May 02 2000 %E A000179 Additional comments from _David W. Wilson_, Feb 18 2003 %E A000179 a(1) changed to -1 at the suggestion of _Don Knuth_. - _N. J. A. Sloane_, Nov 26 2018 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE