|
| |
|
|
A373778
|
|
Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.
|
|
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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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).
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.
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
|
|
|
|
FORMULA
|
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
