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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 5, 1, 1, 2, 6, 12, 6, 1, 1, 2, 6, 17, 21, 7, 1, 1, 2, 6, 22, 41, 28, 8, 1, 1, 2, 6, 24, 69, 73, 36, 9, 1, 1, 2, 6, 24, 94, 156, 113, 45, 10, 1, 1, 2, 6, 24, 109, 273, 291, 162, 55, 11, 1, 1, 2, 6, 24, 118, 408, 614, 477, 220, 66, 12, 1, 1, 2, 6, 24, 120, 526, 1094, 1127, 699, 286, 78, 13, 1

Offset: 1

Thomas Scheuerle, Jun 22 2024

The row sums agree for n = 1..8 and 10..11 with A088532(n), where n = 11 was the last known value of A088532. The process described in A371822 gives in row 9 the permutation {6,1,9,4,7,2,5,8,3} but the closest optimal permutation would have been: {6,2,9,4,7,1,5,8,3}.

			The triangle begins:
   n| k: 1| 2| 3|  4|  5|  6|  7| 8| 9
  ====================================
  [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, 17, 21,  7,  1
  [8]    1, 2, 6, 22, 41, 28,  8, 1
  [9]    1, 2, 6, 24, 69, 73, 36, 9, 1

Cf. A371822.

Cf. A088532, A342474, A373778.

T(n, k) <= A373778(n, k).

Conjecture: T(n, n-2) = ceiling(n*(n-1)/2), for n > 6. This is expected because this triangle does asymptotically approximate the factorial numbers from the left to the right and Pascal's triangle from right to the left.

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

A373877 Triangle read by rows: T(n, k) is the number of permutations of length n, which contain the maximum number of distinct patterns of length k.

Original entry on oeis.org

1, 2, 2, 6, 4, 6, 24, 22, 2, 24, 120, 118, 2, 14, 120, 720, 718, 218, 8, 90, 720, 5040, 5038, 3070, 24, 2, 646, 5040, 40320, 40318, 32972, 64, 28, 20, 5242, 40320, 362880, 362878, 336196, 3704, 4, 4, 158, 47622, 362880, 3628800, 3628798, 3533026, 325752, 16, 16, 16, 1960, 479306, 3628800, 39916800, 39916798, 39574122

Offset: 1

Thomas Scheuerle, Jun 20 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 number of permutations with the greatest count among all P.
A373778 gives the greatest count found.
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.
Column k gives the number of k-good permutations defined in A124188 for all rows where A373778(n, k) = k!.

			The triangle begins:
   n| k:     1|     2|     3|  4|   5|   6|    7|     8
  =====================================================
  [1]        1
  [2]        2,     2,
  [3]        6,     4,     6,
  [4]       24,    22,     2, 24
  [5]      120,   118,     2, 14, 120
  [6]      720,   718,   218,  8,  90, 720
  [7]     5040,  5038,  3070, 24,   2, 646, 5040
  [8]    40320, 40318, 32972, 64,  28,  20, 5242, 40320
  ...
T(3, 2) = 4 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 is a winner.
  {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] :  2 is a winner.
  {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] :  2 is a winner.
  {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] :  2 is a winner.
  {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, A124188, A342474, A373778.

row(n) = my(rowp = vector(n!, i, numtoperm(n, i)), v = vector(n), t = 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); ); if( v[j] < #Set(list), v[j] = #Set(list); t[j] = 1, if(v[j] == #Set(list), t[j] = t[j]+1)); ); ); t;

T(n, 1) = n!.
T(n, n) = n!.
T(n, 2) = n! - 2, for n > 2.
T(n, 3) = A124188(n), for n > 4.
T(n, n-1) = A002464(n), for n > 3.

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

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

A373877 Triangle read by rows: T(n, k) is the number of permutations of length n, which contain the maximum number of distinct patterns of length k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula