Minimizing the sum(permutation*inverse)
franktaw at netscape.net
franktaw at netscape.net
Mon May 15 20:08:32 CEST 2006
These aren't finite sequences; just the first 9 terms of two infinite sequences. Permutations are of numbers, not digits.
The second one is A000330.
Franklin T. Adams-Watters
-----Original Message-----
From: zak seidov zakseidov at yahoo.com
Here's table of min and max for n=1...9 (first entry)
{1,1,1}
{2,5,5}
{3,11,14}
{4,20,30}
{5,35,55}
{6,57,91}
{7,85,140}
{8,120,204}
{9,165,285}
which gives two full fini seqs:
1, 5, 11, 20, 35, 57, 85, 120, 165,
1, 5, 14, 30, 55, 91, 140, 204, 285
Zak
--- Leroy Quet <qq-quet at mindspring.com> wrote:
> 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
>
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
___________________________________________________
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/734d311b/attachment-0001.htm>
More information about the SeqFan
mailing list