A367185 Largest cost for a permutation problem.

0, 2, 7, 17, 35, 62, 100, 152, 219, 303, 406, 530, 678, 851, 1051, 1280, 1540, 1834, 2163, 2529, 2934, 3380, 3869, 4403, 4985, 5616, 6298, 7033, 7823, 8670, 9576, 10544, 11575, 12671, 13834, 15066, 16369, 17745, 19196, 20724, 22332, 24021, 25793, 27650, 29594, 31627

Offset

1,2

Comments

The problem is to maximize Sum_{i=1..n} i p(i) - Max_{j=1..n} j p(j) where p is a permutation of {1,...,n}.

The terms up to n = 100 were computed via integer linear programming.

Links

Rob Pratt, Table of n, a(n) for n = 1..100

CodeForces, Another Permutation Problem

Mathematics Stack Exchange, Maximise ... with p permutation of size n.

MathOverflow, Maximizing a sum minus its maximal summand

Example

For n = 4, the best permutation is [1, 4, 3, 2], with a(4) = (1*1+2*4+3*3+4*2) - max(1*1,2*4,3*3,4*2) = 26 - 9 = 17.

Crossrefs

Sequence in context: A321123 A145066 A014148 * A070070 A318054 A033937

Adjacent sequences: A367182 A367183 A367184 * A367186 A367187 A367188

Keyword

nonn

Author

Rob Pratt, Nov 10 2023

Status

approved