The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002464 Hertzsprung's problem: ways to arrange n non-attacking kings on an n X n board, with 1 in each row and column. Also number of permutations of length n without rising or falling successions. (Formerly M2070 N0818) 49
 1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,5 COMMENTS Permutations of 12...n such that none of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1). This sequence is also the solution to the 'toast problem' devised by my house-mates and me as math undergraduates some 27 years ago: Given a toast rack with n slots, how many ways can the slices be removed so that no two consecutive slices are removed from adjacent slots? - David Jones (david.jones(AT)zetnet.co.uk), Oct 24 2003 This sequence was also derived by the late D. P. Robbins. - David Callan, Nov 04 2003 Another interpretation: number of permutations of n containing exactly n different patterns of size n-1. - Olivier Gérard, Nov 05 2007 Number of directed Hamiltonian paths in the complement of the n-path graph P_n. - Andrew Howroyd, Mar 16 2016 There is an obvious connection between the two descriptions of the sequence: Replace the chessboard with a n X n zero-matrix and each king with "1". This matrix will transform the vector (1,2,..,n) into a permutation such that adjacent components do not differ by 1. The reverse is also true: Any such transformation is a solution of the king problem. - Gerhard Kirchner, Feb 10 2017 A formula of Poulet (1919) relates this to A326411: a(n) = T(n+2,1)/(n+2) + 2*T(n+1,1)/(n+1) + T(n,1)/n, where T(i,j) = A326411(i,j). - N. J. A. Sloane, Mar 08 2022 REFERENCES W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271. F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263. 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). R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40. LINKS N. J. A. Sloane, Table of n, a(n) for n = 0..500 M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254. W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901. Another Roof, A Lifelong Mathematical Obsession, YouTube video, 2023. Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, On the poset of King-Non-Attacking permutations, arXiv:1905.02387 [math.CO], 2019. Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Counting King Permutations on the Cylinder, arXiv:2001.02948 [math.CO], 2020. Christoph Bärligea, On the dimension of the Fomin-Kirillov algebra and related algebras, arXiv:2001.04597 [math.QA], 2020. Robert Brignall, Vít Jelínek, Jan Kynčl, and David Marchant, Zeros of the Möbius function of permutations, arXiv:1810.05449 [math.CO], 2018. Doug Chatham, Independence and domination on shogiboard graphs, Recreational Mathematics Magazine 4.8 (2017), pp. 25-37. Doug Chatham, Reflections on the n+k dragon kings problem, Games and Puzzles, Recreational Mathematics Magazine (2018) 5.10, 39-55. Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020). P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373. Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, Fun with Latin Squares, arXiv:2109.01530 [math.HO], 2021. C. Homberger, Counting Fixed Length Permutation Patterns, Online Journal of Analytic Combinatorics, 7 (2012). Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014. Irving Kaplansky, The asymptotic distribution of runs of consecutive elements, Ann. Math. Statistics, 16 (1945), 200-203 Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], (2013). Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 625-635. O. Patashnik and P. Flajolet, Email to N. J. A. Sloane, Nov 26 1989 P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117) P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119) P. Poulet, Query 4750: Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121) J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710. D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124. Josef Rukavicka, Secretary problem and two almost the same consecutive applicants, arXiv:2106.11244 [math.PR], 2021. A. J. Schwenk, Letter to N. J. A. Sloane, Mar 24 1980 (with enclosure and notes) L. Shapiro and A. B. Stephens, Bootstrap percolation, the Schroeder problems and the n-kings problem, SIAM J. Discrete Math., 4 (1991), 275-280. Jason P. Smith, A Formula for the Mobius function of the Permutation Poset Based on a Topological Decomposition, arXiv preprint arXiv:1506.04406 [math.CO], 2015. Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. See Column 3 in the table on page 3. B. E. Tenner, Mesh patterns with superfluous mesh, arXiv preprint arXiv:1302.1883 [math.CO], 2013. Eric Weisstein's World of Mathematics, Hamiltonian Path Eric Weisstein's World of Mathematics, Path Complement Graph Eric Weisstein's World of Mathematics, Permutation Multiple authors, Discussion at the Art Of Problem Solving forum FORMULA If n = 0 or 1 then a(n) = 1; if n = 2 or 3 then a(n) = 0; otherwise a(n) = (n+1)*a(n-1) - (n-2)*a(n-2) - (n-5)*a(n-3) + (n-3)*a(n-4). G.f.: Sum_{n >= 0} n!*x^n*(1-x)^n/(1+x)^n. - Philippe Flajolet G.f.: e^((1 + x)/((-1 + x) * x)) * (1 + x) * Gamma(0, (1 + x)/((-1 + x) * x))/((-1 + x) * x). - Eric W. Weisstein, May 16 2014 Let S_{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} S_{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4]. a(n) = n! + Sum_{k=1..n} (-1)^k * Sum_{t=1..k} binomial(k-1,t-1) * binomial(n-k,t) * 2^t * (n-k)!. - Max Alekseyev, Jan 29 2006 a(n) = Sum_{k=0..n} (-1)^(n-k)*k!*b(n,k), where g.f. for b(n,k) is (1-x)/(1-(1+y)*x-y*x^2), cf. A035607. - Vladeta Jovovic, Nov 24 2007 Asymptotic (M. Abramson and W. Moser, 1966): a(n)/n! ~ (1 - 2/n^2 - 10/(3*n^3) - 6/n^4 - 154/(15*n^5) - 88/(9*n^6) + 5336/(105*n^7) + 1612/(3*n^8) + 2098234/(567*n^9) + 36500686/(1575*n^10) + ... )/e^2. - Vaclav Kotesovec, Apr 19 2011, extended Dec 27 2020 Conjecture: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. - John Keith, Nov 02 2020 Proof: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. Since a(n) = Sum_{k=0..n-1} (-1)^k*(n-k)!*Sum_{i=0..k} binomial(n-k,i)*binomial(n-1-i,k-i) (M. Abramson and W. Moser, 1966) which is Sum_{k=1..n} (-1)^(k-1)(n-k+1)!*Sum{i=0..k-1} binomial(n-k+1,i)*binomial(n-1-i,k-1-i) = Sum_{k=1..n} (-1)^(n-k)(k!)*Sum_{i=0..n-k} binomial(k,i)*binomial(n-1-i,n-k-i) = k!*A080246(n-1, k-1) as (-1)^(n-k) = (-1)^(n+k) and binomial(n-1-i,k-1) = binomial(n-1-i,n-k-i). - Alex McGaw, Apr 13 2023 EXAMPLE a(4) = 2: 2413, 3142. a(5) = 14 corresponds to these 14 permutations of length 5: 13524, 14253, 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142. MAPLE A002464 := proc(n) options remember; if n <= 1 then 1 elif n <= 3 then 0 else (n+1)*A002464(n-1)-(n-2)*A002464(n-2)-(n-5)*A002464(n-3)+(n-3)*A002464(n-4); fi; end; MATHEMATICA (* computation from the permutation class *) g[ L_ ] := Apply[ And, Map[ #>1&, L ] ]; f[ n_ ] := Length[ Select[ Permutations[ Range[ n ] ], g[ Rest[ Abs[ RotateRight[ # ]-# ] ] ]& ] ]; Table[ f[ n ], {n, 1, 8} ] (* Erich Friedman *) (* or direct computation of terms *) Table[n! + Sum[(-1)^r*(n-r)!*Sum[2^c *Binomial[r-1, c-1] *Binomial[n-r, c], {c, 1, r}], {r, 1, n-1}], {n, 1, 30}] (* Vaclav Kotesovec, Mar 28 2011 *) (* or from g.f. *) M = 30; CoefficientList[Sum[n!*x^n*(1-x)^n/(1+x)^n, {n, 0, M}] + O[x]^M, x] (* Jean-François Alcover, Jul 07 2015 *) CoefficientList[Series[Exp[(1 + x)/((-1 + x) x)] (1 + x) Gamma[0, (1 + x)/((-1 + x) x)]/((-1 + x) x), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 11 2018 *) RecurrenceTable[{a[n] == (n + 1) a[n - 1] - (n - 2) a[n - 2] - (n - 5) a[n - 3] + (n - 3) a[n - 4], a[0] == a[1] == 1, a[2] == a[3] == 0}, a, {n, 0, 20}] (* Eric W. Weisstein, Apr 11 2018 *) PROG (PARI) N = 66; x = 'x + O('x^N); gf = sum(n=0, N, n!*(x*(1-x))^n/(1+x)^n ); v = Vec(gf) /* Joerg Arndt, Apr 17 2013 */ (Python) from math import factorial, comb def A002464(n): return factorial(n)+sum((-1 if k&1 else 1)*factorial(n-k)*sum(comb(k-1, t-1)*comb(n-k, t)<= 2. A diagonal of A001100. Cf. A010028. Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268, A010028, A002493. Cf. A089222. Column k=1 of A333706. Sequence in context: A174705 A109113 A081959 * A282051 A020063 A323561 Adjacent sequences: A002461 A002462 A002463 * A002465 A002466 A002467 KEYWORD nonn,nice,easy AUTHOR N. J. A. Sloane EXTENSIONS Merged with the old A001100, Aug 19 2003 Kaplansky reference from David Callan, Oct 29 2003 Tauraso reference from Parthasarathy Nambi, Dec 21 2006 Edited by Jon E. Schoenfield, Jan 31 2015 STATUS approved

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

Last modified July 15 16:36 EDT 2024. Contains 374333 sequences. (Running on oeis4.)