A331988 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}.

1, 2, 2, 6, 9, 3, 24, 64, 20, 4, 120, 625, 216, 36, 5, 720, 7776, 3136, 512, 56, 6, 5040, 117649, 59049, 10000, 1000, 81, 7, 40320, 2097152, 1331000, 248832, 24336, 1728, 110, 8, 362880, 43046721, 35831808, 7529536, 759375, 50625, 2744, 144, 9, 3628800, 1000000000, 1097199376, 268435456, 28652616, 1889568, 93636, 4096, 182, 10

Offset

1,2

Comments

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.

Links

Chai Wah Wu, Table of n, a(n) for n = 1..70

Chai Wah Wu, Permutations r_j such that ∑i∏j r_j(i) is maximized or minimized, arXiv:1508.02934 [math.CO], 2015-2020.

Chai Wah Wu, On rearrangement inequalities for multiple sequences, arXiv:2002.10514 [math.CO], 2020.

Formula

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

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

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

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

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

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

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

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

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

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

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

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).

Example

T(n,k)
   k    1    2     3      4      5      6      7      8      9     10     11     12
  ---------------------------------------------------------------------------------
n  1|   1    2     3      4      5      6      7      8      9     10     11     12
   2|   2    9    20     36     56     81    110    144    182    225    272    324
   3|   6   64   216    512   1000   1728   2744   4096   5832   8000  10648  13824
   4|  24  625  3136  10000  24336  50625  93636 160000 256036 390625 571536 810000

Prog

(Python)
from itertools import permutations, combinations_with_replacement
def A331988(n, k): # compute T(n, k)
    if k == 1:
        count = 1
        for i in range(1, n):
            count *= i+1
        return count
    ntuple, count = tuple(range(1, n+1)), 0
    for s in combinations_with_replacement(permutations(ntuple, n), k-2):
        t = list(ntuple)
        for d in s:
            for i in range(n):
                t[i] += d[i]
        t.sort()
        w = 1
        for i in range(n):
            w *= (n-i)+t[i]
        if w > count:
            count = w
    return count

Crossrefs

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

Sequence in context: A277510 A169800 A094485 * A242978 A345308 A231137

Adjacent sequences: A331985 A331986 A331987 * A331989 A331990 A331991

Keyword

nonn,tabl

Author

Chai Wah Wu, Feb 23 2020

Status

approved