A333706 -id:A333706 - cp's OEIS frontend

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.

1, 1, 0, 0, 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, 831283558, 11661506218, 175203184374, 2806878055610, 47767457130566, 860568917787402, 16362838542699862, 327460573946510746, 6880329406055690790, 151436547414562736234, 3484423186862152966838

Offset: 0

N. J. A. Sloane

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
For the number of these permutations without fixed points see A288208. - Wolfdieter Lang, May 22 2025

			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.

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.

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.
Art of Problem Solving Forum, Number of permutative
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.
Sela Fried, Further results on staircase (cyclic) words, arXiv:2501.11991 [math.CO], 2025. See p. 12.
Sela Fried, Toufik Mansour, and Mark Shattuck, Counting k-ary words by number of adjacency differences of a prescribed size, arXiv:2504.03013 [math.CO], 2025. See p. 2.
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.
Mark Huibregtse, Cristobal Lemus-Vidales, and David Vella, Bootstrap Percolation, Indecomposable Permutations, and the n-Kings problem, arXiv:2508.02030 [math.CO], 2025. See p. 2.
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.
Igor Minevich, Gabe Cunningham, Aditya Karan, and Joshua V. Gyllinsky, Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464, arXiv:2411.02251 [cs.CC], 2024.
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

Equals 2*A001266(n) for n >= 2. A diagonal of A001100. Cf. A010028.
Cf. A086852, A086853, A086854, A086855, A000130, A000349, A001267, A001268, A010028, A002493.
Cf. A089222, A104698, A288208.
Column k=1 of A333706.

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;

(* 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 *)

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 */

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)<Chai Wah Wu, Feb 19 2024

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
a(n+2) = (n+2)! - Sum_{j=0..n} (-1)^j*(n+1-j)!*2*A104698(n, j), for n >= 0 (Abramson and Moser, p. 1250, (III), N_0(n+2), last line, rewritten). - Wolfdieter Lang, May 14 2025

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

A110128 Number of permutations p of 1,2,...,n satisfying |p(i+2)-p(i)| not equal to 2 for all 0

Original entry on oeis.org

1, 1, 2, 4, 16, 44, 200, 1288, 9512, 78652, 744360, 7867148, 91310696, 1154292796, 15784573160, 232050062524, 3648471927912, 61080818510972, 1084657970877416, 20361216987032284, 402839381030339816, 8377409956454452732

Offset: 0

Roberto Tauraso, A. Nicolosi and G. Minenkov, Jul 13 2005

When n is even: 1) Number of ways that n persons seated at a rectangular table with n/2 seats along the two opposite sides can be rearranged in such a way that neighbors are no more neighbors after the rearrangement. 2) Number of ways to arrange n kings on an n X n board, with 1 in each row and column, which are non-attacking with respect to the main four quadrants.
a(n) is also number of ways to place n nonattacking pieces rook + alfil on an n X n chessboard (Alfil is a leaper [2,2]) [From Vaclav Kotesovec, Jun 16 2010]
Note that the conjectured recurrence was based on the 600-term b-file, not the other way round. - N. J. A. Sloane, Dec 07 2022

Rintaro Matsuo, Table of n, a(n) for n = 0..600 (terms up to a(35) from Vaclav Kotesovec)
Manuel Kauers, Guessed recurrence operator of order 24 and degree 64
Vaclav Kotesovec, Mathematica program for this sequence
George Spahn and Doron Zeilberger, Counting Permutations Where The Difference Between Entries Located r Places Apart Can never be s (For any given positive integers r and s), arXiv:2211.02550 [math.CO], 2022.
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS, vol. 6 (2006), paper A11. arXiv:math/0507293.

Cf. A089222, A002464, A117574, A189281.

Column k=2 of A333706.

A formula is given in the Tauraso reference.
Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 4/n + 8/n^2)/e^2.
a(n) ~ exp(-2) * n! * (1 + 4/n + 8/n^2 + 68/(3*n^3) + 242/(3*n^4) + 1692/(5*n^5) + 72802/(45*n^6) + 2725708/(315*n^7) + 16083826/(315*n^8) + 186091480/(567*n^9) + 32213578294/(14175*n^10) + ...), based on the recurrence by Manuel Kauers. - Vaclav Kotesovec, Dec 05 2022

Edited by N. J. A. Sloane at the suggestion of Vladeta Jovovic, Jan 01 2008

Terms a(33)-a(35) from Vaclav Kotesovec, Apr 20 2012

A117574 Total number of permutations p of [n] such that |p(i+3) - p(i)| is not equal to 3 for 1 <= i <= n-3.

Original entry on oeis.org

1, 1, 2, 6, 20, 80, 384, 2240, 15424, 123456, 1110928, 11287232, 127016304, 1565107248, 20935873872, 301974271248, 4669727780624, 77046043259824, 1350585114106416, 25062108668100208, 490725684463001488, 10109820295907492304

Offset: 0

James Sellers, Apr 27 2006

a(n) is also number of ways to place n nonattacking pieces rook + leaper[3,3] on an n X n chessboard.

Vaclav Kotesovec, Table of n, a(n) for n = 0..30
Vaclav Kotesovec, Non-attacking chess pieces, Sixth edition, p. 633, Feb 02 2013.
Vaclav Kotesovec, Mathematica program for this sequence
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.

Cf. A002464, A110128.

Column k=3 of A333706.

Formula given in Tauraso reference.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 8/n + 30/n^2)/e^2.

Terms a(17)-a(28) from Vaclav Kotesovec, Apr 19 2011
Terms a(29)-a(30) from Vaclav Kotesovec, Apr 20 2012
a(0)=1 prepended by Alois P. Heinz, Feb 05 2023

A189255 Number of permutations p of 1,2,...,n satisfying |p(i+4)-p(i)|<>4 for all 1<=i<=n-4.

Original entry on oeis.org

1, 2, 6, 24, 108, 544, 3264, 23040, 176832, 1563392, 15536160, 171172224, 2066033472, 27146652480, 385447394880, 5878028516736, 95776238793504, 1660164417866304, 30496085473606944, 591661117634375040, 12087628978334638752

Offset: 1

Vaclav Kotesovec, Apr 19 2011

a(n) is also number of ways to place n nonattacking pieces rook + leaper[4,4] on an n X n chessboard.

Vaclav Kotesovec, Table of n, a(n) for n = 1..27
Vaclav Kotesovec, Non-attacking chess pieces, Sixth edition, p. 633, Feb 02 2013.
Vaclav Kotesovec, Mathematica program for this sequence
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.

Cf. A002464, A110128, A117574.

Column k=4 of A333706.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 12/n + 64/n^2)/e^2.

Terms a(26)-a(27) from Vaclav Kotesovec, Apr 20 2012

A189256 Number of permutations p of 1,2,...,n satisfying |p(i+5)-p(i)|<>5 for all 1<=i<=n-5.

Original entry on oeis.org

1, 2, 6, 24, 120, 672, 4128, 28992, 231936, 2088960, 20434944, 221871360, 2645370624, 34344038400, 482103767040, 7269498483456, 117240911729664, 2013265377314688, 36665783917283328, 705762463906133760, 14313891805008665856

Offset: 1

Vaclav Kotesovec, Apr 19 2011

a(n) is also number of ways to place n nonattacking pieces rook + leaper[5,5] on an n X n chessboard.

Vaclav Kotesovec, Table of n, a(n) for n = 1..26
Vaclav Kotesovec, Non-attacking chess pieces, Sixth edition, p. 633, Feb 02 2013.
Vaclav Kotesovec, Mathematica program for this sequence
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.

Cf. A002464, A110128, A117574, A189255.

Column k=5 of A333706.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 16/n + 110/n^2)/e^2.

Terms a(25)-a(26) from Vaclav Kotesovec, Apr 20 2012

A248686 Triangular array of multinomial coefficients: T(n,k) = n!/(n(1)!n(2)! ... *n(k)!), where n(i) = floor((n + i - 1)/k) for i = 1 .. k.

Original entry on oeis.org

1, 1, 2, 1, 3, 6, 1, 6, 12, 24, 1, 10, 30, 60, 120, 1, 20, 90, 180, 360, 720, 1, 35, 210, 630, 1260, 2520, 5040, 1, 70, 560, 2520, 5040, 10080, 20160, 40320, 1, 126, 1680, 7560, 22680, 45360, 90720, 181440, 362880, 1, 252, 4200, 25200, 113400, 226800, 453600, 907200, 1814400, 3628800

Offset: 1

Clark Kimberling, Oct 11 2014

T(n,k) is the number of permutations p of [n] such that p(i)Alois P. Heinz, Feb 09 2023

			First seven rows:
  1
  1    2
  1    3     6
  1    6    12   24
  1   10    30   60    120
  1   20    90  180    360    720
  1   35   210  630   1260   2520   5040
  ...
Writing floor as [ ], the numbers comprising row 4 are
T(4,1) = 4!/[4/1]! = 24/24 = 1
T(4,2) = 4!/([4/2]![5/2]!) = 24/(2*2) = 6
T(4,3) = 4!/([4/3]![5/3]![6/3]!) = 24/(1*1*2) = 12
T(4,4) = 4!/([4/4]![5/4]![6/4]![7/4]!) = 24/(1*1*1*1) = 24.

Clark Kimberling, Table of n, a(n) for n = 1..5000

Main diagonal is A000142.
T(2n,n) gives A000680.
Row sums give A248687.
Cf. A333706.

T:= (n, k)-> combinat[multinomial](n, floor((n+i)/k)$i=0..k-1):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Feb 09 2023

f[n_, k_] := f[n, k] = n!/Product[Floor[(n + i)/k]!, {i, 0, k - 1}]
t = Table[f[n, k], {n, 0, 10}, {k, 1, n}];
u = Flatten[t]  (* A248686 sequence *)
TableForm[t]    (* A248686 array *)
Table[Sum[f[n, k], {k, 1, n}], {n, 1, 22}] (* A248687 *)

A189271 Number of permutations p of 1,2,...,n satisfying |p(i+6)-p(i)|<>6 for all 1<=i<=n-6.

Original entry on oeis.org

1, 2, 6, 24, 120, 720, 4800, 34752, 280512, 2528256, 25282560, 278323200, 3289036800, 42336448512, 589351062528, 8820501301248, 141215147788800, 2407845089203200, 43543159894318080, 832618225074748416, 16782891792284791296

Offset: 1

Vaclav Kotesovec, Apr 19 2011

a(n) is also number of ways to place n nonattacking pieces rook + leaper[6,6] on an n X n chessboard.

Vaclav Kotesovec, Table of n, a(n) for n = 1..24
Vaclav Kotesovec, Non-attacking chess pieces, Sixth edition, p. 633, Feb 02 2013.
Vaclav Kotesovec, Mathematica program for this sequence
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.

Cf. A002464, A110128, A117574, A189255, A189256.

Column k=6 of A333706.

Asymptotic (R. Tauraso 2006, quadratic term V. Kotesovec 2011): a(n)/n! ~ (1 + 20/n + 168/n^2)/e^2.

Generally (for this sequence is d=6): 1/e^2*(1+4(d-1)/n+2d*(3d-4)/n^2+...).

Terms a(23)-a(24) from Vaclav Kotesovec, Apr 21 2012

A361651 Number T(n,k) of permutations p of [n] such that p(i), p(i+k), p(i+2k),... form an up-down sequence for i in [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 2, 3, 6, 0, 5, 6, 12, 24, 0, 16, 20, 30, 60, 120, 0, 61, 80, 90, 180, 360, 720, 0, 272, 350, 420, 630, 1260, 2520, 5040, 0, 1385, 1750, 2240, 2520, 5040, 10080, 20160, 40320, 0, 7936, 10080, 13440, 15120, 22680, 45360, 90720, 181440, 362880

Offset: 0

Alois P. Heinz, Mar 19 2023

Number T(n,k) of permutations p of [n] such that p(i) < p(i+k) > p(i+2k) < ... for i <= k.

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = n! for k>=n.

			Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,    2;
  0,    2,    3,    6;
  0,    5,    6,   12,   24;
  0,   16,   20,   30,   60,  120;
  0,   61,   80,   90,  180,  360,   720;
  0,  272,  350,  420,  630, 1260,  2520,  5040;
  0, 1385, 1750, 2240, 2520, 5040, 10080, 20160, 40320;
  ...

Alois P. Heinz, Rows n = 0..150, flattened

Columns k=0-3 give: A000007, A000111, A361648, A367336.
Main diagonal gives A000142.
T(2n,n) gives A000680.
Cf. A248686, A333706.

b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(o-1+j, u-j), j=1..u))
    end:
T:= (n, k)-> `if`(n=0, 1, `if`(k=0, 0, (l-> mul(b(s, 0), s=l)*
    combinat[multinomial](n, l[]))([floor((n+i)/k)$i=0..k-1]))):
seq(seq(T(n, k), k=0..n), n=0..10);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[o-1+j, u-j], {j, 1, u}]];
T[n_, k_] := If[n == 0, 1, If[k == 0, 0, Function[l, Product[b[s, 0], {s, l}]*multinomial[n, l]][Table[Floor[(n+i)/k], {i, 0, k-1}]]]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Nov 22 2023, after Alois P. Heinz *)

A189849 a(0)=1, a(1)=0, a(n) = 4n(n-1)(a(n-1) + 2(n-1)*a(n-2)).

Original entry on oeis.org

1, 0, 16, 384, 23040, 2088960, 278323200, 50969640960, 12290021130240, 3774394191052800, 1438421245702963200, 666120016990568448000, 368420070161105761075200, 239869937154980747988172800, 181598769336835394381021184000, 158184707164826878472739618816000

Offset: 0

Stewart Herring, Apr 29 2011

The number of ways n couples can sit in rows of two seats with no person next to their partner.

a(n)/(2n)! gives the probability of this is and tends to exp(-1/2) as n tends to infinity.

G. C. Greubel, Table of n, a(n) for n = 0..224

Cf. A053871, A333706.

[(-2)^n*Factorial(n)*(&+[(-1/2)^k*Binomial(n,k)*Factorial(2*k)/Factorial(k): k in [0..n]]): n in [0..20]]; // G. C. Greubel, Jan 13 2018

a:= n-> (-2)^n*n!*add((-1/2)^i*binomial(n, i)*(2*i)!/i!, i=0..n): seq(a(n), n=0..20);

Table[(-2)^n*n!*Sum[(-1/2)^i*Binomial[n,i]*(2*i)!/i!,{i,0,n}],{n,1,20}]
RecurrenceTable[{a[0]==1,a[1]==0,a[n]==4n(n-1)(a[n-1]+2(n-1)a[n-2])},a,{n,20}] (* Harvey P. Dale, May 02 2012 *)

a[0]:1$ a[1]:0$ a[n]:=4*n*(n-1)*(a[n-1]+2*(n-1)*a[n-2])$ makelist(a[n], n, 0, 13);  /* Bruno Berselli, May 23 2011 */

for(n=0,30, print1((-2)^n*n!*sum(k=0,n, (-1/2)^k*binomial(n,k)*(2*k)!/k!), ", ")) \\ G. C. Greubel, Jan 13 2018

a(n) = (-2)^n*n!*hypergeom([ -n, 1/2],[],2).
a(n) = (n!)^2 times the coefficient of x^n in the expansion of exp(-2*x)/sqrt(1-4*x).
a(n) = 2^n*n!*A053871(n).
a(n) = A333706(2n,n). - Alois P. Heinz, Apr 10 2020

A333804 (1/16) times the number of permutations p of [n+2] such that |p(i+n) - p(i)| <> n for i in {1,2}.

Original entry on oeis.org

0, 0, 1, 5, 34, 258, 2172, 20220, 207000, 2315880, 28143360, 369411840, 5210956800, 78636096000, 1264324723200, 21579740582400, 389730550809600, 7425628898688000, 148865650053120000, 3132539179241472000, 69036795668865024000, 1590266397644660736000

Offset: 0

Alois P. Heinz, Apr 05 2020

nonn

			a(2) = 1: there are 16 permutations p of [4] such that |p(i+2) - p(i)| <> 2 for i in {1,2}: 1243, 1324, 1342, 1423, 2134, 2314, 2413, 2431, 3124, 3142, 3241, 3421, 4132, 4213, 4231, 4312.

Alois P. Heinz, Table of n, a(n) for n = 0..448
Wikipedia, Permutation

Cf. A333706.

a:= proc(n) option remember; `if`(n<3, (n-1)*n/2, a(n-1)*
     (n-2)*(n^4+2*n^3-9*n^2+6*n+8)/(n^4-2*n^3-9*n^2+26*n-8))
    end:
seq(a(n), n=0..23);

E.g.f.: 1/(2*x-2)-1/(8*(x-1)^3)+log(1-x)*(1-x)/2+(5*x+3)/8.

a(n) = A333706(n+2,n)/16.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A110128 Number of permutations p of 1,2,...,n satisfying |p(i+2)-p(i)| not equal to 2 for all 0

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A117574 Total number of permutations p of [n] such that |p(i+3) - p(i)| is not equal to 3 for 1 <= i <= n-3.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A189255 Number of permutations p of 1,2,...,n satisfying |p(i+4)-p(i)|<>4 for all 1<=i<=n-4.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A189256 Number of permutations p of 1,2,...,n satisfying |p(i+5)-p(i)|<>5 for all 1<=i<=n-5.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A248686 Triangular array of multinomial coefficients: T(n,k) = n!/(n(1)!*n(2)!* ... *n(k)!), where n(i) = floor((n + i - 1)/k) for i = 1 .. k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A189271 Number of permutations p of 1,2,...,n satisfying |p(i+6)-p(i)|<>6 for all 1<=i<=n-6.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A361651 Number T(n,k) of permutations p of [n] such that p(i), p(i+k), p(i+2k),... form an up-down sequence for i in [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

A248686 Triangular array of multinomial coefficients: T(n,k) = n!/(n(1)!n(2)! ... *n(k)!), where n(i) = floor((n + i - 1)/k) for i = 1 .. k.

A189849 a(0)=1, a(1)=0, a(n) = 4n(n-1)(a(n-1) + 2(n-1)*a(n-2)).