A070735 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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