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

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