|
%I M2070 N0818 #217 Mar 30 2024 21:19:46
%S 1,1,0,0,2,14,90,646,5242,47622,479306,5296790,63779034,831283558,
%T 11661506218,175203184374,2806878055610,47767457130566,
%U 860568917787402,16362838542699862,327460573946510746,6880329406055690790,151436547414562736234,3484423186862152966838
%N 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.
%C Permutations of 12...n such that none of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).
%C 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
%C This sequence was also derived by the late D. P. Robbins. - _David Callan_, Nov 04 2003
%C Another interpretation: number of permutations of n containing exactly n different patterns of size n-1. - _Olivier Gérard_, Nov 05 2007
%C Number of directed Hamiltonian paths in the complement of the n-path graph P_n. - _Andrew Howroyd_, Mar 16 2016
%C 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
%C 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
%D W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
%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 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.
%H N. J. A. Sloane, <a href="/A002464/b002464.txt">Table of n, a(n) for n = 0..500</a>
%H M. Abramson and W. O. J. Moser, <a href="http://dx.doi.org/10.1214/aoms/1177698793">Permutations without rising or falling w-sequences</a>, Ann. Math. Stat., 38 (1967), 1245-1254.
%H W. Ahrens, <a href="https://archive.org/stream/mathunterhaltung00ahrerich#page/n287/mode/2up">Mathematische Unterhaltungen und Spiele</a>, Leipzig: B. G. Teubner, 1901.
%H Another Roof, <a href="https://www.youtube.com/watch?v=qt5I1gZj1ew">A Lifelong Mathematical Obsession</a>, YouTube video, 2023.
%H Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, <a href="https://arxiv.org/abs/1905.02387">On the poset of King-Non-Attacking permutations</a>, arXiv:1905.02387 [math.CO], 2019.
%H Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, <a href="https://arxiv.org/abs/2001.02948">Counting King Permutations on the Cylinder</a>, arXiv:2001.02948 [math.CO], 2020.
%H Christoph Bärligea, <a href="https://arxiv.org/abs/2001.04597">On the dimension of the Fomin-Kirillov algebra and related algebras</a>, arXiv:2001.04597 [math.QA], 2020.
%H Robert Brignall, Vít Jelínek, Jan Kynčl, and David Marchant, <a href="https://arxiv.org/abs/1810.05449">Zeros of the Möbius function of permutations</a>, arXiv:1810.05449 [math.CO], 2018.
%H Doug Chatham, <a href="https://doi.org/10.1515/rmm-2017-0018">Independence and domination on shogiboard graphs</a>, Recreational Mathematics Magazine 4.8 (2017), pp. 25-37.
%H Doug Chatham, <a href="https://doi.org/10.2478/rmm-2018-0007">Reflections on the n+k dragon kings problem</a>, Games and Puzzles, Recreational Mathematics Magazine (2018) 5.10, 39-55.
%H Anders Claesson, <a href="https://akc.is/papers/036-From-Hertzsprungs-problem-to-pattern-rewriting-systems.pdf">From Hertzsprung's problem to pattern-rewriting systems</a>, University of Iceland (2020).
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 373.
%H Michael Han, Tanya Khovanova, Ella Kim, Evin Liang, Miriam Lubashev, Oleg Polin, Vaibhav Rastogi, Benjamin Taycher, Ada Tsui and Cindy Wei, <a href="https://arxiv.org/abs/2109.01530">Fun with Latin Squares</a>, arXiv:2109.01530 [math.HO], 2021.
%H C. Homberger, <a href="http://www.oalib.com/paper/2658972">Counting Fixed Length Permutation Patterns</a>, Online Journal of Analytic Combinatorics, 7 (2012).
%H Cheyne Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657 [math.CO], 2014.
%H Irving Kaplansky, <a href="http://dx.doi.org/10.1214/aoms/1177731121">The asymptotic distribution of runs of consecutive elements</a>, Ann. Math. Statistics, 16 (1945), 200-203
%H Sergey Kitaev and Jeffrey Remmel, <a href="http://arxiv.org/abs/1304.4286">(a,b)-rectangle patterns in permutations and words</a>, arXiv:1304.4286 [math.CO], (2013).
%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, pp. 625-635.
%H O. Patashnik and P. Flajolet, <a href="/A002464/a002464.pdf">Email to N. J. A. Sloane, Nov 26 1989</a>
%H P. Poulet, <a href="/A326411/a326411.pdf">Query 4750: Permutations</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)
%H P. Poulet, <a href="/A326411/a326411_1.pdf">Query 4750: Permutations</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119)
%H P. Poulet, <a href="/A326411/a326411_2.pdf">Query 4750: Permutations</a>, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121)
%H J. Riordan, <a href="http://projecteuclid.org/euclid.aoms/1177700181">A recurrence for permutations without rising or falling successions</a>, Ann. Math. Statist. 36 (1965), 708-710.
%H D. P. Robbins, <a href="http://www.jstor.org/stable/2321990">The probability that neighbors remain neighbors after random rearrangements</a>, Amer. Math. Monthly 87 (1980), 122-124.
%H Josef Rukavicka, <a href="https://arxiv.org/abs/2106.11244">Secretary problem and two almost the same consecutive applicants</a>, arXiv:2106.11244 [math.PR], 2021.
%H A. J. Schwenk, <a href="/A002464/a002464_1.pdf">Letter to N. J. A. Sloane, Mar 24 1980</a> (with enclosure and notes)
%H L. Shapiro and A. B. Stephens, <a href="http://dx.doi.org/10.1137/0404025">Bootstrap percolation, the Schroeder problems and the n-kings problem</a>, SIAM J. Discrete Math., 4 (1991), 275-280.
%H Jason P. Smith, <a href="http://arxiv.org/abs/1506.04406">A Formula for the Mobius function of the Permutation Poset Based on a Topological Decomposition</a>, arXiv preprint arXiv:1506.04406 [math.CO], 2015.
%H Roberto Tauraso, <a href="http://www.emis.de/journals/INTEGERS/papers/g11/g11.Abstract.html">The Dinner Table Problem: The Rectangular Case</a>, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. See Column 3 in the table on page 3.
%H B. E. Tenner, <a href="http://arxiv.org/abs/1302.1883">Mesh patterns with superfluous mesh</a>, arXiv preprint arXiv:1302.1883 [math.CO], 2013.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathComplementGraph.html">Path Complement Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Permutation.html">Permutation</a>
%H Multiple authors, <a href="http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=65890">Discussion at the Art Of Problem Solving forum</a>
%F 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).
%F G.f.: Sum_{n >= 0} n!*x^n*(1-x)^n/(1+x)^n. - _Philippe Flajolet_
%F 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
%F 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].
%F 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
%F 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
%F 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
%F Conjecture: a(n) = Sum_{k=1..n} k!*A080246(n-1, k-1) for n > 0. - _John Keith_, Nov 02 2020
%F 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
%e a(4) = 2: 2413, 3142.
%e 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.
%p 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;
%t (* computation from the permutation class *)
%t 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_ *)
%t (* or direct computation of terms *)
%t 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 *)
%t (* or from g.f. *)
%t 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 *)
%t 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 *)
%t 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 *)
%o (PARI)
%o N = 66; x = 'x + O('x^N);
%o gf = sum(n=0,N, n!*(x*(1-x))^n/(1+x)^n );
%o v = Vec(gf) /* _Joerg Arndt_, Apr 17 2013 */
%o (Python)
%o from math import factorial, comb
%o 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)<<t for t in range(1,k+1)) for k in range(1,n+1)) # _Chai Wah Wu_, Feb 19 2024
%Y Equals 2*A001266(n) for n >= 2. A diagonal of A001100. Cf. A010028.
%Y Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268, A010028, A002493.
%Y Cf. A089222.
%Y Column k=1 of A333706.
%K nonn,nice,easy
%O 0,5
%A _N. J. A. Sloane_
%E Merged with the old A001100, Aug 19 2003
%E Kaplansky reference from _David Callan_, Oct 29 2003
%E Tauraso reference from _Parthasarathy Nambi_, Dec 21 2006
%E Edited by _Jon E. Schoenfield_, Jan 31 2015
|
