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