|
%I #26 Mar 27 2024 08:59:15
%S 1,4,11,21,37,58,87,123,169,224,291,369,461,566,687,823,977,1148,1339,
%T 1549,1781,2034,2311,2611,2937,3288,3667,4073,4509,4974,5471,5999,
%U 6561,7156,7787,8453,9157,9898,10679,11499,12361,13264,14211,15201,16237
%N Minimal value of sum(p(i)p(i+1),i=1..n), where p(n+1)=p(1), as p ranges over all permutations of {1,2,...,n}.
%H Vincenzo Librandi, <a href="/A110611/b110611.txt">Table of n, a(n) for n = 1..1000</a>
%H Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, <a href="http://www.jstor.org/stable/2975240">The Fifty-Seventh William Lowell Putnam Competition</a>, Amer. Math. Monthly, 104, 1997, 744-754, Problem B-3.
%H Vasile Mihai and Michael Woltermann, <a href="http://www.jstor.org/stable/2695399">Problem 10725: The Smoothest and Roughest Permutations</a>, Amer. Math. Monthly, 108 (March 2001), pp. 272-273.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-2,3,-1).
%F a(n) = (n^3+3*n^2+5*n-6)/6 if n is even; a(n)=(n^3+3*n^2+5*n-3)/6 if n is odd.
%F G.f.: x*(1+x+x^2-2*x^3+x^4)/((1-x)^4*(1+x)). [_Colin Barker_, May 10 2012]
%F a(n) = (2*n^3+6*n^2+10*n-9-3*(-1)^n)/12. - _Luce ETIENNE_, Jul 26 2014
%e a(4)=21 because the values of the sum for the permutations of {1,2,3,4} are 21 (8 times), 24 (8 times) and 25 (8 times).
%p a:=proc(n) if n mod 2 = 0 then (n^3+3*n^2+5*n-6)/6 else (n^3+3*n^2+5*n-3)/6 fi end: seq(a(n),n=1..52);
%t CoefficientList[Series[(1+x+x^2-2*x^3+x^4)/((1-x)^4*(1+x)),{x,0,50}],x] (* _Vincenzo Librandi_, May 11 2012 *)
%o (Magma) I:=[1, 4, 11, 21, 37]; [n le 5 select I[n] else 3*Self(n-1)-2*Self(n-2)-2*Self(n-3)+3*Self(n-4)-Self(n-5): n in [1..50]]; // _Vincenzo Librandi_, May 11 2012
%Y Cf. A064842, A110610.
%K nonn,easy
%O 1,2
%A _Emeric Deutsch_, Jul 30 2005
|
