A373778 -id:A373778 - cp's OEIS frontend

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

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.

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

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

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