Distinct Permutation-based Sums

Max relf at unn.ac.ru
Sat Dec 13 02:16:27 CET 2003


Leroy Quet wrote:

>Consider the permutations of {1,2,3,...,n}.
>Let [b(k)] be any one such permutation.
>
>
>If we have an integer sequence {a(k)}, we can take the sum, for the 
>particular permutation b,
>
>
> sum{k=1 to n}  a(k)*b(k).
>
>  
>
If all such sums are distinct for different permutations, we say that 
sequence {a(k)} distinguishes the permutations of order n.

I know a programming contest problem asking to find such sequence for 
n=5 with minimum value of
A=sum{k=1 to n} a(k).
And the answer is { 0, 2, 5, 21, 91 } with A=119.

Similar sequence for n=6 is likely to be { 0, 1, 6, 32, 172, 950 } with 
A=1161 (but I haven't checked it up).

Another variation is to minimize
max { a(k) }
For n=5 it gives sequence { 0, 1, 8, 38, 87 }.

>But, as I am guessing, 
>
>there is a specific infinite positive integer sequence {a(k)}, where
>
>a(1) = 1, 
>
>  
>
a(1)=0 looks more natural for me.

>and for all m's >= 2,
>
>a(m) is the MINIMUM integer > a(m-1) such that:
>
>for each permutation of {1,2,3,...,m},
>
>   sum{k=1 to m}  a(k)*b(k)
>
>is DISTINCT among those sums based on all m! permutations of 1 to m, for 
>every fixed m.
>
>  
>
Yeah, it deserves to be in OEIS.

Regards,
Max






More information about the SeqFan mailing list