CINXE.COM
A000179 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A000179 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000179" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA000179">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A000179 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A000179 </div> <div class=seqname> 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. <br><font size=-1>(Formerly M2062 N0815)</font> </div> </div> <div class=scorerefs> 62 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, -1, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123</div> <div class=seqdatalinks> (<a href="/A000179/list">list</a>; <a href="/A000179/graph">graph</a>; <a href="/search?q=A000179+-id:A000179">refs</a>; <a href="/A000179/listen">listen</a>; <a href="/history?seq=A000179">history</a>; <a href="/search?q=id:A000179&fmt=text">text</a>; <a href="/A000179/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,5</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>According to rook theory, <a href="/wiki/User:John_Riordan">John Riordan</a> considered a(1) to be -1. - <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Apr 02 2010</div> <div class=sectline>This is also the value that the formulas of Touchard and of Wyman and Moser give and is compatible with many recurrences. - <a href="/wiki/User:William_P._Orrick">William P. Orrick</a>, Aug 31 2020</div> <div class=sectline>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. - <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Mar 22 2010</div> <div class=sectline>Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare <a href="/A186638" title="a(0)=a(1)=a(2)=0; thereafter a(n) = n*a(n-1) + n*a(n-2)/(n-2) + (-1)^(n-1)*4/(n-2).">A186638</a>. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Feb 24 2011</div> <div class=sectline>Sequence discovered by Touchard in 1934. - <a href="/wiki/User:L._Edson_Jeffery">L. Edson Jeffery</a>, Nov 13 2013</div> <div class=sectline>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. - <a href="/wiki/User:Stanislav_Sykora">Stanislav Sykora</a>, Mar 14 2014</div> <div class=sectline>An equivalent problem was formulated by Tait; solutions to Tait's problem were given by Muir (1878) and Cayley (1878). - <a href="/wiki/User:William_P._Orrick">William P. Orrick</a>, Aug 31 2020</div> <div class=sectline>From <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Jun 25 2015: (Start)</div> <div class=sectline>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.</div> <div class=sectline>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</div> <div class=sectline> 001*11</div> <div class=sectline> 1*0011</div> <div class=sectline> 11001* (1)</div> <div class=sectline> 11*100</div> <div class=sectline> 0111*0,</div> <div class=sectline>where 5 non-attacking rooks are denoted by {1*}.</div> <div class=sectline>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</div> <div class=sectline> 2*n, 2, 4, ..., 2*n-2 (2)</div> <div class=sectline>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</div> <div class=sectline> 2*j_i - 3 (mod 2*n), (3)</div> <div class=sectline>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.</div> <div class=sectline>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)</div> <div class=sectline>The first 20 terms of this sequence were calculated in 1891 by E. Lucas (see [Lucas, p. 495]). - <a href="/wiki/User:Peter_J._C._Moses">Peter J. C. Moses</a>, Jun 26 2015</div> <div class=sectline>From <a href="/wiki/User:Ira_M._Gessel">Ira M. Gessel</a>, Nov 27 2018: (Start)</div> <div class=sectline>If we invert the formula</div> <div class=sectline> Sum_{ n>=0 } u_n z^n = ((1-z)/(1+z)) F(z/(1+z)^2)</div> <div class=sectline>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.</div> <div class=sectline>The exact formula is (5) of the Yiting Li article.</div> <div class=sectline>This article also gives a combinatorial proof of this formula (though it is not as simple as one might want). (End)</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50.</div> <div class=sectline>M. Cerasoli, F. Eugeni and M. Protasi, Elementi di Matematica Discreta, Nicola Zanichelli Editore, Bologna 1988, Chapter 3, p. 78.</div> <div class=sectline>L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).</div> <div class=sectline>Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124. See u_n.</div> <div class=sectline>E. Lucas, Th茅orie des nombres, Paris, 1891, pp. 491-495.</div> <div class=sectline>P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.</div> <div class=sectline>T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Feb 24 2011</div> <div class=sectline>J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.</div> <div class=sectline>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. - <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Mar 22 2010</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> <div class=sectline>H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.</div> <div class=sectline>J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119.</div> <div class=sectline>J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974. See page 10.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Seiichi Manyama, <a href="/A000179/b000179.txt">Table of n, a(n) for n = 0..450</a> (terms 0..100 from T. D. Noe)</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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></div> <div class=sectline>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.</div> <div class=sectline>P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 372</div> <div class=sectline>Nick Hobson, <a href="/A000179/a000179.py.txt">Python program for this sequence</a>.</div> <div class=sectline>Peter Kagey, <a href="https://arxiv.org/abs/2210.17021">Ranking and Unranking Restricted Permutations</a>, arXiv:2210.17021 [math.CO], 2022.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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]</div> <div class=sectline>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]</div> <div class=sectline>Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 221.</div> <div class=sectline>D. E. Knuth, <a href="/A000179/a000179.txt">Comments on A000179</a>, Nov 25 2018 - Nov 27 2018.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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</div> <div class=sectline>E. Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k29021h">Th茅orie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>H. M. Taylor, <a href="/A000179/a000179.pdf">A problem on arrangements</a>, Mess. Math., 32 (1902), 60ff. [Annotated scanned copy]</div> <div class=sectline>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.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MarriedCouplesProblem.html">Married Couples Problem</a>.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RooksProblem.html">Rooks Problem</a>.</div> <div class=sectline>Wikipedia, <a href="https://en.wikipedia.org/wiki/M%C3%A9nage_problem">Menage problem</a>.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4*(-1)^n)/(n-2) for n >= 3.</div> <div class=sectline>a(n) = <a href="/A059375" title="Number of seating arrangements for the m茅nage problem.">A059375</a>(n)/(2*n!) for n >= 2.</div> <div class=sectline>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)</div> <div class=sectline>G.f.: ((1-x)/(1+x))*Sum_{n>=0} n!*(x/(1+x)^2)^n. - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Jun 26 2007</div> <div class=sectline>a(2^k+2) == 0 (mod 2^k); for k >= 2, a(2^k) == 2(mod 2^k). - <a href="/wiki/User:Vladimir_Shevelev">Vladimir Shevelev</a>, Jan 14 2011</div> <div class=sectline>a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n > 1. - <a href="/wiki/User:Mark_van_Hoeij">Mark van Hoeij</a>, Oct 25 2011</div> <div class=sectline>a(n) ~ (n/e)^n * sqrt(2*Pi*n)/e^2. - <a href="/wiki/User:Charles_R_Greathouse_IV">Charles R Greathouse IV</a>, Jan 21 2016</div> <div class=sectline>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. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Apr 29 2018</div> <div class=sectline>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. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, May 02 2018</div> <div class=sectline>a(n) = Sum_{k=0..n} <a href="/A213234" title="Triangle read by rows: coefficients of auxiliary Rudin-Shapiro polynomials A_{ns}(omega) written in descending powers of x.">A213234</a>(n,k) * <a href="/A000023" title="Expansion of e.g.f. exp(-2*x)/(1-x).">A000023</a>(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)]. - <a href="/wiki/User:William_P._Orrick">William P. Orrick</a>, Jun 25 2020</div> <div class=sectline>a(k+4*p) - 2*a(k+2*p) + a(k) is divisible by p, for any k > 0 and any prime p. - <a href="/wiki/User:Mark_van_Hoeij">Mark van Hoeij</a>, Jan 11 2022</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>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.</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline><a href="/A000179" title="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 a...">A000179</a>:= n ->add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); # for n >= 1</div> <div class=sectline>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; <a href="/A000179" title="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 a...">A000179</a> := n->W(n, 0); # valid for n >= 1</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>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}] (* <a href="/wiki/User:Jean-Fran莽ois_Alcover">Jean-Fran莽ois Alcover</a>, Dec 05 2012, from 2nd formula *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) \\ 3 programs adapted to a(1) = -1 by <a href="/wiki/User:Hugo_Pfoertner">Hugo Pfoertner</a>, Aug 31 2020</div> <div class=sectline>(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)}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Jan 22 2008 */</div> <div class=sectline>(PARI) a(n)=if(n>1, round(2*n*exp(-2)*besselk(n, 2)), 1-2*n) \\ <a href="/wiki/User:Charles_R_Greathouse_IV">Charles R Greathouse IV</a>, Nov 03 2014</div> <div class=sectline>(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)} /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, May 02 2018 */</div> <div class=sectline>(Haskell)</div> <div class=sectline>import Data.List (zipWith5)</div> <div class=sectline>a000179 n = a000179_list !! n</div> <div class=sectline>a000179_list = 1 : -1 : 0 : 1 : zipWith5</div> <div class=sectline> (\v w x y z -> (x * y + (v + 2) * z - w) `div` v) [2..] (cycle [4, -4])</div> <div class=sectline> (drop 4 a067998_list) (drop 3 a000179_list) (drop 2 a000179_list)</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Aug 26 2013</div> <div class=sectline>(Python)</div> <div class=sectline>from math import comb, factorial</div> <div class=sectline>def <a href="/A000179" title="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 a...">A000179</a>(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)) # <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, May 27 2022</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Diagonal of <a href="/A058087" title="Triangle read by rows, giving coefficients of the m茅nage hit polynomials ordered by descending powers. T(n, k) for 0 <= k <= n.">A058087</a>. Also a diagonal of <a href="/A008305" title="Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.">A008305</a>.</div> <div class=sectline>Cf. <a href="/A000904" title="a(n) = (n+1)*a(n-1) + (n+2)*a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.">A000904</a>, <a href="/A059375" title="Number of seating arrangements for the m茅nage problem.">A059375</a>, <a href="/A102761" title="Same as A000179, except that a(0) = 2.">A102761</a>, <a href="/A000186" title="Number of 3 X n Latin rectangles in which the first row is in order.">A000186</a>, <a href="/A094047" title="Number of seating arrangements of n couples around a round table (up to rotations) so that each person sits between two peop...">A094047</a>, <a href="/A067998" title="a(n) = n^2 - 2*n.">A067998</a>, <a href="/A033999" title="a(n) = (-1)^n.">A033999</a>, <a href="/A258664" title="A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular ...">A258664</a>, <a href="/A258665" title="A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular ...">A258665</a>, <a href="/A258666" title="A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular ...">A258666</a>, <a href="/A258667" title="A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular ...">A258667</a>, <a href="/A258673" title="A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular ...">A258673</a>, <a href="/A259212" title="A total of n married couples, including a mathematician M and his wife W, are to be seated at the 2n chairs around a circula...">A259212</a>, <a href="/A213234" title="Triangle read by rows: coefficients of auxiliary Rudin-Shapiro polynomials A_{ns}(omega) written in descending powers of x.">A213234</a>, <a href="/A000023" title="Expansion of e.g.f. exp(-2*x)/(1-x).">A000023</a>.</div> <div class=sectline><a href="/A000179" title="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 a...">A000179</a>, <a href="/A102761" title="Same as A000179, except that a(0) = 2.">A102761</a>, and <a href="/A335700" title="A variant of A000179 and A102761.">A335700</a> are all essentially the same sequence but with different conventions for the initial terms a(0) and a(1). - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Aug 06 2020</div> <div class=sectline>Sequence in context: <a href="/A037571" title="Base 6 digits are, in order, the first n terms of the periodic sequence with initial period 2,1,2.">A037571</a> <a href="/A179237" title="a(0) = 1, a(1) = 2; a(n+1) = 6*a(n) + a(n-1) for n>1.">A179237</a> <a href="/A216316" title="G.f.: 1/( (1-8*x)*(1+x)^2 )^(1/3).">A216316</a> * <a href="/A335700" title="A variant of A000179 and A102761.">A335700</a> <a href="/A246383" title=" Column 1 of triangular matrix A246381 = exp(L) where L(n,k) = C(2*n, 2*k+1)/2.">A246383</a> <a href="/A189087" title="E.g.f.: sinh(x)/(1-sinh(x)-sinh(x)^2).">A189087</a></div> <div class=sectline>Adjacent sequences: <a href="/A000176" title="Generalized tangent numbers d_(n,2).">A000176</a> <a href="/A000177" title="Number of partitions of n into 6 squares.">A000177</a> <a href="/A000178" title="Superfactorials: product of first n factorials.">A000178</a> * <a href="/A000180" title="Expansion of E.g.f. exp(-x)/(1-3x).">A000180</a> <a href="/A000181" title="Coefficients of m茅nage hit polynomials.">A000181</a> <a href="/A000182" title="Tangent (or "Zag") numbers: e.g.f. tan(x), also (up to signs) e.g.f. tanh(x).">A000182</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="sequence contains negative numbers">sign</span>,<span title="an exceptionally nice sequence">nice</span>,<span title="it is very easy to produce terms of sequence">easy</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>More terms from <a href="/wiki/User:James_A._Sellers">James A. Sellers</a>, May 02 2000</div> <div class=sectline>Additional comments from <a href="/wiki/User:David_W._Wilson">David W. Wilson</a>, Feb 18 2003</div> <div class=sectline>a(1) changed to -1 at the suggestion of <a href="/wiki/User:Don_Knuth">Don Knuth</a>. - <a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a>, Nov 26 2018</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 24 10:16 EST 2024. Contains 378080 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>