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

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, 28, 1, 24, 108, 214, 231, 162, 84, 36, 1, 32, 198, 472, 600, 484, 271, 120, 45, 1, 48, 360, 1043, 1564, 1443, 915, 428, 165, 55, 1, 64, 648, 2304, 4074, 4320, 3089, 1608, 642, 220, 66, 1, 96, 1188, 5136, 10618

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..71.

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

From Chai Wah Wu, Feb 24 2020: (Start)

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

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

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

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

(End)

Example

(Partially filled in) table starts (with n rows and k columns):
(Third column is A070735, fourth column is A070736)
   k    1   2     3     4     5     6     7     8     9    10    11    12     13     14     15
  --------------------------------------------------------------------------------------------
n  1|   1   1     1     1     1     1     1     1     1     1     1     1      1      1      1
   2|   3   4     6     8    12    16    24    32    48    64    96   128    192    256    384
   3|   6  10    18    33    60   108   198   360   648  1188  2145  3888   7083  12844  23328
   4|  10  20    44    96   214   472  1043  2304  5136 11328 24993 55296 122624 271040 599832
   5|  15  35    89   231   600  1564  4074 10618
   6|  21  56   162   484  1443  4320
   7|  28  84   271   915  3089
   8|  36 120   428  1608
   9|  45 165   642  2664
  10|  55 220   930  4208
  11|  66 286  1304
  12|  78 364  1781
  13|  91 455  2377
  14| 105 560  3111
  15| 120 680  4002
(Partially filled in) table of how many nonequivalent sets of permutations achieves the value of T(n,k)
   k    1    2     3     4     5     6     7     8     9    10    11    12    13     14     15
  --------------------------------------------------------------------------------------------
n  1|   1    1     1     1     1     1     1     1     1     1     1     1     1      1      1
   2|   1    1     1     1     1     1     1     1     1     1     1     1     1      1      1
   3|   1    1     1     1     1     2     1     2     2     2     1     3     1      1      3
   4|   1    1     2     4    11    10    10    81   791   533    24  1461  3634    192   2404
   5|   1    1     3    12    16   188   211  2685
   6|   1    1    10   110    16
   7|   1    1     6
   8|   1    1    16
   9|   1    1     4
  10|   1    1    12
  11|   1    1
  12|   1    1
  13|   1    1
  14|   1    1
  15|   1    1

Prog

(Python)
from itertools import permutations, combinations_with_replacement
def A260355(n, k): # compute T(n, k)
    if k == 1:
        return n*(n+1)//2
    ntuple, count = tuple(range(1, n+1)), n**(k+1)
    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()
        v = 0
        for i in range(n):
            v += (n-i)*t[i]
        if v < count:
            count = v
    return count

Crossrefs

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

Sequence in context: A207619 A209694 A286951 * A075419 A060922 A143790

Adjacent sequences: A260352 A260353 A260354 * A260356 A260357 A260358

Keyword

nonn,tabl,hard

Author

Chai Wah Wu, Jul 29 2015

Status

approved