Minimizing the sum(permutation*inverse)

[Ray Chandler]

My brute force calculations agree with Leroy and Zak and extend one additional term:

1, 5, 11, 20, 35, 57, 85, 120, 165, 221

Note that this sequence appears to have the following relationships:

1) a(n) = n(n+1)(2n+1)/6

2) a(n) = A0024411(n) - A000292(n-1)

3) a(n) = A000292(n-1) + A000292(n)

Ray Chandler

-----Original Message-----
From: zak seidov [mailto:zakseidov at yahoo.com] 
Sent: Monday, May 15, 2006 2:40 PM
To: seqfan at ext.jussieu.fr
Subject: Re: Minimizing the sum(permutation*inverse)

Yes, of course,
it'd be numbers not digits -
as i suggested 

Zak

--- franktaw at netscape.net wrote:

> 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
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around http://mail.yahoo.com