A002464 -id:A002464 - cp's OEIS frontend

A382645 Number of king permutations on n elements not beginning with the smallest element and not ending with the largest element.

1, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848, 54455754, 717909202, 10171232060, 154142811052, 2488421201446, 42636471916622, 772807552752712, 14774586965277816, 297138592463202402, 6271277634164008170, 138596853553771517492, 3200958202120445923684, 77114612783976599209598

Offset: 0

Dan Li, Apr 01 2025

nonn

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) = 10 solutions are these 10 permutations: 24153, 25314, 31524, 35142, 35241, 41352, 42513, 42531, 52413, and 53142.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See formula (3) at page 5.

Cf. A002464, A382644.

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

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

G.f.: t/(1+t) + Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^(n+2).

a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Apr 04 2025

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

Original entry on oeis.org

0, 0, 0, 1, 5, 24, 128, 835, 6423, 56410, 554306, 6016077, 71426225, 920484892, 12793635300, 190730117959, 3035659077083, 51371100102990, 920989078354838, 17437084517068465, 347647092476801301, 7280060180210901232, 159755491837445900120, 3665942433747225901707

Offset: 0

N. J. A. Sloane

nonn

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

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, A000130, A086852. Equals A086853/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-> ceil(coeff(S(n), t, 2)/2):
seq(a(n), n=0..25);  # 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]]]; a[n_] := Ceiling[Coefficient[S[n], t, 2]/2]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

Coefficient of t^2 in S[n](t) defined in A002464, divided by 2.
Recurrence: (n-3)*(n-2)*(n-4)^3*a(n) = (n-3)*(n^4-9*n^3+23*n^2-4*n-29)*(n-4)*a(n-1) - (n-1)*(n^4-12*n^3+57*n^2-125*n+104)*(n-4)*a(n-2) - (n-2)*(n-1)*(n^4-15*n^3+83*n^2-198*n+169)*a(n-3) + (n-3)^3*(n-2)^2*(n-1)*a(n-4). - Vaclav Kotesovec, Aug 10 2013
a(n) ~ sqrt(2*Pi)*n^(n+1/2)/exp(n+2). - Vaclav Kotesovec, Aug 10 2013

A010028 Triangle read by rows: T(n,k) is one-half the number of permutations of length n with exactly n-k rising or falling successions, for n >= 1, 1 <= k <= n. T(1,1) = 1 by convention.

Original entry on oeis.org

1, 1, 0, 1, 2, 0, 1, 5, 5, 1, 1, 8, 24, 20, 7, 1, 11, 60, 128, 115, 45, 1, 14, 113, 444, 835, 790, 323, 1, 17, 183, 1099, 3599, 6423, 6217, 2621, 1, 20, 270, 2224, 11060, 32484, 56410, 55160, 23811, 1, 23, 374, 3950, 27152, 118484, 325322, 554306, 545135, 239653

Offset: 1

N. J. A. Sloane

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

			Triangle T(n,k) begins:
  1;
  1,  0;
  1,  2,   0;
  1,  5,   5,    1;
  1,  8,  24,   20,    7;
  1, 11,  60,  128,  115,   45;
  1, 14, 113,  444,  835,  790,  323;
  1, 17, 183, 1099, 3599, 6423, 6217, 2621;
  ...

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

Alois P. Heinz, Rows n = 1..141, flattened
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

Diagonals give A001266 (and A002464), A000130, A000349, A001267, A001268.
Triangle in A086856 transposed. Cf. A001100.
Row sums give A001710.

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)-> ceil(coeff(S(n), t, n-k)/2):
seq(seq(T(n, k), k=1..n), n=1..12);  # 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]]]; T[n_, k_] := Ceiling[Coefficient[S[n], t, n-k]/2]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 14 2014, translated from Alois P. Heinz's Maple code *)

For n>1, coefficient of t^(n-k) in S[n](t) defined in A002464, divided by 2.

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

A001266 One-half the number of permutations of length n without rising or falling successions.

Original entry on oeis.org

0, 0, 1, 7, 45, 323, 2621, 23811, 239653, 2648395, 31889517, 415641779, 5830753109, 87601592187, 1403439027805, 23883728565283, 430284458893701, 8181419271349931, 163730286973255373, 3440164703027845395, 75718273707281368117, 1742211593431076483419

Offset: 2

N. J. A. Sloane

nonn

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

a(n) is also the number of Hamiltonian paths in the n-path complement graph. - Eric W. Weisstein, Apr 11 2018

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).

Seiichi Manyama, Table of n, a(n) for n = 2..450 (first 199 terms from Alois P. Heinz)
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Path Complement Graph

Sequence A002464 divided by 2 for n >= 2. A diagonal of A010028. A086856.

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, 0)/2:
seq(a(n), n=2..25);  # 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]]]; a[n_] := Coefficient[S[n], t, 0]/2; Table[a[n], {n, 2, 25}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)
CoefficientList[Series[((Exp[(1 + x)/((-1 + x) x)] (1 + x) Gamma[0, (1 + x)/((-1 + x) x)])/((-1 + x) x) - x - 1)/(2 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/2,
a[2] == a[3] == 0}, a, {n, 2, 20}] (* Eric W. Weisstein, Apr 11 2018 *)

a(n) = A002464(n)/2 = A086856(n, 0).

(1/2) times coefficient of t^0 in S[n](t) defined in A002464.

More terms from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Feb 16 2001

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

Original entry on oeis.org

0, 0, 0, 0, 1, 8, 60, 444, 3599, 32484, 325322, 3582600, 43029621, 559774736, 7841128936, 117668021988, 1883347579515, 32026067455084, 576605574327174, 10957672400252944, 219190037987444577, 4603645435776504120, 101292568208941883236, 2329975164242735146316

Offset: 0

N. J. A. Sloane

nonn

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

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).

Alois P. Heinz, Table of n, a(n) for n = 0..200
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

Cf. A002464, A000130, A086852. Equals A086854/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, 3)/2:
seq(a(n), n=0..25);  # 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]]]; a[n_] := Coefficient[S[n], t, 3]/2; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

Coefficient of t^3 in S[n](t) defined in A002464, divided by 2.
a(n) ~ 2/(3*exp(2)) * n!. - Vaclav Kotesovec, Aug 10 2013
Recurrence: (n-4)*(2*n^6 - 52*n^5 + 557*n^4 - 3136*n^3 + 9740*n^2 - 15727*n + 10242)*a(n) =  + (n-4)*(2*n^7 - 50*n^6 + 511*n^5 - 2693*n^4 + 7450*n^3 - 9041*n^2 - 157*n + 6666)*a(n-1) - (2*n^8 - 58*n^7 + 735*n^6 - 5289*n^5 + 23430*n^4 - 64575*n^3 + 106105*n^2 - 92312*n + 30900)*a(n-2) - (2*n^7 - 54*n^6 + 615*n^5 - 3795*n^4 + 13554*n^3 - 27681*n^2 + 29473*n - 12330)*(n-2)*a(n-3) + (2*n^6 - 40*n^5 + 327*n^4 - 1388*n^3 + 3184*n^2 - 3675*n + 1626)*(n-2)^2*a(n-4). - Vaclav Kotesovec, Aug 10 2013

A086853 Number of permutations of length n with exactly 2 rising or falling successions.

Original entry on oeis.org

0, 0, 0, 2, 10, 48, 256, 1670, 12846, 112820, 1108612, 12032154, 142852450, 1840969784, 25587270600, 381460235918, 6071318154166, 102742200205980, 1841978156709676, 34874169034136930, 695294184953602602, 14560120360421802464, 319510983674891800240

Offset: 0

N. J. A. Sloane, Aug 19 2003

nonn

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

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
J. Riordan, A recurrence for permutations without rising or falling successions, Ann. Math. Statist. 36 (1965), 708-710.

Cf. A002464, A000130, A000349, A001267, A086852, A086854. A diagonal of A001100.

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-> ceil(coeff(S(n), t, 2)):
seq(a(n), n=0..25);  # 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]]; a[n_] := t[n, 2]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

Coefficient of t^2 in S[n](t) defined in A002464.
Conjecture: (-514*n+2465)*a(n) +2*(257*n^2-955*n-1085)*a(n-1) +(-555*n^2+2483*n-1670)*a(n-2) +16*(-17*n^2+73*n-75)*a(n-3) +(354*n^2+528*n-2299)*a(n-4) +2*(-121*n^2+1045*n-1401)*a(n-5) +3*(67*n-115)*(n-4)*a(n-6)=0. - R. J. Mathar, Jun 06 2013
shorter recurrence: (n-3)*(n-2)*(n-4)^3*a(n) = (n-3)*(n^4-9*n^3+23*n^2-4*n-29)*(n-4)*a(n-1) - (n-1)*(n^4-12*n^3+57*n^2-125*n+104)*(n-4)*a(n-2) - (n-2)*(n-1)*(n^4-15*n^3+83*n^2-198*n+169)*a(n-3) + (n-3)^3*(n-2)^2*(n-1)*a(n-4). - Vaclav Kotesovec, Aug 10 2013
a(n) ~ 2*exp(-2) * n!. - Vaclav Kotesovec, Aug 10 2013

A089222 Number of ways of seating n people around a table for the second time without anyone sitting next to the same person as they did the first time.

Original entry on oeis.org

1, 0, 0, 0, 0, 10, 36, 322, 2832, 27954, 299260, 3474482, 43546872, 586722162, 8463487844, 130214368530, 2129319003680, 36889393903794, 675098760648204, 13015877566642418, 263726707757115400, 5603148830577775218, 124568968969991162100, 2892414672938546871250

Offset: 0

Udi Hadad (somebody(AT)netvision.net.il), Dec 22 2003

A078603 counts these arrangements up to circular symmetry (i.e., two arrangements are the same if one can be rotated to give the other). A002816 counts them up to dihedral symmetry (i.e., two arrangements are the same if one can be rotated or reflected to give the other). - Joel B. Lewis, Jan 28 2010

			a(4)=0 because trying to arrange 1,2,3,4 around a table will always give a couple who is sitting next to each other and differ by 1.

J. Snell, Introduction to Probability, e-book, pp. 101 Q. 20.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Art of Problem Solving forum, Random neighbors. - _Joel B. Lewis_, Jan 28 2010
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
Charles M. Grinstead and J. Laurie Snell, Introduction to Probability.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 626.
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. Note that in this paper a(1) = 1. See Column 2 in the table on page 3.

Cf. A002464, A002816, A078603, A078630, A078631.

Same[cperm_, n_] := ( For[same = False; i = 2, (i <= n) && ! same, i++, same = ((Mod[cperm[[i - 1]], n] + 1) == cperm[[i]]) || ((Mod[cperm[[ i]], n] + 1) == cperm[[i - 1]])]; same = same || ((Mod[cperm[[n]], n] + 1) == cperm[[1]]) || ((Mod[ cperm[[1]], n] + 1) == cperm[[n]]); Return[same]); CntSame[n_] := (allPerms = Permutations[Range[n]]; count = 0; For[j = 1, j <= n!, j++, perm = allPerms[[j]]; If[ ! Same[perm, n], count++ ]]; Return[count]);
(* or direct computation of terms *)
Table[If[n<3, 0, n! + (-1)^n*2n + Sum[(-1)^r*(n/(n-r))^2 * (n-r)! * Sum[2^c * Binomial[r-1,c-1] * Binomial[n-r,c], {c,1,r}], {r,1,n-1}]], {n,1,25}] (* Vaclav Kotesovec, Apr 06 2012 *)

Inclusion-exclusion gives that for n > 2, we have a(n) = n! + 2*n*(-1)^n + Sum_{1 <= k <= m < n} (-1)^m * (n/k) * binomial(n-m-1, k-1) * binomial(m-1, k-1) * 2^k * n * (n-m-1)!. - Joel B. Lewis, Jan 28 2010
a(n) = (3*n-30)*a(n-11) + (6*n-45)*a(n-10) + (5*n+18)*a(n-9) - (8*n-139)*a(n-8) - (26*n-204)*a(n-7) - (4*n-30)*a(n-6) + (26*n-148)*a(n-5) + (8*n-74)*a(n-4) - (9*n-18)*a(n-3) - (2*n-15)*a(n-2) + (n+2)*a(n-1), n >= 14. - Vaclav Kotesovec, Apr 13 2010
The asymptotic expansion from article by Aspvall and Liang (also cited in article by Tauraso) is wrong. Bad terms are 736/(15*n^5) + 8428/(45*n^6) + 40174/(63*n^7). Right asymptotic formula is a(n) ~ (n!/e^2)*(1 - 4/n + 20/(3*n^3) + 58/(3*n^4) + 796/(15*n^5) + 7858/(45*n^6) + 40324/(63*n^7) + 140194/(63*n^8) + ...). Verified also numerically. For example, for n=200, exact/asymptotic results are 1.0000000000125542243 (Aspvall + Liang), 1.0000000000000008990 (Kotesovec 7 terms) or 1.0000000000000000121 (Kotesovec 8 terms). - Vaclav Kotesovec, Apr 06 2012
a(n) = 2*n*A002816(n) for n > 1. - Martin Renner, Apr 01 2022

Tauraso reference from Parthasarathy Nambi, Dec 21 2006
More terms from Vladeta Jovovic, Nov 29 2009
a(0)=1 prepended by Alois P. Heinz, Jul 31 2019

A326411 Triangle T(n,k) read by rows: T(n,k) = the number of ways of seating n people around a table for the second time so that k pairs are maintained. Reflected and rotated sequences are counted as one.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 2, 0, 1, 1, 0, 5, 5, 0, 1, 3, 12, 15, 20, 9, 0, 1, 23, 70, 112, 91, 49, 14, 0, 1, 177, 544, 740, 640, 302, 96, 20, 0, 1, 1553, 4500, 6003, 4725, 2439, 747, 165, 27, 0, 1, 14963, 41740, 53585, 41420, 20810, 7076, 1550, 260, 35, 0, 1

Offset: 0

Witold Tatkiewicz, Aug 07 2019

Poulet (1919) arrives at this triangle of numbers by considering n-sided polygons whose vertices lie on a circle. Call a side of such a polygon simple if its endpoints are adjacent on the circle. Then T(n,k) is the number of such polygons with k simple sides. There is also a connection with A002464 (see that entry). - N. J. A. Sloane, Mar 08 2022
Definition requires "pairs" and for n=0 it is assumed that there is 1 way of seating 0 people around a table for the second time so that 0 pairs are maintained and 1 person forms only one pair with him/herself. Therefore T(0,0)=1, T(1,0)=0 and T(1,1)=1.
The weighted average of each row using k as weights converges to 2 for large n and appears to be given by (Sum_{k} k*T(n,k))/n! = 2/(n-1) + 2.

			Assuming the initial order was {1,2,3,4,5} (therefore 1 and 5 form a pair as the first and last persons are neighbors in the case of a round table) there are 5 sets of ways of seating them again so that 3 pairs are conserved: {1,2,3,5,4}, {2,3,4,1,5}, {3,4,5,2,1}, {4,5,1,3,2}, {5,1,2,4,3}. Since within each set we do not allow for circular symmetry (e.g., {1,2,3,5,4} and its rotation to form {2,3,5,4,1} are counted as one) nor reflection ({1,2,3,5,4} and {4,5,3,2,1} are also counted as one), the total number of ways is 5 and therefore T(5,3)=5.
Unfolded table with n individuals (rows) forming k pairs (columns):
    0    1    2    3    4    5    6    7
0   1
1   0    1
2   0    0    1
3   0    0    0    1
4   0    0    2    0    1
5   1    0    5    5    0    1
6   3   12   15   20    9    0   1
7  23   70  112   91   49   14   0   1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50; rows 0..17 from Witold Tatkiewicz)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Page 117)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 118, 119)
P. Poulet, Query 4750, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121. (Pages 120, 121)
Witold Tatkiewicz, link for java program.

Cf. A002816 (column k=0).
Row sums: A001710(n-1) = Sum_k T(n,k).
Cf. also A326390 (accounting for rotation and reflection symmetry), A326397 (disregards reflection symmetry but allows rotation), A326407 (disregards rotation symmetry but allows reflection).
See in addition A002464.

Java
```
See Links section
```

A326411 := proc(n,k)
    option remember;
    if k > n or k < 0 then
        0;
    elif k = n then
        1;
    elif k =0 then
        if n < 5 then
            0 ;
        elif n = 5 then
            1 ;
        elif n = 6 then
            3 ;
        elif n = 7 then
            23 ;
        else
            # Poulet eq (6) page 120, shifted n->n-2
            -(n^3-8*n^2+18*n-21)*procname(n-1,0)
            -4*(n^2-5*n)*procname(n-2,0)
            +2*(n^3-11*n^2+33*n-18)*procname(n-3,0)
            -(n^2-7*n+9)*procname(n-4,0)
            -(n^3-10*n^2+28*n-15)*procname(n-5,0) ;
            -%/(n^2-7*n+9) ;
        end if;
    elif n <= 3 then
        0;
    else
        # Poulet eq (3) page 119
        2*(n-k)*procname(n-1,k-1)/(n-1)+2*k*procname(n-1,k)/(n-1)
            +(k-2)*procname(n-2,k-2)/(n-2) - 2*(k-1)*procname(n-2,k-1)/(n-2) + k*procname(n-2,k)/(n-2) ;
        %*n/k ;
    end if;
end proc:
for n from 0 to 12 do
    for k from 0 to n do
        printf("%a ",A326411(n,k)) ;
    end do:
    printf("\n") ;
end do: # R. J. Mathar, Mar 17 2022

T[n_, k_] := T[n, k] = Which[k > n || k < 0, 0, k == n, 1, k == 0, Which[n<5, 0, n == 5, 1, n == 6, 3, n == 7, 23, True,
    pc = -(n^3 - 8*n^2 + 18*n - 21)*T[n-1, 0]
      - 4*(n^2 - 5*n)*T[n - 2, 0]
      + 2*(n^3 - 11*n^2 + 33*n - 18)*T[n-3, 0]
      - (n^2 - 7*n + 9)*T[n-4, 0]
      - (n^3 - 10*n^2 + 28*n - 15)*T[n-5, 0];
    -pc/(n^2 - 7*n + 9)], n <= 3, 0, True,
   pc = 2*(n-k)*T[n-1, k-1]/(n-1) + 2*k*T[n-1, k]/(n-1) +
     (k - 2)*T[n-2, k-2]/(n-2) -
     2*(k-1)*T[n-2, k-1]/(n-2) + k*T[n-2, k]/(n-2);
    pc*n/k];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 17 2023, after R. J. Mathar *)

Q(n,k)={k*subst(serlaplace(polcoef((1 - 2*x -x^2)/((1 + x)*(1 + (1 - y)*x + y*x^2)) + O(x^n), n-1)), y, k)}
row(n)={Vec(if(n<3, 1, (Q(n,y/(y-1))/2 + (-1)^n)*(y-1)^n), -n-1)} \\ Andrew Howroyd, Mar 01 2024

It appears that Poulet gives recurrences that generate the whole triangle. - N. J. A. Sloane, Mar 09 2022
T(n,n) = 1;
T(n,n-1) = 0 for n >= 1;
T(n,n-2) = n*(n-3)/2 for n >= 4 [Poulet];
T(n,n-3) = n*(n-4)*(2*n-7)/3 for n >= 4 [Poulet, corrected by N. J. A. Sloane, Mar 09 2022]
T(n,n-4) = (25/24)*n^4 + (23/12)*n^3 - (169/24)*n^2 + (85/12)*n - 3 for n > 5 (conjectured); [see Poulet]
T(n,n-5) = (26/15)*n^5 + (25/6)*n^4 - (83/6)*n^3 + (221/6)*n^2 - (299/10)*n + 13 for n > 5 (conjectured); [see Poulet]
T(n,n-6) = (707/240)*n^6 + (2037/240)*n^5 - (413/16)*n^4 + (2233/16)*n^3 - (2777/15)*n^2 + (3739/20)*n - 57 for n > 6 (conjectured). [See Poulet]

A382651 Number of king permutations on n elements without strict fixed points.

Original entry on oeis.org

1, 0, 0, 0, 2, 10, 68, 500, 4174, 38770, 397544, 4462476, 54452394, 717877882, 10170925492, 154139627692, 2488385952526, 42636054584106, 772802263942376, 14774515232543556, 297137552306148570, 6271261537872652418, 138596588342412866276, 3200953561821628327956, 77114526810424117688014

Offset: 0

Dan Li, Apr 02 2025

nonn

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

			a(4) = 2 corresponds to these two permutations: 2413, 3142.
a(5) = 10 corresponds to these 10 permutations of length 5: 24153, 25314, 31524, 35142, 35241, 41352, 42513, 42531, 52413, 53142.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See formula (7) at page 6.

Cf. A002464, A382644, A382645.

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

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

G.f.: (1 + t)*A(t)/(1 + t + t*A(t)) where A(t)=Sum_{n >= 0} n!*t^n*(1-t)^n/(1+t)^n is the g.f. for king permutations given by A002464.

a(n) ~ exp(-2) * n!. - Vaclav Kotesovec, Apr 04 2025

Previous Showing 11-20 of 66 results. Next

cp's OEIS Frontend

A382645 Number of king permutations on n elements not beginning with the smallest element and not ending with the largest element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A010028 Triangle read by rows: T(n,k) is one-half the number of permutations of length n with exactly n-k rising or falling successions, for n >= 1, 1 <= k <= n. T(1,1) = 1 by convention.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A001266 One-half the number of permutations of length n without rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A086853 Number of permutations of length n with exactly 2 rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs