|
%I M2062 N0815 #262 Sep 03 2023 23:40:25
%S 1,-1,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: 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 According to rook theory, _John Riordan_ considered a(1) to be -1. - _Vladimir Shevelev_, Apr 02 2010
%C 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 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 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 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
%C From _Ira M. Gessel_, Nov 27 2018: (Start)
%C If we invert the formula
%C Sum_{ n>=0 } u_n z^n = ((1-z)/(1+z)) F(z/(1+z)^2)
%C 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 The exact formula is (5) of the Yiting Li article.
%C This article also gives a combinatorial proof of this formula (though it is not as simple as one might want). (End)
%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. See u_n.
%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.
%D J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974. See page 10.
%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. Cayley, <a href="https://doi.org/10.1017/S0370164600032430">On a problem of arrangements</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342.
%H A. Cayley, <a href="https://books.google.com/books?id=cknMb_f-snMC&pg=338#v=onepage&q&f=false">On a problem of arrangements</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 338-342.
%H A. Cayley, <a href="https://doi.org/10.1017/S0370164600032569">On Mr Muir's discussion of Professor Tait's problem of arrangements</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391.
%H A. Cayley, <a href="https://books.google.com/books?id=cknMb_f-snMC&pg=388#v=onepage&q&f=false">On Mr Muir's discussion of Professor Tait's problem of arrangements</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 388-391.
%H J. Dutka, <a href="https://doi.org/10.1007/978-1-4613-0195-0">On the Probleme des Menages</a>, Mathem. Conversat. (2001) 277-287, reprinted from <a href="https://doi.org/10.1007/BF03025785">Math. Intell. 8 (1986) 18-25</a>
%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 Peter Kagey, <a href="https://arxiv.org/abs/2210.17021">Ranking and Unranking Restricted Permutations</a>, arXiv:2210.17021 [math.CO], 2022.
%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 I. Kaplansky and J. Riordan, <a href="/A000166/a000166_1.pdf">The problème des ménages</a>, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
%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 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 221.
%H D. E. Knuth, <a href="/A000179/a000179.txt">Comments on A000179</a>, Nov 25 2018 - Nov 27 2018.
%H D. E. Knuth, <a href="https://youtu.be/_cR9zDlvP88?t=2047">Donald Knuth's 24th Annual Christmas Lecture: Dancing Links</a>, Stanfordonline, Video published on YouTube, Dec 12, 2018.
%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 Yiting 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 T. Muir, <a href="https://doi.org/10.1017/S0370164600032557">On Professor Tait's problem of arrangement</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387.
%H T. Muir, <a href="https://books.google.com/books?id=cknMb_f-snMC&pg=382#v=onepage&q&f=false">On Professor Tait's problem of arrangement</a>, Proceedings of the Royal Society of Edinburgh 9 (1878) 382-387.
%H Vladimir Shevelev and 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 and 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/M%C3%A9nage_problem">Menage 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 >= 3.
%F a(n) = A059375(n)/(2*n!) for n >= 2.
%F 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 G.f.: ((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 > 1. - _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 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 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 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 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 >= 1
%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 >= 1
%t 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 (PARI) \\ 3 programs adapted to a(1) = -1 by _Hugo Pfoertner_, Aug 31 2020
%o (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 (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 (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 (Haskell)
%o import Data.List (zipWith5)
%o a000179 n = a000179_list !! n
%o a000179_list = 1 : -1 : 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
%o (Python)
%o from math import comb, factorial
%o 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 Diagonal of A058087. Also a diagonal of A008305.
%Y Cf. A000904, A059375, A102761, A000186, A094047, A067998, A033999, A258664, A258665, A258666, A258667, A258673, A259212, A213234, A000023.
%Y 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 sign,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
%E a(1) changed to -1 at the suggestion of _Don Knuth_. - _N. J. A. Sloane_, Nov 26 2018
|
