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

%I #42 May 26 2020 15:27:21

%S 1,1,3,1,4,6,1,6,10,10,1,8,18,20,15,1,12,33,44,35,21,1,16,60,96,89,56,

%T 28,1,24,108,214,231,162,84,36,1,32,198,472,600,484,271,120,45,1,48,

%U 360,1043,1564,1443,915,428,165,55,1,64,648,2304,4074,4320,3089,1608,642,220,66,1,96,1188,5136,10618

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

%C T(1,k) = 1. T(2,k) = A029744(k+2). T(n,1) = n(n+1)/2 (= A000217(n)). See arXiv link for sets of permutations that achieve the value of T(n,k).

%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 From _Chai Wah Wu_, Feb 24 2020: (Start)

%F T(n,k) >= n*(n!)^(k/n).

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

%F T(n,n) = (n+1)! - n! = A001563(n).

%F T(n,2) = n*(n+1)*(n+2)/6 = A000292(n).

%F (End)

%e (Partially filled in) table starts (with n rows and k columns):

%e (Third column is A070735, fourth column is A070736)

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

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

%e n 1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 2| 3 4 6 8 12 16 24 32 48 64 96 128 192 256 384

%e 3| 6 10 18 33 60 108 198 360 648 1188 2145 3888 7083 12844 23328

%e 4| 10 20 44 96 214 472 1043 2304 5136 11328 24993 55296 122624 271040 599832

%e 5| 15 35 89 231 600 1564 4074 10618

%e 6| 21 56 162 484 1443 4320

%e 7| 28 84 271 915 3089

%e 8| 36 120 428 1608

%e 9| 45 165 642 2664

%e 10| 55 220 930 4208

%e 11| 66 286 1304

%e 12| 78 364 1781

%e 13| 91 455 2377

%e 14| 105 560 3111

%e 15| 120 680 4002

%e (Partially filled in) table of how many nonequivalent sets of permutations achieves the value of T(n,k)

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

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

%e n 1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 2| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

%e 3| 1 1 1 1 1 2 1 2 2 2 1 3 1 1 3

%e 4| 1 1 2 4 11 10 10 81 791 533 24 1461 3634 192 2404

%e 5| 1 1 3 12 16 188 211 2685

%e 6| 1 1 10 110 16

%e 7| 1 1 6

%e 8| 1 1 16

%e 9| 1 1 4

%e 10| 1 1 12

%e 11| 1 1

%e 12| 1 1

%e 13| 1 1

%e 14| 1 1

%e 15| 1 1

%o (Python)

%o from itertools import permutations, combinations_with_replacement

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

%o if k == 1:

%o return n*(n+1)//2

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

%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 v = 0

%o for i in range(n):

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

%o if v < count:

%o count = v

%o return count

%Y Cf. A001563, A029744, A000217, A000292 (T(n,2)), A070735 (T(n,3)), A070736 (T(n,4)).

%K nonn,tabl,hard

%O 1,3

%A _Chai Wah Wu_, Jul 29 2015