|
%I #61 Jun 22 2024 04:47:49
%S 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,
%T 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
%N Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.
%C 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 For n > 3 and k = n, the number of permutations that realize the maximum count is given by A002464(n).
%C Row sums are <= 2^(n-1) (after a result from Herb Wilf).
%C Conjecture: Row sums give the maximum size of a downset in the pattern posets of [n]. If this conjecture is false, it would mean that a pattern of length k, which realizes the maximum possible downset size, does not always contain a pattern with length k - 1, only those patterns in its downset, which do again maximize their downset sizes themselves.
%C 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 T(n, k) = k!, if n >= A342474(k).
%e The triangle begins:
%e n| k: 1| 2| 3| 4| 5| 6| 7
%e =============================
%e [1] 1
%e [2] 1, 1
%e [3] 1, 2, 1
%e [4] 1, 2, 4, 1
%e [5] 1, 2, 6, 5, 1
%e [6] 1, 2, 6, 12, 6, 1
%e [7] 1, 2, 6, 19, 21, 7, 1
%e ...
%e T(3, 2) = 2 because we have:
%e permutations subsequences patterns number of patterns
%e {1,2,3} : {1,2},{1,3},{2,3} : [1,2],[1,2],[1,2] : 1.
%e {1,3,2} : {1,3},{1,2},{3,2} : [1,2],[1,2],[2,1] : 2.
%e {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] : 2.
%e {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] : 2.
%e {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] : 2.
%e {3,2,1} : {3,2},{3,1},{2,1} : [2,1],[2,1],[2,1] : 1.
%e A pattern is a set of indices that may sort a selected subsequence into an increasing sequence.
%o (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 Cf. A002464, A124188, A342474, A373877.
%K nonn,tabl,more,hard
%O 1,4
%A _Thomas Scheuerle_, Jun 18 2024
%E a(40)-a(58) from _Michel Marcus_, Jun 20 2024
|
