Minimizing the sum(permutation*inverse)

Leroy Quet qq-quet at mindspring.com
Mon May 15 17:34:29 CEST 2006


Regarding the sci.math thread:

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

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





More information about the SeqFan mailing list