|
%I #26 Jun 22 2024 04:47:58
%S 1,2,2,6,4,6,24,22,2,24,120,118,2,14,120,720,718,218,8,90,720,5040,
%T 5038,3070,24,2,646,5040,40320,40318,32972,64,28,20,5242,40320,362880,
%U 362878,336196,3704,4,4,158,47622,362880,3628800,3628798,3533026,325752,16,16,16,1960,479306,3628800,39916800,39916798,39574122
%N 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.
%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 number of permutations with the greatest count among all P.
%C A373778 gives the greatest count found.
%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.
%C Column k gives the number of k-good permutations defined in A124188 for all rows where A373778(n, k) = k!.
%F T(n, 1) = n!.
%F T(n, n) = n!.
%F T(n, 2) = n! - 2, for n > 2.
%F T(n, 3) = A124188(n), for n > 4.
%F T(n, n-1) = A002464(n), for n > 3.
%e The triangle begins:
%e n| k: 1| 2| 3| 4| 5| 6| 7| 8
%e =====================================================
%e [1] 1
%e [2] 2, 2,
%e [3] 6, 4, 6,
%e [4] 24, 22, 2, 24
%e [5] 120, 118, 2, 14, 120
%e [6] 720, 718, 218, 8, 90, 720
%e [7] 5040, 5038, 3070, 24, 2, 646, 5040
%e [8] 40320, 40318, 32972, 64, 28, 20, 5242, 40320
%e ...
%e T(3, 2) = 4 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 is a winner.
%e {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] : 2 is a winner.
%e {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] : 2 is a winner.
%e {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] : 2 is a winner.
%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), 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;
%Y Cf. A002464, A124188, A342474, A373778.
%K nonn,tabl,hard
%O 1,2
%A _Thomas Scheuerle_, Jun 20 2024
|
