Permutations problem?

Interesting problem. My first observation is that all numbers of the form 4k+1 or 4k+2 are discarded by parity check:

* the sum of any permutation Σ a_n is congruent with N(N+1)/2 mod 2,

* the sum of 1 through N is congruent with N(N+1)/2 mod 2

=> the sum of |a_n-n| is even.

Therefore, it can't be a permutation of 0 through N if N(N+1)/2 is odd, which happens for N=4k+1 or N=4k+2, k any nonnegative integer.

I assume that all other N's allow such solutions, but the proof has to be constructive. I haven't found any general pattern in solutions obtained for 0, 3, 4, 7, 8, 11 yet, maybe someone else can continue from here.

Edit: To MathMan TG,

the proof is actually simple, using congruences:

* for any integer x, |x| == x (mod 2) ... this is because sign change preserves parity

* thus for each n, |a_n - n| == a_n - n (mod 2)

* Σ |a_n - n| == (Σ a_n) - (Σ n) (mod 2)

* a_n is a permutation of (0, 1, 2, 3, ..., n) => it has exactly the same sum as just n

* therefore Σ |a_n - n| == 0 (mod 2).

ADD:

The O E I S comes through again: https://oeis.org/A075866

(as it usually does).

Alas, no formulas or proofs, but a reference:

"H. A. Shah Ali, Problem 10964, Amer. Math. Monthly, 109 (2002), 759."

ADD 2:

OK - I get it now.

Thanks for the clarificaition, Vasek.

"Sum of differences is always even, sum of numbers can be odd,

and in those cases the differences cannot be the same the as the numbers,

and therefore, since no difference can be greater than N,

there is a repeat somewhere in the list of differences!"

Very nice.

ORIGINAL ANSWER:

Experimental results confirm Vasek's conclusion:

N ... number of such permutations

2 ... none

3 ... 4/4!

4 ... 4/5!

5 ... none/6!

6 ... none/7!

7 ... 32/8!

8 ... 96/9!

9 ... none/10!

10 ... none/11!

11 ... 992/12!

12 ... 2464/13!

13 ... none/14!

14 ... none/15!

15 ... 50512/16!

16 ... 144144/17!

They come in complementary pairs.

For every such permutation, (a0, a1, a2, ... , aN)

there is a 'twin', which is (N-aN, ..., N-a2, N-a1, N-a0).

N=3 ... 4/24

1,3,2,0 Dn=1:2:0:3 [ paired with last one ]

2,1,3,0 Dn=2:0:1:3 [ paired with 3rd one ]

3,0,2,1 Dn=3:1:0:2

3,1,0,2 Dn=3:0:2:1

N=4 ... 4/120

2,4,1,3,0 Dn=2:3:1:0:4 [ paired with 3rd one ]

3,1,4,2,0 Dn=3:0:2:1:4 [ paired with 4th one ]

4,1,3,0,2 Dn=4:0:1:3:2

4,2,0,3,1 Dn=4:1:2:0:3

For example, some of the "near misses" for N=5 are:

0,3,5,2,4,1 Dn=0:2:3:1:0:4 ... sum of Dn = 10

5,2,1,0,4,3 Dn=5:1:1:3:0:2 ... sum of Dn = 12

2,4,0,3,5,1 Dn=2:3:2:0:1:4 ... sum of Dn = 12

3,1,5,4,2,0 Dn=3:0:3:1:2:5 ... sum of Dn = 14

5,3,2,4,0,1 Dn=5:2:0:1:4:4 ... sum of Dn = 14

5,3,2,4,1,0 Dn=5:2:0:1:3:5 ... sum of Dn = 16

(Sum 0-5 = 15, which is odd.)

UPDATE:

Before the clarification on the proof of the sum of differences

being even, I suggested this idea, using induction of a sort.

Anyone care to flesh it out?

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Maybe this is a proof that sum(Dn) is always even ?

0,1,2,3,4,5 Dn=0,0,0,0,0,0 Sum = 0 → even

Every permutation is a series of transpositions,

and every transposition preserves (Sum is even) ?

For example:

0,1,2,3,4,5 ... swap 0,3

3,1,2,0,4,5 → 3,0,0,3,0,0 Sum = 6 → even.

then swap 1,2

3,2,1,0,4,5 → 3,1,1,3,0,0 Sum = 8 → even.

then swap 0,4

3,2,1,4,0,5 → 3,1,1,1,4,0 Sum = 10 → even.

I haven't quite got the fine points of that down,

but it seems like a reasonable idea.

i once ate an orange at it was k

3,5,7,9 and so on