login
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
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!.
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
KEYWORD
nonn,tabl,hard
AUTHOR
Thomas Scheuerle, Jun 20 2024
STATUS
approved