A208951 Twice the maximum of the areas of the convex hulls of permutations {(1,p(1)), (2,p(2)), ..., (n,p(n))} of {1, 2, ..., n}, considered as points in the plane

0, 0, 3, 10, 20, 34, 52, 74

Offset

1,3

Comments

For n>=4, a(n) >= 2n^2 - 8n + 10 which is satisfied by any permutation with the following four points: {(1,2), (2,n), (n-1,1), (n,n-1)}. - Peter Kagey, Oct 30 2021

Links

Table of n, a(n) for n=1..8.

Formula

Conjecture: a(n) = 2n^2 - 8n + 10 for n >= 4. - Peter Kagey, Oct 30 2021

Example

For n=3, the two permutations (sets of points) {(1,1),(2,2),(3,3)} and {(1,3),(2,2),3,1)} have a convex hull with zero area, whereas the remaining four permutations {(1,1),(2,3),(3,2)}, {(1,2),(2,1),(3,3)}, {(1,2),(2,3),(3,1)}, and {(1,3),(2,1),(3,2)} each have a convex hull with area 3/2. So a(3)=3.

Mathematica

(* v. 8.0 *)<<ComputationalGeometry`; a={}; For[n=1, n<=8, n++, {Print[n]; p=Permutations[Range[n]]; an={}; For[k=1, k<=Length[p], k++, {pk=p[[k]]; spk = Table[{i, pk[[i]]}, {i, 1, n}]; AppendTo[an, ConvexHullArea[spk]] }]; AppendTo[a, Max[an]] }]; Print[2*a];

Crossrefs

Cf. A156831, A208952.

Sequence in context: A098645 A089693 A194116 * A299692 A246520 A338631

Adjacent sequences: A208948 A208949 A208950 * A208952 A208953 A208954

Keyword

nonn,more

Author

John W. Layman, Mar 03 2012

Status

approved