A070735 - OEIS

%I #30 Aug 08 2023 10:05:47

%S 1,6,18,44,89,162,271,428,642,930,1304,1781,2377,3111,4002,5073,6344,

%T 7842,9587,11610,13933,16591,19612,23028,26871,31177,35976,41314,

%U 47221,53736,60907,68773,77373,86759,96972,108063,120080,133067,147082,162174,178395,195806,214461,234421,255739

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

%H Martin Fuller, <a href="/A070735/b070735.txt">Table of n, a(n) for n = 1..204</a>

%H Martin Fuller, <a href="/A070735/a070735.txt">Python program for A070735/A070736</a>

%t {1, 6}~Join~Table[Min[Map[Total,Map[#[[1]]*#[[2]]*#[[3]] &, Subsets[Permutations[Range[n]], {3}]]]] , {n, 3, 5}] (* _Robert Price_, Apr 08 2019 *)

%t (* OR, if allowed to replicate small permutations to account for n=1,2 *)

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

%o (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

%o (Python) # See Martin Fuller link, Aug 06 2023

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

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

%K nice,nonn,hard

%O 1,2

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

%E a(16)-a(19) from _Hiroaki Yamanouchi_, Aug 21 2015

%E a(20) onwards from _Martin Fuller_, Aug 06 2023