A110611 -id:A110611 - cp's OEIS frontend

A110610 Maximal 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, 25, 48, 82, 129, 191, 270, 368, 487, 629, 796, 990, 1213, 1467, 1754, 2076, 2435, 2833, 3272, 3754, 4281, 4855, 5478, 6152, 6879, 7661, 8500, 9398, 10357, 11379, 12466, 13620, 14843, 16137, 17504, 18946, 20465, 22063, 23742, 25504

Offset: 1

Emeric Deutsch, Jul 30 2005

			a(4)=25 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).

Michael De Vlieger, Table of n, a(n) for n = 1..10000
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 (4,-6,4,-1).

Cf. A016825, A110611.

Cf. also A064842, A087035, A185173.

a:=proc(n) if n=1 then 1 else (2*n^3+3*n^2-11*n+18)/6 fi end: seq(a(n),n=1..50);

Rest@ CoefficientList[Series[x (1 + x) (1 - x + 2 x^2 - x^3)/(1 - x)^4, {x, 0, 42}], x] (* Michael De Vlieger, Jan 29 2022 *)

a(1)=1; a(n)=(2n^3+3n^2-11n+18)/6 for n>=2.

G.f.: x*(1+x)*(1-x+2*x^2-x^3)/(1-x)^4. [Colin Barker, Jul 24 2012]

A306262 Difference between maximum and minimum sum of products of successive pairs in permutations of [n].

Original entry on oeis.org

0, 0, 0, 4, 11, 24, 42, 68, 101, 144, 196, 260, 335, 424, 526, 644, 777, 928, 1096, 1284, 1491, 1720, 1970, 2244, 2541, 2864, 3212, 3588, 3991, 4424, 4886, 5380, 5905, 6464, 7056, 7684, 8347, 9048, 9786, 10564, 11381, 12240, 13140, 14084, 15071, 16104, 17182

Offset: 0

Louis Rogliano, Feb 01 2019

nonn

			a(4) = 11 = 23 - 12. 1342 and 2431 have sums 23, 3214 and 4123 have sums 12.

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Cf. A026035, A101986.

a:= n-> `if`(n=0, 0, (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
    <0|0|0|0|1>, <-1|3|-2|-2|3>>^n. <<1, 0, 0, 4, 11>>)[1, 1]):
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 02 2019

a[n_] := Module[
  {min, max, perm, g, mperm},
  perm = Permutations[Range[n]];
  g[x_] := Sum[x[[i]] x[[i + 1]], {i, 1, Length[x] - 1}];
  mperm = Map[g, perm];
  min = Min[mperm];
  max = Max[mperm];
  Return[max - min]]
LinearRecurrence[{3,-2,-2,3,-1},{0,0,0,4,11,24},60] (* Harvey P. Dale, Aug 05 2020 *)

concat([0,0,0], Vec(x^3*(4 - x - x^2) / ((1 - x)^4*(1 + x)) + O(x^40))) \\ Colin Barker, Feb 05 2019

a(n+1) = a(n) + 1/4*((-1+(-1)^(n-1))^2+2*(n-1)*(n+4)) with a(n) = 0 for n <= 2.
From Alois P. Heinz, Feb 01 2019: (Start)
G.f.: -(x^2+x-4)*x^3/((x+1)*(x-1)^4).
a(n) = (2*n^3+6*n^2-26*n+15-3*(-1)^n)/12 for n > 0.
a(n) = A101986(n-1) - A026035(n) for n > 0. (End)
a(n) = 3*a(n-1)-2*a(n-2)-2*a(n-3)+3*a(n-4)-a(n-5). - Wesley Ivan Hurt, May 28 2021
a(n) = A110610(n+1) - A110611(n+1). - Talmon Silver, Sep 24 2025

More terms from Alois P. Heinz, Feb 01 2019

A358212 a(n) is the maximal possible sum of squares of the side lengths of an n^2-gon supported on a subset 1 <= x,y <= n of an integer lattice.

Original entry on oeis.org

4, 10, 36, 98, 232

Offset: 2

Giedrius Alkauskas, Nov 04 2022

Examples show that a(7) >= 462, a(8) >= 842, a(9) >= 1424, a(10) >= 2242.

Asymptotics: liminf a(n)/n^4 >= 8/27, limsup a(n)/n^4 <= 2/3.

Oliver Mantas Ališauskas, Grid connector, Web application for this problem.
Oliver Mantas Ališauskas, Giedrius Alkauskas, and Valdas Dičiūnas, Full Grid Lattice Polygons with Maximal Sum of Squares of Edge-Lengths, arXiv:2311.03011 [math.CO], 2023-2024.
S. Chow, A. Gafni, and P. Gafni, Connecting the dots: maximal polygons on a square grid, Math. Mag. 94 (2021), no. 2, 118-124.
G. L. Cohen and E. Tonkes, Dartboard arrangements, Elect. J. Combin., 8(2) (2001), #R4.

Cf. A209077, A110611, A064842, A226595, A226596.

a(5) from Giedrius Alkauskas, Oct 09 2023

a(6) from Giedrius Alkauskas, Nov 30 2023

cp's OEIS Frontend

A110610 Maximal 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}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A306262 Difference between maximum and minimum sum of products of successive pairs in permutations of [n].

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A358212 a(n) is the maximal possible sum of squares of the side lengths of an n^2-gon supported on a subset 1 <= x,y <= n of an integer lattice.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions