|
| |
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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!.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, 1) = n!.
T(n, n) = n!.
T(n, 2) = n! - 2, for n > 2.
|
|
|
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
