A070736 -id:A070736 - cp's OEIS frontend

A070735 Let r, s, t be three permutations of the set { 1, 2, 3, ..., n }; a(n) = minimal value of Sum_{i=1..n} r(i)s(i)t(i).

1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 9587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773, 77373, 86759, 96972, 108063, 120080, 133067, 147082, 162174, 178395, 195806, 214461, 234421, 255739

Offset: 1

Michael Reid (mreid(AT)math.umass.edu), May 15 2002

Martin Fuller, Table of n, a(n) for n = 1..204
Martin Fuller, Python program for A070735/A070736

Cf. A000292 (for two permutations), A070736 (for four).

Cf. A072368 (three subsets of {1..3n})

{1, 6}~Join~Table[Min[Map[Total,Map[#[[1]]*#[[2]]*#[[3]] &, Subsets[Permutations[Range[n]], {3}]]]] , {n, 3, 5}] (* Robert Price, Apr 08 2019 *)
(* OR, if allowed to replicate small permutations to account for n=1,2 *)
Table[ Min[Map[Total,Map[#[[1]]*#[[2]]*#[[3]] &,Subsets[If[n > 2, Permutations[Range[n]],Flatten[Table[Permutations[Range[n]], 3], 1]], {3}]]]] , {n, 1, 5}] (* Robert Price, Apr 09 2019 *)

a(n) = {ret = 0; nb = n!; for (a=1, nb, pa = numtoperm(n, a); for (b=1, nb, pb = numtoperm(n, b); for (c=1, nb, pc = numtoperm(n, c); sp = sum(i=1, n, pa[i]*pb[i]*pc[i]); if (! ret, ret = sp, ret = min(ret, sp));););); return (ret);} \\ Michel Marcus, Jun 10 2013

Python
```
# See Martin Fuller link, Aug 06 2023
```

a(16)-a(19) from Hiroaki Yamanouchi, Aug 21 2015

a(20) onwards from Martin Fuller, Aug 06 2023

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

Original entry on oeis.org

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

Chai Wah Wu, Jul 29 2015

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

			(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

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.

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

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

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)

A260356 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..5} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Original entry on oeis.org

1, 12, 60, 214, 600, 1443, 3089

Offset: 1

Chai Wah Wu, Jul 28 2015

See Wu link for sets of permutations that achieve the value of a(n).

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

Cf. A000292 (two permutations), A070735 (three permutations), A070736 (four permutations), A260357 (six permutations), A260358 (seven permutations), A260359 (eight permutations), A260355.

A260357 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..6} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Original entry on oeis.org

1, 16, 108, 472, 1564, 4320

Offset: 1

Chai Wah Wu, Jul 28 2015

See arXiv link for sets of permutations that achieve the value of a(n).

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

Cf. A000292 (two permutations), A070735 (three permutations), A070736 (four permutations), A260356 (five permutations), A260358 (seven permutations), A260359 (eight permutations), A260355.

A260358 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..7} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Original entry on oeis.org

1, 24, 198, 1043, 4074

Offset: 1

Chai Wah Wu, Jul 28 2015

See arXiv link for sets of permutations that achieve the value of a(n).

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

Cf. A000292 (two permutations), A070735 (three permutations), A070736 (four permutations), A260356 (five permutations), A260357 (six permutations), A260359 (eight permutations), A260355.

A260359 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..8} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Original entry on oeis.org

1, 32, 360, 2304, 10618

Offset: 1

Chai Wah Wu, Jul 28 2015

See arXiv link for sets of permutations that achieve the value of a(n).

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

Cf. A000292 (two permutations), A070735 (three permutations), A070736 (four permutations), A260356 (five permutations), A260357 (six permutations), A260358 (seven permutations), A260355.

cp's OEIS Frontend

A070735 Let r, s, t be three permutations of the set { 1, 2, 3, ..., n }; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A260356 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..5} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A260357 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..6} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A260358 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..7} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A260359 a(n) is the minimal value of Sum_{i=1..n} Product_{j=1..8} r_j(i), where each r_j is a permutation of {1,2,...,n}.

Views

Author

Keywords

Comments

Links

Crossrefs

A070735 Let r, s, t be three permutations of the set { 1, 2, 3, ..., n }; a(n) = minimal value of Sum_{i=1..n} r(i)s(i)t(i).