A371823 -id:A371823 - 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

A371822 Triangle read by rows. Row n is the lexicographically earliest permutation of [n] that can be obtained from row n-1 by inserting the element n and optional cyclic shifting to maximize the pattern density.

Original entry on oeis.org

1, 1, 2, 3, 1, 2, 3, 1, 4, 2, 2, 5, 3, 1, 4, 2, 5, 3, 6, 1, 4, 3, 6, 1, 4, 7, 2, 5, 2, 5, 8, 3, 6, 1, 4, 7, 6, 1, 9, 4, 7, 2, 5, 8, 3, 7, 2, 10, 5, 8, 3, 6, 1, 9, 4, 7, 2, 10, 5, 8, 3, 11, 6, 1, 9, 4, 8, 3, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5, 13, 8, 3, 11, 6, 1, 14, 9, 4, 12, 7, 2, 10, 5, 13, 8, 3

Offset: 1

Thomas Scheuerle, Jun 22 2024

The first 13 rows include shortest k-superpatterns for k up to 5. These k-superpatterns are also optimal superpatterns. Optimal means the overall pattern density including patterns of all length is maximal among all permutations of [n]. How many more shortest superpatterns will be given by this sequence? The next will be expected in row 17.
Row n is a k-superpattern if row n of A371823 starts with 1!, 2!, ..., k!. If n also coincides with A342474(k), then row n is a shortest possible k-superpattern.
At time of sequence publication, all known rows agree up to cyclic shift with rows from A194832. This could indicate that A194832 will at least almost optimize the pattern density for permutations on the circle.
The above observations are accompanied by strong statistical arguments: because (1+sqrt(5))/2 has the simplest continued fraction expansion of any irrational number it will optimize asymptotically the pattern density in the permutations induced by it.

			The first 10 rows:
  1
  1,  2
  3,  1,  2
  3,  1,  4,  2
  2,  5,  3,  1,  4
  2,  5,  3,  6,  1,  4
  3,  6,  1,  4,  7,  2,  5
  2,  5,  8,  3,  6,  1,  4,  7
  6,  1,  9,  4,  7,  2,  5,  8,  3
  7,  2, 10,  5,  8,  3,  6,  1,  9,  4

Wikipedia, Superpattern.

A371823 lists the number of different patterns of length k in row n.
Cf. A194832 (same rows cyclically shifted?).
Cf. A342474, A373778.

Edited by Peter Munn, Jul 09 2024

A374411 Triangle T(n, k) read by rows: Maximum number of linear patterns of length k in a circular permutation of length n taken from row n in A194832.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 2, 6, 4, 1, 2, 6, 16, 5, 1, 2, 6, 20, 25, 6, 1, 2, 6, 24, 60, 36, 7, 1, 2, 6, 24, 85, 126, 49, 8, 1, 2, 6, 24, 100, 222, 196, 64, 9, 1, 2, 6, 24, 115, 390, 511, 288, 81, 10, 1, 2, 6, 24, 120, 558, 1085, 912, 405, 100, 11, 1, 2, 6, 24, 120, 654, 1911, 2328, 1458, 550, 121, 12

Offset: 1

Thomas Scheuerle, Jul 08 2024

Pattern counting considers only one revolution otherwise every sufficiently long circular permutation, with enough revolutions allowed, contains every pattern.

Each column k is divisible by k, because as we count linear patterns inside a circular permutation, we may obtain all circular shifts of the subset which represents a particular pattern.

			The triangle begins:
   n| k: 1| 2| 3|  4|   5|   6|   7|  8|  9
  =========================================
  [1]    1
  [2]    1, 2
  [3]    1, 2, 3
  [4]    1, 2, 6,  4
  [5]    1, 2, 6, 16,   5
  [6]    1, 2, 6, 20,  25,   6
  [7]    1, 2, 6, 24,  60,  36,   7
  [8]    1, 2, 6, 24,  85, 126,  49,  8
  [9]    1, 2, 6, 24, 100, 222, 196, 64, 9
.
Row 5 of A194832 is [3, 1, 4, 2, 5].
T(5, 4) = 16 because we will find these 16 distinct patterns of length 4:
   [3, 1, 4, 2] [1, 4, 2, 3] [4, 2, 3, 1] [2, 3, 1, 4]
 These are rotations of the ordering [1, 4, 2, 3].
   [1, 4, 2, 5] [4, 2, 5, 1] [2, 5, 1, 4] [5, 1, 4, 2]
 These are rotations of the ordering [1, 3, 2, 4].
   [2, 5, 3, 1] [5, 3, 1, 2] [3, 1, 2, 5] [1, 2, 5, 3]
 These are rotations of the ordering [1, 2, 4, 3].
   [5, 3, 1, 4] [3, 1, 4, 5] [1, 4, 5, 3] [4, 5, 3, 1]
 These are rotations of the ordering [1, 3, 4, 2].

Cf. A194832, A371823, A373778.

T(n, k+1)/(k+1) <= A371823(n-1, k) <= A373778(n-1, k).

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

A371822 Triangle read by rows. Row n is the lexicographically earliest permutation of [n] that can be obtained from row n-1 by inserting the element n and optional cyclic shifting to maximize the pattern density.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A374411 Triangle T(n, k) read by rows: Maximum number of linear patterns of length k in a circular permutation of length n taken from row n in A194832.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula