login
Table T(n,k) read by antidiagonals. T(n,k) is the maximum value of Product_{i=1..n} Sum_{j=1..k} r_j[i] where each r_j is a permutation of {1..n}.
2

%I #37 May 26 2020 15:26:47

%S 1,2,2,6,9,3,24,64,20,4,120,625,216,36,5,720,7776,3136,512,56,6,5040,

%T 117649,59049,10000,1000,81,7,40320,2097152,1331000,248832,24336,1728,

%U 110,8,362880,43046721,35831808,7529536,759375,50625,2744,144,9,3628800,1000000000,1097199376,268435456,28652616,1889568,93636,4096,182,10

%N Table T(n,k) read by antidiagonals. T(n,k) is the maximum value of Product_{i=1..n} Sum_{j=1..k} r_j[i] where each r_j is a permutation of {1..n}.

%C A dual sequence to A260355. See arXiv link for sets of permutations that achieve the value of T(n,k). The minimum value of Product_{i=1..n} Sum_{j=1..k} r_j[i] is equal to n!*k^n.

%H Chai Wah Wu, <a href="/A331988/b331988.txt">Table of n, a(n) for n = 1..70</a>

%H Chai Wah Wu, <a href="http://arxiv.org/abs/1508.02934">Permutations r_j such that ∑i∏j r_j(i) is maximized or minimized</a>, arXiv:1508.02934 [math.CO], 2015-2020.

%H Chai Wah Wu, <a href="https://arxiv.org/abs/2002.10514">On rearrangement inequalities for multiple sequences</a>, arXiv:2002.10514 [math.CO], 2020.

%F T(n,n) = (n*(n+1)/2)^n = A061718(n).

%F T(n,k) <= (k(n+1)/2)^n.

%F T(1,k) = k = A000027(k).

%F T(n,1) = n! = A000142(n).

%F T(2,2m) = 9m^2 = A016766(m).

%F T(2,2m+1) = (3m+1)*(3m+2) = A001504(m).

%F T(n,2) = (n+1)^n = A000169(n+1).

%F T(3,k) = 8k^3 = A016743(k) for k > 1.

%F If n divides k then T(n,k) = (k*(n+1)/2)^n.

%F If k is even then T(n,k) = (k*(n+1)/2)^n.

%F If n is odd and k >= n-1 then T(n,k) = (k*(n+1)/2)^n.

%F If n is even and k is odd such that k >= n-1, then T(n,k) = ((k^2*(n+1)^2-1)/4)^(n/2).

%e T(n,k)

%e k 1 2 3 4 5 6 7 8 9 10 11 12

%e ---------------------------------------------------------------------------------

%e n 1| 1 2 3 4 5 6 7 8 9 10 11 12

%e 2| 2 9 20 36 56 81 110 144 182 225 272 324

%e 3| 6 64 216 512 1000 1728 2744 4096 5832 8000 10648 13824

%e 4| 24 625 3136 10000 24336 50625 93636 160000 256036 390625 571536 810000

%o (Python)

%o from itertools import permutations, combinations_with_replacement

%o def A331988(n,k): # compute T(n,k)

%o if k == 1:

%o count = 1

%o for i in range(1,n):

%o count *= i+1

%o return count

%o ntuple, count = tuple(range(1,n+1)), 0

%o for s in combinations_with_replacement(permutations(ntuple,n),k-2):

%o t = list(ntuple)

%o for d in s:

%o for i in range(n):

%o t[i] += d[i]

%o t.sort()

%o w = 1

%o for i in range(n):

%o w *= (n-i)+t[i]

%o if w > count:

%o count = w

%o return count

%Y Cf. A000027, A000142, A000169, A001504, A016743, A016766, A061711, A061718, A260355.

%K nonn,tabl

%O 1,2

%A _Chai Wah Wu_, Feb 23 2020