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,2

Links

Martin Fuller, Table of n, a(n) for n = 1..204

Martin Fuller, Python program for A070735/A070736

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

Prog

(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

Crossrefs

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

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

Sequence in context: A009957 A344992 A011929 * A136028 A083719 A182706

Adjacent sequences: A070732 A070733 A070734 * A070736 A070737 A070738

Keyword

nice,nonn,hard

Author

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

Extensions

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

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

Status

approved