login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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}. 6
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 (list; table; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 14:54 EDT 2020. Contains 337272 sequences. (Running on oeis4.)