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

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

Offset

1,4

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

Links

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

Formula

T(n, k) = k!, if n >= A342474(k).

T(n, k) >= A371823(n, k).

T(n, k) >= A374411(n+1, k+1)/(k+1).

Example

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.

Prog

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

Crossrefs

Cf. A002464, A088532, A124188, A342474.

Cf. A371823, A373877, A374411.

Sequence in context: A113143 A181802 A371823 * A110971 A136788 A334622

Adjacent sequences: A373775 A373776 A373777 * A373779 A373780 A373781

Keyword

nonn,tabl,more,hard

Author

Thomas Scheuerle, Jun 18 2024

Extensions

a(40)-a(58) from Michel Marcus, Jun 20 2024

Status

approved