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

[Ron Hardin]

Good deal, I'll add that as a comment.  I think I can get the corresponding term of the first in a day, and submit.


%I A000004
%S A000004 0,1,11,5,63,23,355,269,1903,387,9281,1587,44457,94475
%N A000004 Number of distinct even values of the n-1th difference of permutations of 1..n
%K A000004 nonn
%O A000004 2,3


%I A000005
%S A000005 2,2,0,6,58,22,0,272,1882,386,9116,1586,44424,94474,0
%N A000005 Number of distinct odd values of the n-1th difference of permutations of 1..n
%K A000005 nonn
%O A000005 2,1


 rhhardin at mindspring.com
rhhardin at att.net (either)



----- Original Message ----
From: Max Alekseyev <maxale at gmail.com>
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Sent: Sat, March 6, 2010 10:30:36 AM
Subject: [seqfan] Re: Differences of permutations of 1..2^k

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/
>


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/