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
More information about the SeqFan
mailing list