A110611 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}.
1, 4, 11, 21, 37, 58, 87, 123, 169, 224, 291, 369, 461, 566, 687, 823, 977, 1148, 1339, 1549, 1781, 2034, 2311, 2611, 2937, 3288, 3667, 4073, 4509, 4974, 5471, 5999, 6561, 7156, 7787, 8453, 9157, 9898, 10679, 11499, 12361, 13264, 14211, 15201, 16237
Offset: 1
Examples
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).
Links
- Vincenzo Librandi, Table of n, a(n) for n = 1..1000
- Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, The Fifty-Seventh William Lowell Putnam Competition, Amer. Math. Monthly, 104, 1997, 744-754, Problem B-3.
- Vasile Mihai and Michael Woltermann, Problem 10725: The Smoothest and Roughest Permutations, Amer. Math. Monthly, 108 (March 2001), pp. 272-273.
- Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).
Programs
-
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
-
Maple
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);
-
Mathematica
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 *)
Formula
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.
G.f.: x*(1+x+x^2-2*x^3+x^4)/((1-x)^4*(1+x)). [Colin Barker, May 10 2012]
a(n) = (2*n^3+6*n^2+10*n-9-3*(-1)^n)/12. - Luce ETIENNE, Jul 26 2014