Minimizing the sum(permutation*inverse)

[franktaw at netscape.net]

As noted in the posting(s) by Rob Johnson in that thread, the resulting sequence is the tetrahedral numbers A000292, plus 1 when n = 2 or 3 (mod 4):
 
1, 5, 11, 20, 35, 57, 85, 120, 165, 221, 287, 364, 455, 561, 681, 816, 969, 1141, 1331, 1540, 1771, 2025, 2301, 2600, 2925, 3277, 3655, 4060, 4495, 4961, 5457, 5984, 6545, 7141, 7771, 8436, 9139, 9881, 10661, 11480, 12341, 13245, 14191, 15180, 16215, 17297, 18425, 19600, 20825, 22101

I'll submit this sequence.
 
Franklin T. Adams-Watters
 
-----Original Message-----
From: Leroy Quet <qq-quet at mindspring.com>
To: seqfan at ext.jussieu.fr
Sent: Mon, 15 May 06 09:34:29 -0600
Subject: Minimizing the sum(permutation*inverse)


Regarding the sci.math thread:

http://groups.google.com/group/sci.math/browse_thread/thread/6cf265b0d0e2f157

Let {b(k)} be a permutation of {1,2,3,...,n}. 
Let {c(k)} be the inverse-permutation of {b(k)}. 
(ie. b(c(j)) =j, for every j.) 

What is the minimum possible sum:
sum{k=1 to n}  b(k) * c(k)  ? 

For example, if b is: 
[1,2,3], 
[2,1,3], 
[3,2,1], 
each give a sum of 14 (since each of these permutations is its own 
inverse). 

But 
[2,3,1], 
[3,1,2], 
(which are inverses of each other) 
both give a sum of 11.

I get (possibly erroneously) that the sequences of minimum sums begins:
1, 5, 11, 20, 35,...

Could someone please calculate/submit this sequence (unless it is already 
in the EIS, of course).

thanks,
Leroy Quet
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060515/4f124bc4/attachment-0001.htm>