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.

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,2

Comments

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!.

Links

Table of n, a(n) for n=1..58.

Formula

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.

Example

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.

Prog

(PARI) 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;

Crossrefs

Cf. A002464, A124188, A342474, A373778.

Sequence in context: A182411 A067804 A074911 * A174222 A071059 A256468

Adjacent sequences: A373874 A373875 A373876 * A373878 A373879 A373880

Keyword

nonn,tabl,hard

Author

Thomas Scheuerle, Jun 20 2024

Status

approved