A002464 -id:A002464 - cp's OEIS frontend

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

1, 1, 2, 5, 18, 75, 410, 2729, 20906, 181499, 1763490, 18943701, 222822578, 2847624899, 39282739034, 581701775369, 9202313110506, 154873904848803, 2762800622799362, 52071171437696453, 1033855049655584786, 21567640717569135515

Offset: 0

Vaclav Kotesovec, Apr 19 2011

nonn

a(n) is also the number of ways to place n nonattacking pieces rook + semi-leaper (2,2) on an n X n chessboard.
Comments from Vaclav Kotesovec, Mar 05 2022: (Start)
The original submission had keyword hard because of the following running times (in 2012):
a(33) 39 hours
a(34) 78 hours
a(35) 147 hours
The conjectured recurrence would imply the asymptotic expansion for a(n)/n! ~
(1 + 3/n + 2/n^2 + 1/n^3 + 0/n^4 + 3/n^5 + 26/n^6 + 101/n^7 + 124/n^8 - 1409/n^9 - 13266/n^10)/e.
This exactly matches the formula from 2011. In addition, all coefficients are integers. It is highly probable that recurrence is correct.
(End)
There are good reasons to believe the conjecture is correct. (It has the expected form.)  The problem is one of counting Hamiltonian cycles in the complement of some simple graph. There is a method for counting these efficiently (although I have not implemented in code). Similar to A242522 / A229430. - Andrew Howroyd, Mar 06 2022
See also Manuel Kauers's comments below. Since the four new terms took weeks of computation, the keyword "hard" continues to be justified. - N. J. A. Sloane, Mar 06 2022
a(40)-a(300) were computed using an independent solution (dynamic programming, O(N^4) per term), and the conjectured recurrence was further confirmed to be correct up to n=300. Consequently, the keyword "hard" is removed. - Rintaro Matsuo, Oct 18 2022

Rintaro Matsuo, Table of n, a(n) for n = 0..300 (terms 0..35 from Vaclav Kotesovec, terms 36..39 from Christoph Koutschan, computed using a parallelization of Kotesovec's Mathematica program)
Robert Dougherty-Bliss, Experimental Methods in Number Theory and Combinatorics, Ph. D. Dissertation, Rutgers Univ. (2024). See p. 4.
Manuel Kauers, Comments on the Conjectured Recurrence for A189281.
Manuel Kauers and Christoph Koutschan, Guessing with Little Data, arXiv:2202.07966 [cs.SC], 2022.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 644.
Vaclav Kotesovec, Mathematica program for this sequence.
Rintaro Matsuo, O(n^4) code to calculate a(n)
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.

Cf. A000255, A002464, A055790, A110128.

Asymptotics: a(n)/n! ~ (1 + 3/n + 2/n^2)/e.
Conjectured recurrence of degree 11 and order 8: (262711*n + 1387742*n^2 - 824875*n^3 - 1855253*n^4 - 111530*n^5 + 680983*n^6 + 364242*n^7 + 84992*n^8 + 10332*n^9 + 640*n^10 + 16*n^11)*a(n) + (-1050844*n - 9705192*n^2 - 7414683*n^3 + 3536494*n^4 + 6459004*n^5 + 3326393*n^6 + 903534*n^7 + 144684*n^8 + 13756*n^9 + 720*n^10 + 16*n^11)*a(n+1) + (3492344 - 2212342*n - 8507169*n^2 - 11544227*n^3 - 12034116*n^4 - 8216995*n^5 - 3442049*n^6 - 890050*n^7 - 142300*n^8 - 13660*n^9 - 720*n^10 - 16*n^11)*a(n+2) + (19817984 + 45323852*n + 825228*n^2 - 57004661*n^3 - 57059306*n^4 - 28077270*n^5 - 8398637*n^6 - 1631510*n^7 - 207980*n^8 - 16828*n^9 - 784*n^10 - 16*n^11)*a(n+3) + (9586160 + 6680237*n - 13772613*n^2 - 27689586*n^3 - 22162455*n^4 - 9855085*n^5 - 2629562*n^6 - 427656*n^7 - 41332*n^8 - 2176*n^9 - 48*n^10)*a(n+4) + (22192864 + 44710768*n - 2924668*n^2 - 52385912*n^3 - 45161616*n^4 - 18784740*n^5 - 4549208*n^6 - 674256*n^7 - 60400*n^8 - 3008*n^9 - 64*n^10)*a(n+5) + (557152 - 2032472*n - 2937392*n^2 - 1594200*n^3 - 517688*n^4 - 122032*n^5 - 19856*n^6 - 1792*n^7 - 64*n^8)*a(n+6) + (3786960 + 7105324*n - 1191064*n^2 - 8059160*n^3 - 5938996*n^4 - 2073752*n^5 - 402736*n^6 - 44528*n^7 - 2624*n^8 - 64*n^9)*a(n+7) + (-598208 - 943004*n + 414196*n^2 + 1213772*n^3 + 728648*n^4 + 203584*n^5 + 29616*n^6 + 2176*n^7 + 64*n^8)*a(n+8) = 0. This recurrence correctly predicted the four new terms in the b-file. - Christoph Koutschan, Feb 19 2022
Comment from N. J. A. Sloane, Mar 12 2022: (Start)
The preceding conjectured recurrence is equivalent to the following, which has degree 3 and order 13, and was obtained by Doron Zeilberger and then reformatted by Manuel Kauers (it uses Mathematica syntax):
Conjecture: ((-1 + n)^2*n*a[n])/4 + (n*(-16 + 38*n + 11*n^2)*a[1 + n])/16 +
(3/2 + (139*n)/16 + (29*n^2)/8 + (3*n^3)/16)*a[2 + n] +
(-21/4 - (51*n)/4 - (79*n^2)/16 - (5*n^3)/8)*a[3 + n] +
(-15/2 - n/8 + (5*n^2)/4 + n^3/8)*a[4 + n] +
(603/4 + (307*n)/4 + (49*n^2)/4 + (11*n^3)/16)*a[5 + n] +
(-41 - (533*n)/16 - (49*n^2)/8 - (5*n^3)/16)*a[6 + n] +
(-911/2 - 161*n - (303*n^2)/16 - (3*n^3)/4)*a[7 + n] +
(-363 - (417*n)/4 - (37*n^2)/4 - n^3/4)*a[8 + n] +
(-993/4 - 53*n - (11*n^2)/4)*a[9 + n] + (-130 - (93*n)/4 - n^2)*a[10 + n] +
(-71/4 - 2*n)*a[11 + n] + (-10 - n)*a[12 + n] + a[13 + n] == 0.
(End)
From Mark van Hoeij, Jul 25 2012: (Start)
A compact way to write the order 13 recurrence is as follows:
Let b(n) = a(n+3) + a(n+2) + (n/2+2)*a(n+1) + (n-1)*a(n)/2
and c(n) = b(n+4) + (n/2+2)*b(n+2) - b(n+1)/2 + (1-n)*b(n)/2;
then c(n+6) - (n+11)*c(n+5) - (2*n+75/4)*c(n+4) + (3-n)*c(n+3)/4 - c(n+2)/2 - (7*n+22)*c(n+1)/4-n*c(n) = 0. (End)

A383040 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,1),(0,2),(1,0),(2,0)}).

Original entry on oeis.org

1, 1, 0, 0, 2, 12, 78, 568, 4674, 42944, 436314, 4860020, 58914870, 772330276, 10888803374, 164310553184, 2642525580218, 45124440536632, 815438318526482, 15547317496485932, 311912067538692126, 6568399090178800988, 144867849880285518694, 3339550150164041194232, 80315480372245746015970

Offset: 0

Dan Li, Apr 22 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, 53142.

Dan Li and Philip B. Zhang, Distributions of mesh patterns of short lengths on king permutations, arXiv:2411.18131 [math.CO], 2024. See Theorem 4.1 at page 13.

Cf. A002464, A382644, A382645, A382651.

G.f.: (1 + t)^2*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.

A002493 Number of ways to arrange n non-attacking kings on an n X n board, with 2 sides identified to form a cylinder, with 1 in each row and column.

Original entry on oeis.org

1, 0, 0, 0, 10, 60, 462, 3920, 36954, 382740, 4327510, 53088888, 702756210, 9988248956, 151751644590, 2454798429600, 42130249479562, 764681923900260, 14636063499474054, 294639009867223880

Offset: 1

N. J. A. Sloane

nonn

Number of directed Hamiltonian paths in the complement of C_n where C_n is the n-cycle graph. - Andrew Howroyd, Mar 15 2016

Number of ways of arranging n consecutive integers in a circle such that no pair of adjacent integers differ by 1, rotations are distinct. - Graham Holmes, Sep 03 2020

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

Vincenzo Librandi, Table of n, a(n) for n = 1..100
M. Abramson and W. O. J. Moser, Permutations without rising or falling w-sequences, Ann. Math. Stat., 38 (1967), 1245-1254.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Counting King Permutations on the Cylinder, arXiv:2001.02948 [math.CO], 2020.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 627-8.
A. J. Schwenk, Letter to N. J. A. Sloane, Mar 24 1980 (with enclosure and notes)

Cf. A002464, A002816, A006184.

Right diagonal of A338838.

b1:= proc(n, r) local gu, x; if r=0 then RETURN(0): fi: gu := (x*diff(x*(1+x)/(1-x),x))* (x*(1 + x)/(1 - x))^(r-1); gu := taylor(gu, x = 0, n +1); coeff(gu, x, n ) end: b:=proc(n) local r: if n=1 then 1 elif n=2 then 0 else add((-1)^(n-r)*r!*b1(n,r),r=0..n): fi: end: # Doron Zeilberger, Nov 14 2007

b[n_]:=(If[n>0, 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}], 0]); Table[If[n>2, b[n]-2*Sum[b[n-1-2k], {k, 0, Floor[n/2]}], If[n==1, 1, 0]], {n, 1, 25}] (* Vaclav Kotesovec after Vladeta Jovovic, Apr 06 2012 *)

The linear recurrence operator annihilating this sequence is (N is the shift operator Na(n):=a(n + 1)) is - 3*(43*n + 197)*(n - 2)*(n + 1)/( - 1222 + 753*n + 349*n^2) - 5*(n - 1)*(44*n^2 + 477*n + 1222)/( - 1222 + 753*n + 349*n^2)*N + 2*(n + 1)*(239*n^2 + 873*n - 1232)/( - 1222 + 753*n + 349*n^2)*N^2 + 4*(394 - 259*n + 215*n^2 + 55*n^3)/( - 1222 + 753*n + 349*n^2)*N^3 - ( - 7342 + 3699*n + 2718*n^2 + 349*n^3)/( - 1222 + 753*n + 349*n^2)*N^4 + N^5. - Doron Zeilberger, Nov 14 2007
a(n) = Sum((-1)^(n-k)*k!*A102413(n,k),k=1..n), n>2. - Vladeta Jovovic, Nov 23 2007
a(n) = b(n+1) - 2*Sum_{k=0..floor(n/2)} b(n-2*k) for n>1, where b(n)=A002464(n) if n>0 else b(0)=0. - Vladeta Jovovic, Nov 24 2007
Asymptotic: a(n) ~ n!/e^2*(1 - 2/n - 2/n^2 - 4/(3n^3) + 8/(3n^4) + 326/(15n^5) + 4834/(45n^6) + 154258/(315n^7) + 232564/(105n^8) + ...). - Vaclav Kotesovec, Apr 06 2012
a(n) = n! + Sum_{i=1..n-1} ((-1)^i * (n-i-1)! * n * Sum_{j=0..i-1} (2^(j+1) * C(i-1,j) * C(n-i,j+1))), for n>=5. - Andrew Woods, Jan 08 2015

A086854 Number of permutations of length n with exactly 3 rising or falling successions.

Original entry on oeis.org

0, 0, 0, 0, 2, 16, 120, 888, 7198, 64968, 650644, 7165200, 86059242, 1119549472, 15682257872, 235336043976, 3766695159030, 64052134910168, 1153211148654348, 21915344800505888, 438380075974889154, 9207290871553008240, 202585136417883766472, 4659950328485470292632

Offset: 0

N. J. A. Sloane, Aug 19 2003

nonn

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

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

Cf. A002464, A000130, A000349, A001267, A086852, A086853. 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-> coeff(S(n), t, 3):
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]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)

Coefficient of t^3 in S[n](t) defined in A002464.
Recurrence (for n>4): (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 11 2013
a(n) ~ 4/3*exp(-2) * n! = n! * 0.45231366335478... - Vaclav Kotesovec, Aug 11 2013

A127697 Number of permutations of {1,2,...,n} where adjacent elements differ in value by 3 or more.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 2, 32, 368, 3984, 44304, 521606, 6564318, 88422296, 1272704694, 19521035238, 318120059458, 5491779703870, 100150978723568, 1924351621839740, 38864316540425434, 823161467837784388

Offset: 0

Richard Forster (gbrl01(AT)yahoo.co.uk), Apr 11 2007, Apr 26 2007

Equivalently, number of permutations of {1,2,...,n} where elements that differ by 1 in value are neither in positions i and i+1 (adjacent), nor i and i+2.

			Valid permutations of {1,...,6} are 415263 and 362514.

Robert P. P. McKone, The permutations n=6 to n=10.

Cf. A002464 (stride >= 2), A179957 (stride >= 4), A179958 (stride >=5).

Clear[permCount]; permCount[s_, last_] := permCount[s, last] = Module[{n, j}, n = Length[s]; If[n == 0, 1, Total[Table[If[Abs[last - j] >= 3, permCount[DeleteCases[s, j], j], 0], {j, s}]]]]; Table[permCount[Range[n], -2], {n, 0, 12}] (* Robert P. P. McKone, Mar 01 2025 *)

Jul 01 2010: Zak Seidov corrected a(10) and a(11). R. H. Hardin then computed a(12) through a(18).
Corrected first term to 1 (was 0).
a(0), a(19)-a(20) from Alois P. Heinz, Oct 27 2014
a(21) from Alois P. Heinz, Feb 09 2025

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

A338526 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] without consecutive adjacent values.

Original entry on oeis.org

1, 1, 1, 1, 2, 0, 1, 3, 2, 0, 1, 4, 6, 4, 2, 1, 5, 12, 18, 20, 14, 1, 6, 20, 48, 90, 124, 90, 1, 7, 30, 100, 272, 582, 860, 646, 1, 8, 42, 180, 650, 1928, 4386, 6748, 5242, 1, 9, 56, 294, 1332, 5110, 15912, 37566, 59612, 47622, 1, 10, 72, 448, 2450, 11604, 46250, 148648, 360642, 586540, 479306

Offset: 0

Xiangyu Chen, Nov 07 2020

Also number of ways to arrange n non-attacking kings on an n X k board, with 0 or 1 in each row and 1 in each column. - Ron L.J. van den Burg, Aug 04 2024

			n\k  0    1    2    3    4    5    6    7    8
0    1
1    1    1
2    1    2    0
3    1    3    2    0
4    1    4    6    4    2
5    1    5    12   18   20   14
6    1    6    20   48   90   124  90
7    1    7    30   100  272  582  860  646
8    1    8    42   180  650  1928 4386 6748 5242

Diagonal is A002464.

T(2n,n) gives A375022.

isok(s, p) = {for (i=1, #s-1, if (abs(s[p[i+1]] - s[p[i]]) == 1, return (0));); return (1);}
T(n, k) = {my(nb = 0); forsubset([n, k], s, for(i=1, k!, if (isok(s, numtoperm(k, i)), nb++););); nb;} \\ Michel Marcus, Nov 17 2020

T(n,k) = (n! + Sum_{p=1..k-1} (-1)^p (n-p)! Sum_{r=1..p} 2^r binomial(k-p,r) binomial(p-1,r-1) )/(n-k)!. - Ron L.J. van den Burg, Aug 04 2024

O.g.f.: Sum_{n>=0} Sum_{k=0..n} T(n,k)*x^n*y^k = Sum_{i>=0} i!(x*y*(1-x*y)/(1+x*y))^i/(1-x)^(i+1). - Ron L.J. van den Burg, Aug 14 2024

A383107 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)}).

Original entry on oeis.org

1, 1, 0, 0, 2, 14, 88, 636, 5174, 47122, 475128, 5257976, 63381078, 826817350, 11607019144, 174484968604, 2796703640190, 47613279070594, 858080079253440, 16320196781972904, 326687694661023774, 6865553778933359142, 151139392725808178080, 3478151644016630307452, 83516524547918673461238

Offset: 0

Dan Li, Apr 22 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) = 14 solutions are these 14 permutations: 13524, 14253, 24135, 24153, 25314, 31425, 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 Theorem 4.2 at page 15.

Cf. A002464, A382644, A382645, A382651, A383040.

G.f.: (1/(1 + t) + t*(1 + t)/(1 + t + t*A(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.

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

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 11, 113, 1099, 11060, 118484, 1366134, 16970322, 226574211, 3240161105, 49453685911, 802790789101, 13815657556958, 251309386257874, 4818622686395380, 97145520138758844, 2054507019515346789, 45484006970415223287, 1052036480881734378541

Offset: 0

N. J. A. Sloane

nonn

(1/2) times number of permutations of 12...n such that exactly 4 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 A086855/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, 4)/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, 4]/2]; Table [a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 24 2014, after Alois P. Heinz *)

Coefficient of t^4 in S[n](t) defined in A002464, divided by 2.
Recurrence (for n>5): (n-5)*(n^8 - 41*n^7 + 730*n^6 - 7358*n^5 + 45799*n^4 - 179702*n^3 + 432498*n^2 - 581244*n + 332100)*a(n) = (n^10 - 45*n^9 + 895*n^8 - 10301*n^7 + 75340*n^6 - 361190*n^5 + 1124682*n^4 - 2150033*n^3 + 2147364*n^2 - 499899*n - 544266)*a(n-1) - (n^10 - 44*n^9 + 869*n^8 - 10112*n^7 + 76390*n^6 - 388742*n^5 + 1336932*n^4 - 3028095*n^3 + 4237931*n^2 - 3198426*n + 917988)*a(n-2) - (n^10 - 43*n^9 + 823*n^8 - 9195*n^7 + 66108*n^6 - 318138*n^5 + 1033118*n^4 - 2224673*n^3 + 3023402*n^2 - 2325285*n + 761190)*a(n-3) + (n^8 - 33*n^7 + 471*n^6 - 3783*n^5 + 18594*n^4 - 56865*n^3 + 104723*n^2 - 104847*n + 42783)*(n-2)^2*a(n-4). - Vaclav Kotesovec, Aug 11 2013
a(n) ~ n!*exp(-2)/3. - Vaclav Kotesovec, Aug 11 2013

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

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Aug 19 2003

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

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

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.

Columns give A001266 (see also A002464), A000130, A000349, A001267, A001268.
Triangle in A001100 divided by 2 (except for T(1, 0)). A010028 transposed.
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, k)/2):
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]/2]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 11}] // Flatten (* Jean-François Alcover, Jan 14 2014, translated from Alois P. Heinz's Maple code *)

Previous Showing 21-30 of 66 results. Next

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A383040 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,1),(0,2),(1,0),(2,0)}).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A002493 Number of ways to arrange n non-attacking kings on an n X n board, with 2 sides identified to form a cylinder, with 1 in each row and column.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A086854 Number of permutations of length n with exactly 3 rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A127697 Number of permutations of {1,2,...,n} where adjacent elements differ in value by 3 or more.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A338526 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] without consecutive adjacent values.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A383107 Number of king permutations on n elements avoiding the mesh pattern (12, {(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)}).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs