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.

%I A373778 #74 Jul 24 2025 10:34:09
%S A373778 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,
%T A373778 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,
%U A373778 112,273,291,162,55,11,1,1,2,6,24,119,408,614,477,220,66,12,1
%N A373778 Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.
%C A373778 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.
%C A373778 For n > 3 and k = n, the number of permutations that realize the maximum count is given by A002464(n).
%C A373778 Row sums are <= 2^(n-1) (after a result from Herb Wilf).
%C A373778 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].
%C A373778 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.
%F A373778 T(n, k) = k!, if n >= A342474(k).
%F A373778 T(n, k) >= A371823(n, k).
%F A373778 T(n, k) >= A374411(n+1, k+1)/(k+1).
%e A373778 The triangle begins:
%e A373778    n| k: 1| 2| 3|  4|  5|  6| 7
%e A373778   =============================
%e A373778   [1]    1
%e A373778   [2]    1, 1
%e A373778   [3]    1, 2, 1
%e A373778   [4]    1, 2, 4,  1
%e A373778   [5]    1, 2, 6,  5,  1
%e A373778   [6]    1, 2, 6, 12,  6, 1
%e A373778   [7]    1, 2, 6, 19, 21, 7, 1
%e A373778   ...
%e A373778 T(3, 2) = 2 because we have:
%e A373778   permutations  subsequences      patterns           number of patterns
%e A373778   {1,2,3} : {1,2},{1,3},{2,3} : [1,2],[1,2],[1,2] :  1.
%e A373778   {1,3,2} : {1,3},{1,2},{3,2} : [1,2],[1,2],[2,1] :  2.
%e A373778   {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] :  2.
%e A373778   {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] :  2.
%e A373778   {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] :  2.
%e A373778   {3,2,1} : {3,2},{3,1},{2,1} : [2,1],[2,1],[2,1] :  1.
%e A373778 A pattern is a set of indices that may sort a selected subsequence into an increasing sequence.
%o A373778 (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
%Y A373778 Cf. A002464, A088532, A124188, A342474.
%Y A373778 Cf. A371823, A373877, A374411.
%K A373778 nonn,hard,tabl
%O A373778 1,5
%A A373778 _Thomas Scheuerle_, Jun 18 2024
%E A373778 a(41)-a(59) from _Michel Marcus_, Jun 20 2024
%E A373778 a(60)-a(78) from _Jinyuan Wang_, Jul 23 2025