# [seqfan] Re: Differences of permutations of 1..2^k

Max Alekseyev maxale at gmail.com
Sat Mar 6 16:30:36 CET 2010

The (n-1)-st difference of permutation (q_1, q_2, ..., q_n) is

\sum_{i=0}^{n-1} (-1)^i \binom{n-1}{i} q_{i+1}

It is easy to check that if n=p^k for prime p then

(-1)^i \binom{n-1}{i} == 1 (mod p)

Therefore, the (n-1)-st difference of permutation (q_1, q_2, ..., q_n)
equals simply the sum of its elements modulo p, which is 0 (unless p=2
and k=1).

Regards,
Max

On Sat, Mar 6, 2010 at 9:29 AM, Maximilian Hasler
<maximilian.hasler at gmail.com> wrote:
> If n>2 is a power of a prime p,
> then the (n-1)-st difference of any permutation of 1..n is a multiple of p.
> At least it seems so...
>
> Maximilian
>
> On Sat, Mar 6, 2010 at 3:12 PM, Ron Hardin <rhhardin at att.net> wrote:
>>
>> For n>1, the 2^n-1st difference of any permuation of 1..2^n is even.
>>
>> At least I think so.
>>
>>  ---rhhardin at mindspring.com
>> rhhardin at att.net (either)
>>
>>
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>