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

Author

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

Keywords

• nice
• nonn
• hard

Links

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

Crossrefs

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

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

Programs

Mathematica

{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 *)

PARI

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

Extensions

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

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