A002464 -id:A002464 - cp's OEIS frontend

A373778 Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 5, 1, 1, 2, 6, 12, 6, 1, 1, 2, 6, 19, 21, 7, 1, 1, 2, 6, 23, 41, 28, 8, 1, 1, 2, 6, 24, 71, 76, 36, 9, 1, 1, 2, 6, 24, 94, 156, 114, 45, 10, 1, 1, 2, 6, 24, 112, 273, 291, 162, 55, 11, 1, 1, 2, 6, 24, 119, 408, 614, 477, 220, 66, 12, 1

Offset: 1

Thomas Scheuerle, Jun 18 2024

Let P be a permutation of the set {1, 2, ..., n}. We consider all subsequences from P of length k and count the different permutation patterns obtained. T(n, k) is the greatest count among all P.
For n > 3 and k = n, the number of permutations that realize the maximum count is given by A002464(n).
Row sums are <= 2^(n-1) (after a result from Herb Wilf).
Row sums are >= A088532(n). This means that a pattern of length k, which realizes the maximum possible downset size, does not always contain only those patterns in its downset, which do again maximize their downset sizes themselves. A088532(n) can be interpreted as the maximum size of a downset in the pattern posets of [n].
Statistical results show that the maximum number of patterns occurs among the permutations that, when represented as a 2D pointset, maximize the average distance between neighboring points.

			The triangle begins:
   n| k: 1| 2| 3|  4|  5|  6| 7
  =============================
  [1]    1
  [2]    1, 1
  [3]    1, 2, 1
  [4]    1, 2, 4,  1
  [5]    1, 2, 6,  5,  1
  [6]    1, 2, 6, 12,  6, 1
  [7]    1, 2, 6, 19, 21, 7, 1
  ...
T(3, 2) = 2 because we have:
  permutations  subsequences      patterns           number of patterns
  {1,2,3} : {1,2},{1,3},{2,3} : [1,2],[1,2],[1,2] :  1.
  {1,3,2} : {1,3},{1,2},{3,2} : [1,2],[1,2],[2,1] :  2.
  {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] :  2.
  {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] :  2.
  {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] :  2.
  {3,2,1} : {3,2},{3,1},{2,1} : [2,1],[2,1],[2,1] :  1.
A pattern is a set of indices that may sort a selected subsequence into an increasing sequence.

Cf. A002464, A088532, A124188, A342474.

Cf. A371823, A373877, A374411.

row(n) = my(rowp = vector(n!, i, numtoperm(n, i)), v = vector(n)); for (j=1, n, for (i=1, #rowp, my(r = rowp[i], list = List()); forsubset([n,j], s, my(ss = Vec(s)); vp = vector(j, ik, r[ss[ik]]); vs = Vec(vecsort(vp,,1)); listput(list, vs);); v[j] = max(v[j], #Set(list)););); v; \\ Michel Marcus, Jun 20 2024

T(n, k) = k!, if n >= A342474(k).
T(n, k) >= A371823(n, k).
T(n, k) >= A374411(n+1, k+1)/(k+1).

a(41)-a(59) from Michel Marcus, Jun 20 2024

a(60)-a(78) from Jinyuan Wang, Jul 23 2025

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

Original entry on oeis.org

1, 1, 0, 0, 2, 14, 88, 632, 5152, 46976, 474056, 5249064, 63298724, 825977620, 11597642568, 174371083288, 2795208188972, 47592162832412, 857760977798888, 16315057829100968, 326599827759568812, 6863964030561807340, 151109048051281532488, 3477542225297684400056, 83503678542689445133052

Offset: 0

Dan Li, Apr 25 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.4 at page 17.

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

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

A010030 Irregular triangle read by rows: T(n,k) (n >= 1, 0 <= k <= [n/2]) = number of permutations of 1..n with [n/2]-k runs of consecutive pairs up and down (divided by 2).

Original entry on oeis.org

1, 1, 0, 3, 0, 3, 8, 1, 25, 28, 7, 17, 155, 143, 45, 259, 1005, 933, 323, 131, 2770, 7488, 7150, 2621, 3177, 27978, 64164, 62310, 23811, 1281, 51433, 294602, 619986, 607445, 239653

Offset: 1

N. J. A. Sloane

			Triangle begins:
1,
1, 0,
3, 0,
3, 8, 1,
25, 28, 7,
17, 155, 143, 45,
259, 1005, 933, 323,
131, 2770, 7488, 7150, 2621,
3177, 27978, 64164, 62310, 23811,
1281, 51433, 294602, 619986, 607445, 239653,
...

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

Cf. A002464, A001266, A000239, A000544, A001282.

G.f. for number of permutations of 1..n by number of runs of consecutive pairs up and down is Sum(n!*(((1-y)*(2*x^2-x^3)-x)/((1-y)*x^2-1))^n,n = 0 .. infinity), cf. A010029. - Vladeta Jovovic, Nov 23 2007

More terms from Vladeta Jovovic, Nov 23 2007

Entry revised by N. J. A. Sloane, Apr 14 2014

A086855 Number of permutations of length n with exactly 4 rising or falling successions.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 22, 226, 2198, 22120, 236968, 2732268, 33940644, 453148422, 6480322210, 98907371822, 1605581578202, 27631315113916, 502618772515748, 9637245372790760, 194291040277517688, 4109014039030693578, 90968013940830446574, 2104072961763468757082

Offset: 0

N. J. A. Sloane, Aug 19 2003

nonn

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.

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, A086853. A diagonal of A001100.

Twice A001268.

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)):
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]]; Table [a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 13 2014, after Alois P. Heinz *)

Coefficient of t^4 in S[n](t) defined in A002464.

a(n) ~ 2/3*exp(-2) * n!. - Vaclav Kotesovec, Aug 14 2013

A095818 Number of permutations of 1..n with no five elements in correct or reverse order.

Original entry on oeis.org

1, 1, 2, 6, 24, 118, 714, 5012, 40164, 361872, 3621366, 39854930, 478427452, 6221137644, 87112280208, 1306869108686, 20912175669082, 355537064658852, 6400095163337508, 121608318630457872, 2432271817858395382, 51079520016325649394, 1123782363517325646716

Offset: 0

Jonas Wallgren, Jun 08 2004

nonn

For no k do either of the subsequences k(k+1)(k+2)(k+3)(k+4) or (k+4)(k+3)(k+2)(k+1)k occur in any permutation.

Andrew Howroyd, Table of n, a(n) for n = 0..200
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, A095816, A095817.

seq(n)={my(m=5); 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 = 5. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

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

a(0)=1 prepended and terms a(20) and beyond from Andrew Howroyd, Aug 31 2018

A129535 Number of permutations of 1,...,n with at least one pair of adjacent consecutive entries (i.e., of the form k(k+1) or (k+1)k), n >= 2.

Original entry on oeis.org

2, 6, 22, 106, 630, 4394, 35078, 315258, 3149494, 34620010, 415222566, 5395737242, 75516784982, 1132471183626, 18115911832390, 307919970965434, 5541804787940598, 105282261866132138, 2105441434230129254, 44210612765653749210, 972564180363044943766

Offset: 2

Emeric Deutsch, May 05 2007

nonn

Column 1 of A129534. a(n) = n! - A002464(n).

Column k=2 of A322481.

			a(4)=22 because 3142 and 2413 are the only permutations of 1,2,3,4 with no adjacent consecutive entries.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.

Alois P. Heinz, Table of n, a(n) for n = 2..450

Cf. A002464, A129534, A322481.

E:=x->sum(n!*x^n,n=0..35): G:=E(x)-E(x*(1-x)/(1+x)): Gser:=series(G,x=0,30): seq(coeff(Gser,x,n),n=2..23);

G.f.: E(x) - E(x(1-x)/(1+x)), where E(x) = Sum_{n>=0} n!*x^n.
a(n) = n! - Sum_{k=1..n} ((-1)^(n-k)*k!*Sum_{i=0..n-k} binomial(i+k-1, k-1)*binomial(k, n-i-k)), n > 0. - Vladimir Kruchinin, Sep 08 2010
D-finite with recurrence a(n) +2*(-n+1)*a(n-1) +(n^2-2*n-2)*a(n-2) +(-n^2+7*n-14)*a(n-3) -(n-3)*(n-5)*a(n-4) +(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Jul 26 2022

A383407 Number of king permutations on n elements avoiding the mesh pattern (12, {(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, 475124, 5257936, 63380706, 826813990, 11606987816, 174484661916, 2796700455414, 47613243806514, 858079661762692, 16320191491499712, 326687622910353650, 6865552738575268502, 151139376627154723752, 3478151378775992816412, 83516519907235226131286

Offset: 0

Dan Li, Apr 26 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.5 at page 18.

Cf. A002464, A382644, A382645, A382651, A383040, A383107, A383312, A383406.

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

A383857 Number of permutations of [n] such that precisely one rising or falling succession occurs, but without either n(n-1) or (n-1)n.

Original entry on oeis.org

0, 0, 2, 8, 34, 196, 1366, 10928, 98330, 983036, 10811134, 129714184, 1686103522, 23603603540, 354033474374, 5664286296416, 96289603698346, 1733166940314028, 32929480177913230, 658578501071986616, 13829959293448920434, 304255691156335505924

Offset: 1

Wolfdieter Lang, May 19 2025

See A086852 or 2*A000130 for the counting including the successions n(n-1) and (n-1)n. See also the k = 1 columns of the triangles A001100 and 2*A086856.

For the number of permutations of length n without rising or falling successions see A002464(n).

			a(3) = 2*1 from the permutations 213 and the reverted 312.
a(4) = 2*4 from 1324, 1423, 2314, 3124 and the reverted 4231, 3241, 4132, 4213.
a(5) = 2*17 from the permutations corresponding to A086852(5) = 2*20, without 13542, 24513, 25413, and the reverted 24531, 31542, 31452.

Cf. A000130, A001100, A002464, A086852, A086856.

a(n) = A002464(n+1) - (n-1) * A002464(n).

A072148 Number of invertible (-1,0,1) n X n matrices having (Tij = -Tji; i

Original entry on oeis.org

2, 14, 92, 796, 7672, 83944

Offset: 1

Wouter Meeussen, Aug 25 2003

The matrix powers T^k reach identity I for k a divisor of 12. All T^k are invertible (-1,0,1)-matrices with determinant +/-1. The matrix |Tij| is symmetric. The matrices T are "pseudo-anti-symmetric" (that is Tij=-Tji except for the main diagonal, or, equivalently, the sum of an anti-symmetric and a diagonal matrix). Their eigenvalues belong to {-1, -I, I, 1, -(-1)^(1/3), (-1)^(1/3), -(-1)^(2/3), (-1)^(2/3)}.

			{{1,-1,0,0,0},{1,0,0,0,0},{0,0,0,-1,0},{0,0,1,1,0},{0,0,0,0,-1}}
qualifies since its powers are:
{{0,-1,0,0,0},{1,-1,0,0,0},{0,0,-1,-1,0},{0,0,1,0,0},{0,0,0,0,1}},
{{-1,0,0,0,0},{0,-1,0,0,0},{0,0,-1,0,0},{0,0,0,-1,0},{0,0,0,0,-1}},
{{-1,1,0,0,0},{-1,0,0,0,0},{0,0,0,1,0},{0,0,-1,-1,0},{0,0,0,0,1}},
{{0,1,0,0,0},{-1,1,0,0,0},{0,0,1,1,0},{0,0,-1,0,0},{0,0,0,0,-1}},
{{1,0,0,0,0},{0,1,0,0,0},{0,0,1,0,0},{0,0,0,1,0},{0,0,0,0,1}}.

Cf. A081959 A002464 A020063 A033169 A090410 A066052.

triamatsig[li_List] := Block[{len=Sqrt[8Length[li]+1]/2-1/2}, If[IntegerQ[len], (Part[li, # ]&/@ Table[If[j>i, j(j-1)/2+i, i(i-1)/2+j], {i, len}, {j, len}])Table[If[j>i, -1, 1], {i, len}, {j, len}], li]]; n=4; it=triamatsig/@(-1+IntegerDigits[Range[0, -1+3^(n(n+1)/2)], 3, n(n+1)/2]); result4=Cases[it, (q_?MatrixQ)/; Det[q]=!=0 && And@@ Table[Union[Flatten[{MatrixPower[q, k], {-1, 0, 1}}]]==={-1, 0, 1}, {k, 25}]]

a(6) from Wouter Meeussen, Nov 15 2005

A095817 Number of permutations of 1..n with no four elements in correct or reverse order.

Original entry on oeis.org

1, 1, 2, 6, 22, 114, 692, 4884, 39318, 355490, 3567292, 39345804, 473148014, 6161310442, 86376341412, 1297099489668, 20772929663254, 353415786538434, 6365693021157116, 121016486728717740, 2421505946364174606, 50873034832373299370, 1119617627206173146308

Offset: 0

Jonas Wallgren, Jun 08 2004

nonn

For no k do either of the subsequences k(k+1)(k+2)(k+3) or (k+3)(k+2)(k+1)k occur in any permutation.

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, A095816, A095818.

seq(n)={my(m=4); 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 = 4. - Ivana Jovovic ( ivana121(AT)EUnet.yu ), Nov 11 2007

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

a(0)=1 prepended and terms a(20) and beyond from Andrew Howroyd, Aug 31 2018

Previous Showing 41-50 of 66 results. Next

cp's OEIS Frontend

A373778 Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A010030 Irregular triangle read by rows: T(n,k) (n >= 1, 0 <= k <= [n/2]) = number of permutations of 1..n with [n/2]-k runs of consecutive pairs up and down (divided by 2).

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A086855 Number of permutations of length n with exactly 4 rising or falling successions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A095818 Number of permutations of 1..n with no five elements in correct or reverse order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A129535 Number of permutations of 1,...,n with at least one pair of adjacent consecutive entries (i.e., of the form k(k+1) or (k+1)k), n >= 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A383857 Number of permutations of [n] such that precisely one rising or falling succession occurs, but without either n(n-1) or (n-1)n.

Views

Author

Keywords

Comments

Examples