# Distinct Permutation-based Sums

Max relf at unn.ac.ru
Sat Dec 13 02:53:14 CET 2003

```Leroy Quet wrote:

>>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 }.
>>
>>
>
>
>Interesting. But to clarify, the sequence I am asking about is fixed
>for all values up to a(m-1), *then* a(m) is determined.
>
>
>
>
That's not true. a(m) may not exist. And it does not exist even for
small examples.
Let a(1)=0, a(2)=1, a(3)=3. This sequence distinguishes all permutations
of order 3.
But at the same time there is an equality

a(3)*1 + a(1)*2 + a(4)*3 + a(2)*4 = a(2)*1 + a(3)*2 + a(4)*3 + a(1)*4

that holds for ANY a(4).
Hence,  a(4) can NOT be defined such that a(1), a(2), a(3),a(4)
distinguishes all permutations of order 4.

Regards,
Max

```