Max/Min Sums From Permutations

[David Wilson]

Let p be a permutation of the integers (1, 2, ..., n) (n >= 1).

Define f as cyclic sum of products of adjacent pairs,

    f(p) = p(1)*(p2) + p(2)*p(3) + ... + p(n-1)*p(n) + p(n)*p(1).

Modulo my programming abilities...

Up to n = 10, f(p) is minimized by the permutation p with

    p(i) = 
        i,            if 1 <= i <= [(n+1)/2], i odd
        n+1-i         if 1 <= i <= [(n+1)/2], i even
        n+1-p(n+1-i)  if [(n+1)/2] < i <= n.

Assuming this holds beyond n = 10, the minimal value would be

    fmin(n) =
        (n^3 + 3n^2 + 5n - 6)/6    if i even
        (n^3 + 3n^2 + 5n - 3)/6    if i odd

The sequence for fmin starts

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 17318

Similarly, up to n = 10, f(p) is maximized by

    p(i) =
        2i-1          if 1 <= i <= [(n+1)/2]
        p(n+1-i)+1    if [(n+1)/2] < i <= n.

And extrapolating beyond n = 10 gives

    fmax(n)
        1                            if n = 1
        (2n^3 + 3n^2 - 11n + 18)/6,  if n >= 2.

The sequence for fmax starts

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 27351 29285 31308

Assuming these sequences are correct, I don't find either in the OEIS.

----- Original Message ----- 
From: "Joshua Zucker" <joshua.zucker at gmail.com>
To: <ham>; <seqfan at ext.jussieu.fr>
Cc: "Leroy Quet" <qq-quet at mindspring.com>
Sent: Monday, January 31, 2005 12:18 AM
Subject: Re: Max/Min Sums From Permutations


>I very much like Emeric's suggestion that we look at the circular
> version of this sequence!
> 
> I haven't been able to get very much farther, though, and there's not
> as simple of an obvious conjecture about the sequence; I'll have to
> keep thinking.  Has anyone got anything better than the brute-force
> computer search yet?