A002464 -id:A002464 - cp's OEIS frontend

A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.

1, 0, 2, 0, 4, 2, 2, 10, 10, 2, 14, 40, 48, 16, 2, 90, 230, 256, 120, 22, 2, 646, 1580, 1670, 888, 226, 28, 2, 5242, 12434, 12846, 7198, 2198, 366, 34, 2, 47622, 110320, 112820, 64968, 22120, 4448, 540, 40, 2, 479306, 1090270, 1108612, 650644, 236968, 54304, 7900, 748, 46, 2

Offset: 1

N. J. A. Sloane, Aug 19 2003

Number of permutations of 12...n such that exactly k of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

			Triangle T(n,k) begins (n >= 1, k = 0..n-1):
    1;
    0,    2;
    0,    4,    2;
    2,   10,   10,   2;
   14,   40,   48,  16,   2;
   90,  230,  256, 120,  22,  2;
  646, 1580, 1670, 888, 226, 28, 2;
  ...

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
J. Riordan, A recurrence for permutations without rising or falling successions. Ann. Math. Statist. 36 (1965), 708-710.
David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag.

Alois P. Heinz, Rows n = 1..141, flattened
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.

Columns give A002464, A086852, A086853, A086854, A086955.
Triangle in A086856 multiplied by 2. Cf. A010028.
Cf. A322294, A322295, A322296.

S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
       [n+1], expand((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)))
    end:
T:= (n, k)-> coeff(S(n), t, k):
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Jan 11 2013

s[n_] := s[n] = If[n < 4, {1, 1, 2*t, 4*t + 2*t^2}[[n + 1]], Expand[(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]]]; t[n_, k_] := Ceiling[Coefficient[s[n], t, k]]; Flatten[ Table[ Table[t[n, k], {k, 0, n - 1}], {n, 1, 10}]] (* Jean-François Alcover, Jan 25 2013, translated from Alois P. Heinz's Maple program *)

Let T{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} T{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].

T(n, 0) = n! + Sum_{i=1..m-1} (-1)^i*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), and T(n, k) = Sum_{i=1..m-1} (-1)^(i-k)*binomial(i, k)*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), for k >= 1, and n >= 1. See the D. P.Robbins link for A(n, k) = T(n, k), and his comment concerning the case k = i = 0 . - Wolfdieter Lang, May 17 2025

A333706 Number T(n,k) of permutations p of [n] such that |p(i+k) - p(i)| <> k for i in [n-k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 4, 6, 0, 2, 16, 20, 24, 0, 14, 44, 80, 108, 120, 0, 90, 200, 384, 544, 672, 720, 0, 646, 1288, 2240, 3264, 4128, 4800, 5040, 0, 5242, 9512, 15424, 23040, 28992, 34752, 38880, 40320, 0, 47622, 78652, 123456, 176832, 231936, 280512, 323520, 352800, 362880

Offset: 0

Alois P. Heinz, Apr 02 2020

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,    0,    2;
  0,    0,    4,     6;
  0,    2,   16,    20,    24;
  0,   14,   44,    80,   108,   120;
  0,   90,  200,   384,   544,   672,   720;
  0,  646, 1288,  2240,  3264,  4128,  4800,  5040;
  0, 5242, 9512, 15424, 23040, 28992, 34752, 38880, 40320;
  ...

Alois P. Heinz, Rows n = 0..20, flattened
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11.
Wikipedia, Permutation

Columns k=0-10 (for n>=k) give: A000007, A002464, A110128, A117574, A189255, A189256, A189271, A360384, A360386, A360462, A360463.
Main diagonal gives A000142.
T(2n,n) gives A189849.
T(n+1,n) gives 4*A138772(n).
T(n+2,n) gives 16*A333804(n).
Cf. A000170 (condition is satisfied for all k), A248686 (p(i) at distance k are sorted).

A086852 Number of permutations of length n with exactly 1 rising or falling succession.

Original entry on oeis.org

0, 0, 2, 4, 10, 40, 230, 1580, 12434, 110320, 1090270, 11876980, 141373610, 1825321016, 25405388150, 379158271420, 6039817462210, 102278890975360, 1834691141852174, 34752142215026180, 693126840194499290, 14519428780464454600, 318705819455462421670

Offset: 0

N. J. A. Sloane, Aug 19 2003

Permutations of 12...n such that exactly one of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

For the number of such permutations without (n-1)n or n(n-1) see A383857(n), for n >= 1. - Wolfdieter Lang, May 22 2025

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Sergey Kitaev, Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
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.

Cf. A002464, A086853, A086854, A000349, A001267, A383857.
Twice A000130. A diagonal of A001100.
Cf. A104698, A384494.

S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
       [n+1], expand((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)))
    end:
a:= n-> coeff(S(n), t, 1):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 21 2012

S[n_] := S[n] = If[n<4, {1, 1, 2*t, 4*t+2*t^2}[[n+1]], Expand[(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_] := Coefficient[S[n], t, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

Coefficient of t^1 in S[n](t) defined in A002464.
(3-n)*a(n) +(n+1)*(n-3)*a(n-1) -(n^2-4*n+5)*a(n-2) -(n-1)*(n-5)*a(n-3) +(n-1)*(n-2)*a(n-4)=0. - R. J. Mathar, Jun 06 2013
a(n) ~ 2*sqrt(2*Pi)*n!/exp(2) = 0.678470495... * n!. - Vaclav Kotesovec, Aug 10 2013
From Wolfdieter Lang, May 31 2025: (Start)
a(n) = Sum_{i=1..n-1} (-1)^(i-1)*i*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), for n >= 0. See the D. P. Robbins link, p. 123, eq. (7), A(n, 1).
a(n+2) = Sum_{k=0..n} 2*R(n, k)*B(n, k), with B(n, k) = A384494(n, k) = (-1)^k*(k+1)*(n+1-k)!, and R(n, k) = A104698(n, k), for n >= 0. This equals (2*MR*MB^t)_{n,n}, with the (infinite) square matrices with vanishing upper diagonals corresponding to R and B, and t indicates transposition. (End)

A000130 One-half the number of permutations of length n with exactly 1 rising or falling successions.

Original entry on oeis.org

0, 0, 1, 2, 5, 20, 115, 790, 6217, 55160, 545135, 5938490, 70686805, 912660508, 12702694075, 189579135710, 3019908731105, 51139445487680, 917345570926087, 17376071107513090, 346563420097249645, 7259714390232227300, 159352909727731210835, 3657569576966074846118

Offset: 0

N. J. A. Sloane

nonn

(1/2) times number of permutations of 12...n such that exactly one of the following occurs: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).

Partial sums seem to be in A000239. - Ralf Stephan, Aug 28 2003

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
J. Riordan, A recurrence for permutations without rising or falling successions. Ann. Math. Statist. 36 (1965), 708-710.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..200

Cf. A002464, A086853. Equals A086852/2. A diagonal of A010028.

S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
       [n+1], expand((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)))
    end:
a:= n-> coeff(S(n), t, 1)/2:
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 21 2012

S[n_] := S[n] = If[n<4, {1, 1, 2*t, 4*t+2*t^2}[[n+1]], Expand[(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_] := Coefficient[S[n], t, 1]/2; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)

Coefficient of t^1 in S[n](t) defined in A002464, divided by 2.

a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Sep 11 2014

A137774 Number of ways to place n nonattacking empresses on an n X n board.

Original entry on oeis.org

1, 2, 2, 8, 20, 94, 438, 2766, 19480, 163058, 1546726, 16598282, 197708058, 2586423174, 36769177348, 563504645310, 9248221393974, 161670971937362, 2996936692836754, 58689061747521430, 1210222434323163704, 26204614054454840842, 594313769819021397534, 14086979362268860896282

Offset: 1

Vaclav Kotesovec, Jan 27 2011

An empress moves like a rook and a knight.

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Separators - a new statistic for permutations, arXiv:1905.12364 [math.CO], 2019.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, On the Sparseness of the Downsets of Permutations via Their Number of Separators, Enumerative Combinatorics and Applications (2021) Vol. 1, No. 3, Article #S2R21.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.685 and 636.
W. Schubert, N-Queens page

Cf. A201513, A000170, A002465, A201540.
Cf. A185085, A051223, A244284, A201511, A201861, A137774, A245011.
Cf. A218244, A002464, A110128, A117574, A089222, A002493.

Asymptotics (Vaclav Kotesovec, Jan 26 2011): a(n)/n! -> 1/e^4.
General asymptotic formulas for number of ways to place n nonattacking pieces rook + leaper[r,s] on an n X n board:
a(n)/n! -> 1/e^2 for 0a(n)/n! -> 1/e^4 for 0

Terms a(16)-a(17) from Vaclav Kotesovec, Feb 06 2011
Terms a(18)-a(19) from Wolfram Schubert, Jul 24 2011
Terms a(20)-a(24) (computed by Wolfram Schubert), Vaclav Kotesovec, Aug 25 2012

A095816 Number of permutations of 1..n with no three elements in correct or reverse order.

Original entry on oeis.org

1, 1, 2, 4, 18, 92, 570, 4082, 33292, 304490, 3086890, 34357812, 416526730, 5463479106, 77094352076, 1164544912938, 18749754351338, 320544941916628, 5799226664694602, 110695180631374114, 2223242026407894732, 46868311165318977130, 1034758905785710599402

Offset: 0

Jonas Wallgren, Jun 08 2004

nonn

Counts permutations with the property that no subsequence i(i+1)(i+2) or (i+2)(i+1)i occurs.

Andrew Howroyd, Table of n, a(n) for n = 0..200
W. M. Dymacek and I. Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2, J. Int. Seq. 14 (2011) # 11.1.6, Table 1.
D. M. Jackson and R. C. Read, A note on permutations without runs of given length, Aequationes Math. 17 (1978), no. 2-3, 336-343.

Cf. A002464, A095817, A095818.

Cf. A165963, A165964, A078628. [From Isaac Lambert, Oct 07 2009]

seq(n)={my(m=3); Vec(sum(k=0, n, k!*((2*x^m-x^(m+1)-x)/(x^m-1) + O(x*x^n))^k))} \\ Andrew Howroyd, Aug 31 2018

G.f. Sum_{n>=0} n!*((2*x^m-x^(m+1)-x)/(x^m-1))^n where m = 3. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007
From Vaclav Kotesovec, May 26 2023: (Start)
a(n) ~ n! * (1 - 2/n + 6/n^2 - 28/(3*n^3) - 10/(3*n^4) + 496/(15*n^5) + 1384/(45*n^6) - 79724/(315*n^7) - 259306/(315*n^8) + 3718094/(2835*n^9) + 33233992/(2025*n^10) + ...).
a(n) = (n-3)*a(n-1) + 3*(n-1)*a(n-2) + (2*n-5)*a(n-3) - (n-3)*a(n-4) - (2*n-13)*a(n-5) - (n-8)*a(n-6) + (n-6)*a(n-7).
(End)

More terms from Ivana Jovovic (ivana121(AT)EUnet.yu), Nov 11 2007

a(0)=1 prepended by Max Alekseyev, Jun 14 2011

A104698 Triangle read by rows: T(n,k) = Sum_{j=0..n-k} binomial(k, j)*binomial(n-j+1, k+1).

Original entry on oeis.org

1, 2, 1, 3, 4, 1, 4, 9, 6, 1, 5, 16, 19, 8, 1, 6, 25, 44, 33, 10, 1, 7, 36, 85, 96, 51, 12, 1, 8, 49, 146, 225, 180, 73, 14, 1, 9, 64, 231, 456, 501, 304, 99, 16, 1, 10, 81, 344, 833, 1182, 985, 476, 129, 18, 1, 11, 100, 489, 1408, 2471, 2668, 1765, 704, 163, 20, 1, 12

Offset: 0

Gary W. Adamson, Mar 19 2005

The n-th column of the triangle is the binomial transform of the n-th row of A081277, followed by zeros. Example: column 3, (1, 6, 19, 44, ...) = binomial transform of row 3 of A081277: (1, 5, 8, 4, 0, 0, 0, ...). A104698 = reversal by rows of A142978. - Gary W. Adamson, Jul 17 2008
This sequence is jointly generated with A210222 as an array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1) + 1 and v(n,x) = 2x*u(n-1,x) + v(n-1,x) + 1. See the Mathematica section at A210222. - Clark Kimberling, Mar 19 2012
This Riordan triangle T appears in a formula for A001100(n, 0) = A002464(n), for n >= 1. - Wolfdieter Lang, May 13 2025

			The Riordan triangle T begins:
  n\k  0   1   2    3    4    5    6   7   8  9 10 ...
  ----------------------------------------------------
  0:   1
  1:   2   1
  2:   3   4   1
  3:   4   9   6    1
  4:   5  16  19    8    1
  5:   6  25  44   33   10    1
  6:   7  36  85   96   51   12    1
  7:   8  49 146  225  180   73   14   1
  8:   9  64 231  456  501  304   99  16   1
  9:  10  81 344  833 1182  985  476 129  18  1
  10: 11 100 489 1408 2471 2668 1765 704 163 20  1
  ... reformatted and extended by _Wolfdieter Lang_, May 13 2025
From _Wolfdieter Lang_, May 13 2025: (Start)
Zumkeller recurrence (adapted for offset [0,0]): 19 = T(4, 2) = T(2, 1) + T(3, 1) + T(3,3) = 4 + 9 + 6 = 19.
A-sequence recurrence: 19 = T(4, 2) = 1*T(3. 1) + 2*T(3. 2) - 2*T(3, 3) = 9 + 12 - 2 = 19.
Z-sequence recurrence: 5 = T(4, 0) = 2*T(3, 0) - 1*T(3, 1) + 2*T(3, 2) - 6*T(3, 3) = 8 - 9 + 12 + 6 = 5.
Boas-Buck recurrence: 19 = T(4, 2) = (1/2)*((2 + 0)*T(2, 2) + (2 + 2*2)*T(3, 2)) = (1/2)*(2 + 36) = 19. (End)

Reinhard Zumkeller, First 100 rows of triangle, flattened

Diagonal sums are A008937(n+1).
Cf. A048739 (row sums), A008288, A005900 (column 3), A014820 (column 4)
Cf. A081277, A142978 by antidiagonals, A119328, A110271 (matrix inverse).
Cf. A001100, A002464, A010673, A040000, A112478, A133872, A383857.

a104698 n k = a104698_tabl !! (n-1) !! (k-1)
a104698_row n = a104698_tabl !! (n-1)
a104698_tabl = [1] : [2,1] : f [1] [2,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) ([0] ++ us ++ [0]) $
          zipWith (+) ([1] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Jul 17 2015

A104698 := proc(n, k) add(binomial(k, j)*binomial(n-j+1, n-k-j), j=0..n-k) ; end proc:
seq(seq(A104698(n, k), k=0..n), n=0..15); # R. J. Mathar, Sep 04 2011
T := (n, k) -> binomial(n + 1, k + 1)*hypergeom([-k, k - n], [-n - 1], -1):
for n from 0 to 9 do seq(simplify(T(n, k)), k = 0..n) od;
T := proc(n, k) option remember; if k = 0 then n + 1 elif k = n then 1 else T(n-2, k-1) + T(n-1, k-1) + T(n-1, k) fi end: # Peter Luschny, May 13 2025

u[1, ] = 1; v[1, ] = 1;
u[n_, x_] := u[n, x] = x u[n-1, x] + v[n-1, x] + 1;
v[n_, x_] := v[n, x] = 2 x u[n-1, x] + v[n-1, x] + 1;
Table[CoefficientList[u[n, x], x], {n, 1, 11}] // Flatten (* Jean-François Alcover, Mar 10 2019, after Clark Kimberling *)

T(n,k)=sum(j=0,n-k,binomial(k,j)*binomial(n-j+1,k+1)) \\ Charles R Greathouse IV, Jan 16 2012

The triangle is extracted from the product A * B; A = [1; 1, 1; 1, 1, 1; ...], B = [1; 1, 1; 1, 3, 1; 1, 5, 5, 1; ...] both infinite lower triangular matrices (rest of the terms are zeros). The triangle of matrix B by rows = A008288, Delannoy numbers.
From Paul Barry, Jul 18 2005: (Start)
Riordan array (1/(1-x)^2, x(1+x)/(1-x)) = (1/(1-x), x)*(1/(1-x), x(1+x)/(1-x)).
T(n, k) = Sum_{j=0..n} Sum_{i=0..j-k} C(j-k, i)*C(k, i)*2^i.
T(n, k) = Sum_{j=0..k} Sum_{i=0..n-k-j} (n-k-j-i+1)*C(k, j)*C(k+i-1, i). (End)
T(n, k) = binomial(n+1, k+1)*2F1([-k, k-n], [-n-1], -1) where 2F1 is a Gaussian hypergeometric function. - R. J. Mathar, Sep 04 2011
T(n, k) = T(n-2, k-1) + T(n-1, k-1) + T(n-1, k) for 1 < k < n; T(n, 0) = n + 1; T(n, n) = 1. - Reinhard Zumkeller, Jul 17 2015
From Wolfdieter Lang, May 13 2025: (Start)
The Riordan triangle T = (1/(1 - x)^2, x*(1 + x)/(1 - x)) has the o.g.f. G(x, y) = 1/((1 - x)*(1 - x - y*x*(1+x))) for the row polynomials R(n, y) = Sum_{k=0..n} T(n, k)*y^k.
The o.g.f. for column k is G(k, x) = (1/(1 - x)^2)*(x*(1 + x)/(1 - x))^k, for k >= 0.
The o.g.f. for the diagonal m is D(m, x) = N(m, x)/(1 - x)^(m+1), with the numerator polynomial N(m, x) = Sum_{k=0..floor(m/2)} A034867(m, k)*x^(2*k) for m >= 0.
The row sums with o.g.f. R(x) = 1/((1 -x)*(1 - 2*x -x^2) give A048739.
The alternating row sums with o.g.f. 1/((1 - x)(1 + x^2)) give A133872.
The A-sequence for this Riordan triangle has o.g.f. A(x) = 1 + x + sqrt(1 + 6*x + x^2))/2 giving A112478(n). Hence T(n, k) = Sum_{j=0..n-k} A112478(j)*T(n-1, k-1+j), for n >= 1, k >= 1, T(n, k) = 0 for n < k, and T(0, 0) = 1.
The Z-sequence has o.g.f. (5 + x - sqrt(1 + 6*x + x^2))/2 = 3 + x - A(x) giving Z(n) = {2, -1, -A112478(n >= 2)}. Hence T(n, 0) = Sum_{j=0..n-1} Z(j)*T(n-1, j), for n >= 1. For A- and Z-sequences of Riordan triangles see a W. Lang link at A006232 with references.
The Boas-Buck sequences alpha and beta for the Riordan triangle T (see A046521 for the Aug 10 2017 comment and reference) are alpha(n) = A040000(n+1) = repeat{2} and beta(n) = A010673(n+1) = repeat{2,0}. Hence the recurrence for column T(n, k){n>=k}, with input T(k, k) = 1, for k >= 0, is T(n, k) = (1/(n-k)) * Sum{j=k..n-1} (2 + k*(1 + (-1)^(n-1-j))) *T(j,k), for n >= k+1. (End)

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

A382644 Number of king permutations on n elements not beginning with the smallest element.

Original entry on oeis.org

1, 0, 0, 0, 2, 12, 78, 568, 4674, 42948, 436358, 4860432, 58918602, 772364956, 10889141262, 164314043112, 2642564012498, 45124893118068, 815444024669334, 15547394518030528, 311913179428480218, 6568416226627210572, 144868131187935525662, 3339555055674217441176, 80315570986097045133282

Offset: 0

Dan Li, Apr 01 2025

A permutation p(1)p(2)...p(n) is a king permutation if |p(i+1)-p(i)|>1 for each 0

			For n = 4 the a(4) = 2 solutions are the two permutations 2413 and 3142.
For n = 5 the a(5) = 12 solutions are these 12 permutations: 24135, 24153, 25314, 31425, 31524, 35142, 35241, 41352, 42513, 42531, 52413, and 53142.

Alois P. Heinz, Table of n, a(n) for n = 0..450
Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See formula (2) at page 5.

Cf. A001266, A002464, A382645.

a:= proc(n) option remember; `if`(n<4, [1,0$3][n+1],
      (n+1)*a(n-1)-(n-3)*(a(n-2)+a(n-3))+(n-2)*a(n-4))
    end:
seq(a(n), n=0..24);  # Alois P. Heinz, Apr 04 2025

nmax = 20; CoefficientList[Series[Sum[k!*x^k*(1-x)^k/(1+x)^(k+1), {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Apr 04 2025 *)

my(N=30, t='t+O('t^N)); Vec(sum(n=0,N,n!*t^n*(1-t)^n/(1+t)^(n+1))) \\ Joerg Arndt, Apr 03 2025

G.f.: Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^(n+1).
a(n) = (n+1)*a(n-1) - (n-3)*(a(n-2)+a(n-3)) + (n-2)*a(n-4) for n>=4. - Alois P. Heinz, Apr 04 2025
a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Apr 04 2025

Showing 1-10 of 66 results. Next

cp's OEIS Frontend

A033169 Erroneous version of A002464.

Views

Author

Keywords

A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A333706 Number T(n,k) of permutations p of [n] such that |p(i+k) - p(i)| <> k for i in [n-k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A086852 Number of permutations of length n with exactly 1 rising or falling succession.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A000130 One-half the number of permutations of length n with exactly 1 rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A137774 Number of ways to place n nonattacking empresses on an n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A095816 Number of permutations of 1..n with no three elements in correct or reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A104698 Triangle read by rows: T(n,k) = Sum_{j=0..n-k} binomial(k, j)*binomial(n-j+1, k+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell