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

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

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

Example

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

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

Prog

(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

Crossrefs

Cf. A064842, A110610.

Sequence in context: A301239 A301161 A301173 * A008004 A212254 A301064

Adjacent sequences: A110608 A110609 A110610 * A110612 A110613 A110614

Keyword

nonn,easy

Author

Emeric Deutsch, Jul 30 2005

Status

approved