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

Author

Rob Pratt, Nov 10 2023

Keywords

• nonn

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.

Examples

			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.
		

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